1 people like it.

Tree folding

How to fold a tree left branch first.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 

type Tree<'a> =
  | Node of Tree<'a> * 'a * Tree<'a>
  | Leaf

let rec fold (f : 'b -> Tree<'a> -> 'b) (m  : 'b) (t : Tree<'a>) : 'b =
  let m' = f m t
  match t with
    | Node(tl, _, tr) -> fold f (fold f m' tl) tr
    | Leav -> m'

let sum t =
  let folder m t' : int =
    match t' with
      | Node(_, v, _) -> m + v
      | Leaf -> m
  fold folder 0 t

let testTree =
  Node(Node(Node(Leaf, 9, Leaf), 2, Node(Leaf, 21, Leaf)), 12, Leaf)
union case Tree.Node: Tree<'a> * 'a * Tree<'a> -> Tree<'a>
type Tree<'a> =
  | Node of Tree<'a> * 'a * Tree<'a>
  | Leaf

Full name: Script.Tree<_>
union case Tree.Leaf: Tree<'a>
val fold : f:('b -> Tree<'a> -> 'b) -> m:'b -> t:Tree<'a> -> 'b

Full name: Script.fold
val f : ('b -> Tree<'a> -> 'b)
val m : 'b
val t : Tree<'a>
val m' : 'b
val tl : Tree<'a>
val tr : Tree<'a>
val Leav : Tree<'a>
val sum : t:Tree<int> -> int

Full name: Script.sum
val t : Tree<int>
val folder : (int -> Tree<int> -> int)
val m : int
val t' : Tree<int>
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 v : int
val testTree : Tree<int>

Full name: Script.testTree
Raw view Test code New version

More information

Link:http://fssnip.net/tb
Posted:9 years ago
Author:krgn
Tags: tree , folding

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.