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

More information

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