 0 people like it.

# Binary tree traversal

Binary tree traversal with continuation passing style transformation and defuntionalization

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: ``` ``````type tree<'a> = | Leaf | Branch of 'a * tree<'a> * tree<'a> // naive preorder: preordernaive t let rec preordernaive t = match t with | Leaf -> [] | Branch(v, l, r) -> [v] @ (preordernaive l) @ (preordernaive r) // with memoization (not tail recursive): preordermem (t, []) let rec preordermem (t, vs) = match t with | Leaf -> vs | Branch (v, l, r) -> v :: preordermem (l, preordermem (r, vs)) // with continuation (tail recursive): preordercps t id let rec preordercps t k = match t with | Leaf -> k [] | Branch (v, l, r) -> preordercps r (fun r -> k <| (preordercps l (fun l -> v :: l) @ r)) // with continuation and defunctionalization (tail recursive): preorderdefun t ([], []) let rec preorderdefun t (k, vs) = match t with | Branch (v, l, _) -> preorderdefun l (t :: k, v :: vs) | Leaf -> match k with | Branch (_, _, r) :: k' -> preorderdefun r (k', vs) | Leaf :: _ | [] -> List.rev vs ``````
union case tree.Leaf: tree<'a>
union case tree.Branch: 'a * tree<'a> * tree<'a> -> tree<'a>
type tree<'a> =
| Leaf
| Branch of 'a * tree<'a> * tree<'a>
val preordernaive : t:tree<'a> -> 'a list
val t : tree<'a>
val v : 'a
val l : tree<'a>
val r : tree<'a>
val preordermem : t:tree<'a> * vs:'a list -> 'a list
val vs : 'a list
val preordercps : t:tree<'a> -> k:('a list -> 'a list) -> 'a list
val k : ('a list -> 'a list)
val r : 'a list
val l : 'a list
val preorderdefun : t:tree<'a> -> k:tree<'a> list * vs:'a list -> 'a list
val k : tree<'a> list
val k' : tree<'a> list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member GetReverseIndex : rank:int * offset:int -> int
member GetSlice : startIndex:int option * endIndex:int option -> 'T list