Writing Divided differences using macros

[CGMossa]

As some sort of enlightening exercise, I want to write divided differences in Rust using Macros.

After a lot of help from the discord channel, we've arrived at this

macro_rules! divided_difference {
    () => {};
    ([$($x:expr,)+]; $f:ident) => { $crate::divided_difference!([$($x),+]; $f) };
    ([$x:expr]; $f:ident) => {
        $f($x)
    };
    ([$left:expr, $right:expr]; $f:ident) => {
        ($f($right) - $f($left)) / ($right - $left)
    };
    ([$leftmost:expr $(,$middle:expr)* ,$rightmost:expr]; $f:ident) => {
        (divided_difference!([$($middle,)* $rightmost]; $f) - divided_difference!([$leftmost, $($middle),*]; $f)) / ($rightmost - $leftmost)
    };
}

where this fails to compile.

See playground.

[RustyYato]

You can use a variant of tt munchers to handle this

Rust Playground

[CGMossa]

This looks like it is the solution, but I am not familiar with @split. I also don't really see why you have another case for this, i.e.

    (@split [$leftmost:expr] [$($middle:expr),*] [$next:expr $(, $rest:expr)*]; $f:ident) => {
        divided_difference!(@split [$leftmost] [$($middle, )* $next] [$($rest),*]; $f)
    };

Thanks!

[RustyYato]

You need another internal state to handle the tt muncher, this is @split. I just like labeling internal states of this macro state machine with names. In this case split splits off the last element of the list.

[RustyYato]

That state is used to extract the middle. This is recursion, the first @split case is the base case, where there was nothing else in the middle. The second @split case is the recursive case, where there are items in the middle.

@split [0] [] [1, 2, 3, 4, 5] // second @split
@split [0] [1] [2, 3, 4, 5]
@split [0] [1, 2] [3, 4, 5]
@split [0] [1, 2, 3] [4, 5]
@split [0] [1, 2, 3, 4] [5] // first @split

// leftmost = 0
// middle = [1, 2, 3, 4]
// rightmost = 5

[xfix]

Normally, Rust macros essentially behave like linked list pattern match. So you can pattern match (x:xs), but you cannot pattern match the end of the linked list (this is the case in many functional programming languages too).

However, by making use of recursion, you can move the entire middle of the list to another list, leaving you with the last part of a list.

#[doc(hidden)]
#[macro_export]
macro_rules! __split_mid_right {
    ($f:tt $leftmost:tt [$(($middle:tt))*] [$rightmost:tt]) => {
        (
            $crate::divided_difference!([$($middle,)* $rightmost]; $f) -
            $crate::divided_difference!([$leftmost $(,$middle)*]; $f)
        ) / ($rightmost - $leftmost)
    };
    ($f:tt $leftmost:tt [$($ms:tt)*] [$x:tt $($xs:tt)*]) => {
        $crate::__split_mid_right!($f $leftmost [$($ms)* $x] [$($xs)*]);
    };
}

#[macro_export]
macro_rules! divided_difference {
    ([$($x:expr,)+]; $f:ident) => {
        $crate::divided_difference!([$($x),+]; $f)
    };
    ([$x:expr]; $f:ident) => {
        $f($x)
    };
    ([$left:expr, $right:expr]; $f:ident) => {
        ($f($right) - $f($left)) / ($right - $left)
    };
    ([$leftmost:expr $(,$middle:expr)*]; $f:ident) => {
        $crate::__split_mid_right!($f $leftmost [] [$(($middle))*])
    };
}