Created
September 17, 2019 16:16
-
-
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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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