pufuwozu/roy — Issue #68: Show off recursion on recursive datatypes
Author: eegg
Created: 2011-12-12 20:10:22+00:00
State: open

Common functions such as map, fold, etc. Here's some stuff to pick from:

```haskell
// Lists
data List a = Nil | Cons a (List a)

let listToStr l = match l
case Nil = ""
case (Cons x xs) = x ++ " " ++ (listToStr xs)

// example lists
let ex1 = Cons 2 (Cons 3 (Cons 7 (Cons -5 (Cons 7 (Cons 10 Nil)))))
let ex2 = Cons 6 (Cons -8 Nil)
let strListEx = (Cons "hello" (Cons "list," (Cons "from" (Cons "Roy" Nil))))

console.log "Example list of words:" (listToStr strListEx)

// Map function f over a list l
let map f l = match l
case Nil = Nil
case (Cons hd tl) = Cons (f hd) (map f tl)

// Left-fold l starting with s using f
let foldl f s l = match l
case Nil = s
case (Cons hd tl) = foldl f (f s hd) tl

// Example fold functions
let sum l = foldl (\a b -> a + b) 0 l
let product l = foldl (\a b -> a * b) 1 l

console.log "Sum:" (sum ex1)
console.log "Product:" (product ex1)

let append l1 l2 = match l1
case Nil = l2
case (Cons hd tl) = Cons hd (append tl l2)

let ex1ex2 = append ex1 ex2

// Lists of lists ...
let concat ls = foldl append Nil ls

data Ordering = LT | EQ | GT
let compare a b =
if a < b then
LT
else
if a == b then
EQ
else
GT

let orderingToString o = match o
case LT = "LT"
case EQ = "EQ"
case GT = "GT"

console.log "compare 4 5:" (orderingToString (compare 4 5))
console.log "compare 7 -3:" (orderingToString (compare 7 -3))
console.log "compare 1 1:" (orderingToString (compare 1 1))

data Tree a = Node (Tree a) a (Tree a) | Leaf
let search t x = match t
case Leaf = false
case (Node l v r) = match (compare x v)
case LT = search l x
case EQ = true
case GT = search r x

let insert t x = match t
case Leaf = Node Leaf x Leaf
case (Node l v r) = match (compare x v)
case LT = Node (insert l x) v r
case EQ = Node l v r
case GT = Node l v (insert r x)

let fromList l = foldl insert Leaf l

// Create a tree from our appended list
let tree = fromList ex1ex2

console.log "Search tree for 5:" (search tree 5)
console.log "Search tree for 7:" (search tree 7)

let toList t = match t
case Leaf = Nil
case (Node l v r) = concat (Cons (toList l) (Cons (Cons v Nil) (Cons (toList r) Nil)))

// Sort and eliminate duplicates :)
let treeSort l = toList (fromList l)
```