F# Seq.unfold for recursive structure

When I blogged the CSP style, I was wondering if there a better way to resolve this problem. Today I read through the Roman string generation snippet from F# snippet site. I suddenly realize the Seq.fold and Seq.unfold is something I was chasing for.

Let me first start with the Seq.unfold. The MSDN document only shows how to generate seq from a single point. I am trying to solve is to decompose a complex recursive structure and generate a sequence. A typical complex recursive structure is a tree.

The tree definition is shown like the following:

 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))))  

• The first sample is to traverse the tree by layer. Do you notice where is the queue? :-)

 let f state =   
   match state with  
   | [] -> None  
   | h::t ->   
     match h with   
     | Nil -> None  
     | Node(v, Nil, Nil) -> Some (v, t)  
     | Node(v, subTree, Nil)  
     | Node(v, Nil, subTree) -> Some (v, t@[subTree])  
     | Node(v, l, r) -> Some (v, t@[l;r])  
 Seq.unfold generator2 [tree]  
 |> Seq.toList  

• The second sample is to change the code a little bit and see what can happen.. :-). You can run the code and see if the output is same to pre-order traversal.

 let generator2 state =   
   match state with  
   | [] -> None  
   | h::t ->   
     match h with   
     | Nil -> None  
     | Node(v, Nil, Nil) -> Some (v, t)  
     | Node(v, subTree, Nil)  
     | Node(v, Nil, subTree) -> Some (v, [subTree]@t)  
     | Node(v, l, r) -> Some (v, [l;r]@t)  
 Seq.unfold generator2 [tree]  
 |> Seq.toList  

It is getting late, I will come back to give more samples using the powerful Seq.fold and Seq.unfold.

Tweet to fsharp