Recursion Schemes in Rust (naive)

main.rs

trait Rec : Sized{
  type F<T>;
  fn fmap<A,B>(f : impl Fn(A)->B, x : Self::F<A>) -> Self::F<B>;

  fn prj(t : Self)->Self::F<Self>;
  fn inj(t : Self::F<Self>)->Self;
}
fn fold<R : Rec, A>(step : &impl Fn(R::F<A>)->A, x : R )->A {
  step(
    R::fmap(
      |x| fold(step, x), 
      R::prj(x)
    )
  )
}

fn unfold<R : Rec, A>(gen : &impl Fn(A )->R::F<A>, x : A )->R {
  R::inj(
    R::fmap(
      |x| unfold(gen, x), 
      gen(x)
    )
  )
}


// fn hylo<R : Rec, A, B>(step : &impl Fn(R::F<B>)->B, gen : &impl Fn(A )->R::F<A>, x : A )->B {
//   fold::<R,B>(step, unfold::<R,A>(gen, x ))
// }
fn hylo<R : Rec, A, B>(
  step : &impl Fn(R::F<B>)->B, 
  gen  : &impl Fn(A)->R::F<A>, 
  x : A
)->B {
    step( <R>::fmap(|a| hylo::<R,A,B>(step, gen, a), gen(x)))
}

#[derive(Debug)]
pub enum BinaryTree {
    Leaf(i32),
    Branch(Box<BinaryTree>, Box<BinaryTree>),
}
fn l(i: i32) -> BinaryTree {
    BinaryTree::Leaf(i)
}
fn b(l: BinaryTree, r: BinaryTree) -> BinaryTree {
    BinaryTree::Branch(Box::new(l), Box::new(r))
}

pub enum FBinaryTree<T> {
  Leaf(i32),
  Branch(T,T)
}

impl Rec for BinaryTree {
  type F<T> = FBinaryTree<T>;

  fn inj(t : Self::F<Self>)->Self {
      match t {
        FBinaryTree::Leaf(n) => BinaryTree::Leaf(n),
        FBinaryTree::Branch(l, r) => BinaryTree::Branch(Box::new(l), Box::new(r)),
      }
  }
  fn prj(t : Self)->Self::F<Self> {
      match t {
        BinaryTree::Leaf(n) => FBinaryTree::Leaf(n),
        BinaryTree::Branch(l, r) => FBinaryTree::Branch(*l,*r),
      }
  }
  fn fmap<A,B>(f : impl Fn(A)->B, x : Self::F<A>) -> Self::F<B> {
      match x {
        FBinaryTree::Leaf(n) => FBinaryTree::Leaf(n),
        FBinaryTree::Branch(l, r) => FBinaryTree::Branch(f(l), f(r)),
      }
  }
}



enum Nat<T> {
  S(T),
  Z
}

impl Rec for u8 {
  type F<T> = Nat<T>;

  fn prj(t : Self)->Self::F<Self> {
      match t {
        0 => Nat::Z,
        n => Nat::S(n-1)
      }
  }
  fn inj(t : Self::F<Self>)->Self {
      match t {
        Nat::S(n) => n+1,
        Nat::Z => 0,
          }
  }

  fn fmap<A,B>(f : impl Fn(A)->B, x : Self::F<A>) -> Self::F<B> {
      match x {
        Nat::S(n) => Nat::S(f(n)),
        Nat::Z => Nat::Z,
      }
  }
}




fn g() {





  let tree_ = unfold::<BinaryTree, i32>(&|x| 
    match x { 
      0 => FBinaryTree::Leaf(0), 
      b => FBinaryTree::Branch(b/2 , b/2)
    }, 10);
  println!("tree : {tree_:#?}");

  // let count = fold::<BinaryTree,usize>(
  //   &|x| match x {
  //       FBinaryTree::Leaf(_) => 1,
  //       FBinaryTree::Branch(l, r) => l+r,
  //   }, 
  //   tree_);
  // println!("count : {count:?}")


  let n = unfold::<u8,BinaryTree>(
    &|x| match x {
        BinaryTree::Leaf(_) => Nat::Z,
        BinaryTree::Branch(l, r) => match *l {
            BinaryTree::Leaf(_) => Nat::S(*r),
            BinaryTree::Branch(l1, r1) => Nat::S(b(*l1, b(*r1, *r))),
        },
    },
  tree_); 
  println!("n : {n:?}");

  let double = fold::<u8, u16>(
    &|x| match x {
        Nat::S(n) => {println!("S");2 + n},
        Nat::Z => {println!("Z");0},
    },
    n
  );
  println!("double : {double:?}");

  // let wtf = fold::<u8,Box<dyn FnOnce(u16)->u16>>(
  //   &|x|match x {
  //       Nat::S(f) => Box::new(|x| f(x+2)),
  //       Nat::Z => Box::new(|x| x),
  //   }, 
  //   n
  // );

  // println!("wtf(0) : {:?}",wtf(0)); 
  
  let tree = b(b(l(1), l(2)), b(b(l(3), l(4)), l(5)));

  let sum = fold::<BinaryTree, Box<dyn FnOnce(isize)->isize>> (
    &|x| match x {
        FBinaryTree::Leaf(n) => Box::new(move |x| {
          println!("L");
          x + n as isize
        }),
        FBinaryTree::Branch(l, r) => Box::new(|x| {
          println!("B");
          l(r(x))
        }) ,
    },
    tree
  );
  println!("sum : {}", sum(0));
}



fn main() {
    g();
}