3 people like it.
Like the snippet!
Layout binary tree
Solution to the layout binary tree problem from 99 OCaml problems
1:
2:
3:
4:
5:
6:
7:

type 'a binary_tree =
 Empty
 Node of 'a * 'a binary_tree * 'a binary_tree
let example_tree =
Node('a', Node('b', Node('d', Empty, Empty), Node('e', Empty, Empty)),
Node('c', Empty, Node('f', Node('g', Empty, Empty), Empty)))

1:
2:
3:
4:
5:

let rec count_leaves tree =
match tree with
 Empty > 0
 Node(_,Empty,Empty) > 1
 Node(_,a,b) > (count_leaves a) + (count_leaves b)

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

type 'a pos_binary_tree =
 E (* represents the empty tree *)
 N of 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree
(*N(w,x,y,l,r) represents a (nonempty) binary tree with root w "positioned" at (x,y), and subtrees l and r *)
let make_pos_binary_tree (tree:binary_tree<_>) =
let rec layout t x depth =
match t with
 Empty > (x,E)
 Node(a,l,r) >
let x',lTree = layout l x (depth+1)
let x'',rTree = layout r (x'+1) (depth+1)
(x'',N(a,x',depth,lTree,rTree))
let finalX,finalTree = layout tree 1 1
finalTree

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

let laidOutTree = make_pos_binary_tree example_tree
let canvas = Array2D.init 50 50 (fun _ _ > ' ')
let rec draw tree =
match tree with
 E > ()
 N(v,x,y,l,r) >
canvas.[y,x] < v
draw l
draw r
draw laidOutTree
for y in 0..49 do
for x in 0..49 do
stdout.Write(canvas.[y,x])
stdout.WriteLine()

union case binary_tree.Empty: 'a binary_tree
union case binary_tree.Node: 'a * 'a binary_tree * 'a binary_tree > 'a binary_tree
type 'a binary_tree =
 Empty
 Node of 'a * 'a binary_tree * 'a binary_tree
Full name: Script.binary_tree<_>
val example_tree : char binary_tree
Full name: Script.example_tree
val count_leaves : tree:'a binary_tree > int
Full name: Script.count_leaves
val tree : 'a binary_tree
val a : 'a binary_tree
val b : 'a binary_tree
type 'a pos_binary_tree =
 E
 N of 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree
Full name: Script.pos_binary_tree<_>
union case pos_binary_tree.E: 'a pos_binary_tree
union case pos_binary_tree.N: 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree > 'a pos_binary_tree
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 make_pos_binary_tree : tree:'a binary_tree > 'a pos_binary_tree
Full name: Script.make_pos_binary_tree
val layout : ('b binary_tree > int > int > int * 'b pos_binary_tree)
val t : 'b binary_tree
val x : int
val depth : int
val a : 'b
val l : 'b binary_tree
val r : 'b binary_tree
val x' : int
val lTree : 'b pos_binary_tree
val x'' : int
val rTree : 'b pos_binary_tree
val finalX : int
val finalTree : 'a pos_binary_tree
val laidOutTree : char pos_binary_tree
Full name: Script.laidOutTree
val canvas : char [,]
Full name: Script.canvas
module Array2D
from Microsoft.FSharp.Collections
val init : length1:int > length2:int > initializer:(int > int > 'T) > 'T [,]
Full name: Microsoft.FSharp.Collections.Array2D.init
val draw : tree:char pos_binary_tree > unit
Full name: Script.draw
val tree : char pos_binary_tree
val v : char
val y : int
val l : char pos_binary_tree
val r : char pos_binary_tree
val y : int32
val x : int32
val stdout<'T> : System.IO.TextWriter
Full name: Microsoft.FSharp.Core.Operators.stdout
More information