pattern_core/pattern/
unfold.rs

1//! unfold: anamorphism for building a Pattern tree from a seed.
2//!
3//! Ported from `Pattern.Core.unfold` in the Haskell reference implementation.
4//! Implemented iteratively with an explicit work stack to avoid stack overflow
5//! on deep hierarchies.
6
7use crate::pattern::Pattern;
8
9/// Anamorphism: expand a seed into a `Pattern<V>` tree.
10///
11/// `expand` receives a seed and returns the value for the current node plus
12/// a list of child seeds. The tree is built iteratively (work stack) to avoid
13/// stack overflow for arbitrarily deep hierarchies.
14///
15/// # Examples
16///
17/// ```rust
18/// use pattern_core::unfold;
19///
20/// // Build a depth-3 binary tree from a depth seed
21/// let tree = unfold(|depth: u32| {
22///     if depth == 0 {
23///         (depth, vec![])
24///     } else {
25///         (depth, vec![depth - 1, depth - 1])
26///     }
27/// }, 2u32);
28///
29/// assert_eq!(tree.value, 2);
30/// assert_eq!(tree.elements.len(), 2);
31/// assert_eq!(tree.elements[0].value, 1);
32/// ```
33pub fn unfold<A, V>(expand: impl Fn(A) -> (V, Vec<A>), seed: A) -> Pattern<V> {
34    // Two-phase iterative implementation using an explicit work stack.
35    // Work::Expand(seed)       — expand the seed, push children then Collect
36    // Work::Collect(value, n)  — pop n children from result stack, assemble Pattern
37
38    enum Work<A, V> {
39        Expand(A),
40        Collect(V, usize),
41    }
42
43    let mut work_stack: Vec<Work<A, V>> = vec![Work::Expand(seed)];
44    let mut result_stack: Vec<Pattern<V>> = Vec::new();
45
46    while let Some(item) = work_stack.pop() {
47        match item {
48            Work::Expand(s) => {
49                let (value, children) = expand(s);
50                let n = children.len();
51                // Collect marker runs after all children are assembled
52                work_stack.push(Work::Collect(value, n));
53                // Push children in reverse so leftmost is processed first (LIFO)
54                for child in children.into_iter().rev() {
55                    work_stack.push(Work::Expand(child));
56                }
57            }
58            Work::Collect(value, n) => {
59                let start = result_stack.len() - n;
60                let elements: Vec<Pattern<V>> = result_stack.drain(start..).collect();
61                result_stack.push(Pattern { value, elements });
62            }
63        }
64    }
65
66    result_stack
67        .pop()
68        .expect("unfold: result stack should have exactly one element")
69}
pattern_core/pattern/unfold.rs

pattern_core/pattern/
unfold.rs
