Skip to content

Instantly share code, notes, and snippets.

@inanna-malick
Created September 17, 2019 16:16
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save inanna-malick/99266d80feb5fa3ce3a260ad17ffa646 to your computer and use it in GitHub Desktop.
Save inanna-malick/99266d80feb5fa3ce3a260ad17ffa646 to your computer and use it in GitHub Desktop.
terrible idea - anamorphism is not idiomatic in rust. I think I need to use refcell (mut pointers up/down tree)
//stack-safe anamorphism (unfolding change). Builds a tree layer by layer.
pub fn ana<X>(f: impl Fn(X) -> Tree<X>, seed: X) -> FixTree {
let mut instructions: Vec<Option<X>> = vec![]; // depth first, Some == add child w/ seed, None == back a level
let mut path_to_root: Vec<&mut Vec<Box<FixTree>>> = vec![]; // pointer to children of focused node
// ^ this breaks it, requires multiple borrows... drop this in a gist (or use refcel, rain says to do so)
let root = f(seed);
match root {
Tree::Leaf(n) => FixTree(Tree::Leaf(n)),
Tree::Node(xs) => {
for x in xs.into_iter() {
instructions.push(Some(x));
instructions.push(None)
}
let mut focus = vec![];
path_to_root.push(&mut focus);
while let Some(mut focus) = path_to_root.pop() {
while let Some(instruction) = instructions.pop() {
match instruction {
None => {
break; // pop next node up towards root
}
Some(x) => {
let to_push = f(x);
match to_push {
Tree::Leaf(n) => {
&focus.push(Box::new(FixTree(Tree::Leaf(n))));
}
Tree::Node(xs) => {
// right after this must set focus to pushed node's children
for x in xs.into_iter() {
instructions.push(Some(x));
instructions.push(None)
}
// update focus pointer
&focus.push(Box::new(FixTree(Tree::Node(vec!()))));
path_to_root.push(focus); // TODO: also push to path to root? (DONE)
let mut new_focus = focus.last_mut().unwrap().0.children_mut().unwrap();
// TODO: need to _instead_
focus = &mut new_focus;
}
}
}
}
}
}
FixTree(Tree::Node(focus))
}
}
}
struct FixTree(Tree<Box<FixTree>>);
enum Tree<X> {
Node(Vec<X>),
Leaf(u64),
}
impl<X> Tree<X> {
fn children_mut(&mut self) -> Option<&mut Vec<X>> {
match self {
Tree::Node(xs) => Some(xs),
Tree::Leaf(_) => None,
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment