Saturday, November 17, 2012

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