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: 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 IReadOnlyList<'T>
    interface IReadOnlyCollection<'T>
    interface IEnumerable
    interface IEnumerable<'T>
    member GetReverseIndex : rank:int * offset:int -> int
    member GetSlice : startIndex:int option * endIndex:int option -> 'T list
    member Head : 'T
    member IsEmpty : bool
    member Item : index:int -> 'T with get
    member Length : int
    ...

val rev : list:'T list -> 'T list

Next Version Raw view Test code New version

More information

Link:	http://fssnip.net/876
Posted:	2 years ago
Author:	tathanhdinh
Tags:	binary tree , continuation passing