16 people like it.

Tree searching using Tail recursion with continuation

Sample code which demonstrate tree searching using : Tail recursion with continuation

 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: 
open System

type 'a Tree = 
    | Node of ('a Tree list * 'a)

let myTree = Node([
                    Node(
                          [Node([],21); 
                           Node([],22) 
                          ]
                        ,2);
                    Node([],3); 
                    Node([ 
                          Node([],41); 
                          Node([],42) 
                         ]
                        ,4)
                   ]
                  ,1)

let rec findTree (cont:unit -> int) (find:int)  (t:int Tree list)= 
    match t with
    | [] -> cont()
    | (h::t) -> match h with
                | Node(child,value) ->  if value = find then 1 
                                        else t |> findTree (fun _ -> findTree cont find child) find
    

[myTree] |> findTree (fun _ -> 0) 22 |> Console.WriteLine 
//0 for not found, 1 for found
namespace System
type 'a Tree = | Node of ('a Tree list * 'a)

Full name: Script.Tree<_>
union case Tree.Node: ('a Tree list * 'a) -> 'a Tree
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val myTree : int Tree

Full name: Script.myTree
val findTree : cont:(unit -> int) -> find:int -> t:int Tree list -> int

Full name: Script.findTree
val cont : (unit -> int)
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val find : int
val t : int Tree list
val h : int Tree
val child : int Tree list
val value : int
type Console =
  static member BackgroundColor : ConsoleColor with get, set
  static member Beep : unit -> unit + 1 overload
  static member BufferHeight : int with get, set
  static member BufferWidth : int with get, set
  static member CapsLock : bool
  static member Clear : unit -> unit
  static member CursorLeft : int with get, set
  static member CursorSize : int with get, set
  static member CursorTop : int with get, set
  static member CursorVisible : bool with get, set
  ...

Full name: System.Console
Console.WriteLine() : unit
   (+0 other overloads)
Console.WriteLine(value: string) : unit
   (+0 other overloads)
Console.WriteLine(value: obj) : unit
   (+0 other overloads)
Console.WriteLine(value: uint64) : unit
   (+0 other overloads)
Console.WriteLine(value: int64) : unit
   (+0 other overloads)
Console.WriteLine(value: uint32) : unit
   (+0 other overloads)
Console.WriteLine(value: int) : unit
   (+0 other overloads)
Console.WriteLine(value: float32) : unit
   (+0 other overloads)
Console.WriteLine(value: float) : unit
   (+0 other overloads)
Console.WriteLine(value: decimal) : unit
   (+0 other overloads)
Raw view Test code New version

More information

Link:http://fssnip.net/1F
Posted:13 years ago
Author:Ankur Dhama
Tags: tail recursion , continuation