Lazy Tree - level order

impl1.fs

// -----------------------------
// 1) Lazy List
// -----------------------------
type 'a lazyList =
    | LNil
    | LCons of Lazy<'a * 'a lazyList>

module LazyList =
    let cons x xs = LCons(lazy (x, xs))
    let empty<'a> : 'a lazyList = LNil

    let (|Cons|Nil|) (ls: 'a lazyList) =
        match ls with
        | LNil -> Nil
        | LCons lz ->
            let (hd, tl) = lz.Force()
            Cons(hd, tl)

    let rec iter f (ls: 'a lazyList) =
        match ls with
        | LNil -> ()
        | LCons lz ->
            let (hd, tl) = lz.Force()
            f hd
            iter f tl

// -----------------------------
// 2) Binary Tree
// -----------------------------
type 'a Tree =
    | Empty
    | Node of 'a * 'a Tree * 'a Tree

// -----------------------------
// 3) Purely Functional Queue
// -----------------------------
type 'a queue = 'a list * 'a list

module Queue =
    let empty = ([], [])
    let isEmpty (f, r) = (f = []) && (r = [])

    let enqueue x (f, r) =
        (f, x :: r)

    let dequeue = function
        | ([], []) -> failwith "Queue is empty."
        | (h :: t, r) -> (h, (t, r))
        | ([], r) ->
            match List.rev r with
            | [] -> failwith "Queue is empty."
            | h' :: f' -> (h', (f', []))

// -----------------------------
// 4) Lazy BFS
// -----------------------------
module LazyBFS =
    open LazyList
    open Queue

    /// Given a queue of subtrees, return a lazy list of their BFS order
    let rec bfs (q : 'a Tree queue) : 'a lazyList =
        if isEmpty q then
            LNil
        else
            let (front, qTail) = dequeue q
            match front with
            | Empty -> 
                bfs qTail
            | Node(value, left, right) ->
                LCons(lazy(
                    value, 
                    bfs (enqueue right (enqueue left qTail))
                ))

    /// BFS for the entire tree: start with root in an empty queue
    let levelOrder (root : 'a Tree) : 'a lazyList =
        bfs (enqueue root empty)

// -----------------------------
// 5) Example + Demo
// -----------------------------

// Build a small test tree:
//          1
//         / \
//        2   3
//       / \   \
//      4   5   6
let exampleTree = 
    Node(1,
            Node(2, Node(4, Empty, Empty),
                    Node(5, Empty, Empty)),
            Node(3, Empty,
                    Node(6, Empty, Empty)))

// Grab the BFS as a lazy list
let lazyBfs = LazyBFS.levelOrder exampleTree

// Now we can print them lazily:
// Only as we force each node do we do the BFS steps.
printfn "Level-order BFS traversal (entirely lazy):"
LazyList.iter (fun x -> printf "lazy: %d " x) lazyBfs
printfn "\n"

// If we wanted partial consumption, we could do something like:
// match lazyBfs with
// | LazyList.Cons(hd, tail) -> printfn "First node = %A" hd
// | LazyList.Nil -> printfn "Tree is empty"

impl2.fs

// Tree type definition
type 'a lazyTree =
    | EmptyTree 
    | TreeNode of Lazy<'a * 'a lazyTree * 'a lazyTree>

// Module definition with explicit signature
module LazyTree =
    // Expose the node constructor
    let node x l r = TreeNode(lazy(
        printfn "Evaluating node with value: %A" x
        (x, l, r)
    ))
        
    // Pattern matching by using .Force() to evaluate the lazy value
    let (|Node|Empty|) = function
        | EmptyTree -> Empty
        | TreeNode(lazyValue) -> 
            let value, left, right = lazyValue.Force()
            Node(value, left, right)
    
    // Print the tree level by level
    let rec printLevel level = function
        | Empty -> printfn "%*s-" (level * 4) ""
        | Node(value, left, right) ->
            printfn "%*s%A" (level * 4) "" value
            printLevel (level + 1) left
            printLevel (level + 1) right

// Now we need to use LazyTree.node explicitly
let tree = 
    LazyTree.node 1
        (LazyTree.node 2 
            (LazyTree.node 4 EmptyTree EmptyTree)
            (LazyTree.node 5 EmptyTree EmptyTree))
        (LazyTree.node 3
            (LazyTree.node 6 EmptyTree EmptyTree)
            (LazyTree.node 7 EmptyTree EmptyTree))

// Test the lazy evaluation
printfn "Starting tree traversal:"
LazyTree.printLevel 0 tree