I need to generate an iterator that traverses a binary tree of n variables.
Where the parent node represents a function and the child node represents a value.
For example when n = 4, there are 5 constructors:
f(n,f(n,f(n,n)))
f(n,f(f(n,n),n))
f(f(n,n),f(n,n))
f(f(n,f(n,n)),n)
f(f(f(n,n),n),n)
How should I generate iterators for general cases?
Some hard coded attempts:
use std::slice::Iter;
fn catalan_tree3<T: Copy>() -> Iter<'static, fn(&[fn(T, T) -> T], &[T]) -> T> {
// &[fn(&[fn(T, T) -> T; 2], &[T; 3]) -> T; 2]
let fs: &[fn(&[fn(T, T) -> T], &[T]) -> T; 2] = &[
|f, n| f[0](n[0], f[1](n[1], n[2])),
|f, n| f[0](f[1](n[0], n[1]), n[2])
];
return fs.iter();
}
fn catalan_tree4<T: Copy>() -> Iter<'static, fn(&[fn(T, T) -> T], &[T]) -> T> {
// &[fn(&[fn(T, T) -> T; 3], &[T; 4]) -> T; 5]
let fs: &[fn(&[fn(T, T) -> T], &[T]) -> T; 5] = &[
|f, n| f[0](n[0], f[1](n[1], f[2](n[2], n[3]))),
|f, n| f[0](n[0], f[1](f[2](n[1], n[2]), n[3])),
|f, n| f[0](f[1](n[0], n[1]), f[2](n[2], n[3])),
|f, n| f[0](f[1](n[0], f[2](n[1], n[2])), n[3]),
|f, n| f[0](f[1](f[2](n[0], n[1]), n[2]), n[3]),
];
return fs.iter();
}
fn catalan_tree<'a, T>(n: usize) -> Iter<'a, fn(&[fn(T, T) -> T], &[T]) -> T> {
// I am not sure if such type annotation is appropriate
unimplemented!()
}
#[test]
fn test() {
use std::ops::{Add, Sub};
let fs: Vec<fn(i32, i32) -> i32> = vec![Add::add, Sub::sub];
let ns: Vec<i32> = vec![1, 2, 3];
// for f in catalan_tree::<i32>(3)
for f in catalan_tree3::<i32>() {
println!("{}", f(&fs, &ns))
}
}