Seq.unfold and recursive

Let me continue yesterday's post about using unfold to get rid of recursive function call.

First starts with a simple sample. the following code is a Fibonacci sequence generator.

 let seq = Seq.unfold (fun (i,j) -> Some(i, (i,i+j))) (1I, 1I)  
 seq |> Seq.take 100 |> Seq.toList  

The post-order traversal can also use unfold. The algorithm takes a list as state variable. If the head of the list is a simple value, yield it into the sequence. This operation decreases the list length by 1. If the head element is a subtree which is in (v, left, right) format, then replace the subtree element with three elements: left, right, and v. This operation increases the list length by 2 (= add 3 elements and remove 1 element). The code is listed below:

 type NodeType = int  

 type BinaryTree =   
   | Nil   
   | Node of NodeType * BinaryTree * BinaryTree  
 let tree = Node(5,  
         Node(42,   
            Node(3, Nil, Nil),  
            Node(2, Nil, Nil)),  
         Node(4,   
            Node(13,   
              Node(14, Nil, Nil),   
              Node(16, Nil, Nil)),  
            Node(12,   
              Node(15, Nil, Nil),   
              Node(21,   
                 Node(22, Nil, Nil),   
                 Nil))))  

 let postOrder state =  
   match state with   
   | [] -> None  
   | h::t ->  
     match h with  
     | Nil -> None  
     | Node(v, Nil, Nil) -> Some (Some v, t)  
     | Node(v, subTree, Nil)  
     | Node(v, Nil, subTree) -> Some (None, [subTree; Node(v, Nil, Nil)]@t)  
     | Node(v, l, r ) -> Some (None, [l; r; Node(v, Nil, Nil)] @t)  

 Seq.unfold postOrder [tree]  
 |> Seq.filter (fun n -> n.IsSome)  
 |> Seq.map (fun (Some(n)) -> n)  
 |> Seq.toList  

Tweet to fsharp