## Friday, November 16, 2012

### 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.