type 'a mylist =
| Nil
| Cons of 'a * 'a mylist
let rec map f = function
| Nil -> Nil
| Cons (h, t) -> Cons (f h, map f t)
type 'a tree =
| Leaf
| Node of 'a * 'a tree * 'a tree
let rec map f = function
| Leaf -> Leaf
| Node (v, l, r) -> Node (f v, map f l, map f r)
type 'a mylist = Nil | Cons of 'a * 'a mylist
val map : ('a -> 'b) -> 'a mylist -> 'b mylist = <fun>
type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree
val map : ('a -> 'b) -> 'a tree -> 'b tree = <fun>
let lst = map succ (Cons (1, Nil))
File "[2]", line 1, characters 20-24:
1 | let lst = map succ (Cons (1, Nil))
^^^^
Error: This variant expression is expected to have type int tree
The constructor Cons does not belong to type tree
Well that's an issue! OCaml is trying to use the most recent definition of map, which is the one for 'a tree, not 'a mylist.
We can fix this with a module.
module MyList = struct
type 'a mylist =
| Nil
| Cons of 'a * 'a mylist
let rec map f = function
| Nil -> Nil
| Cons (h, t) -> Cons (f h, map f t)
end
module Tree = struct
type 'a tree =
| Leaf
| Node of 'a * 'a tree * 'a tree
let rec map f = function
| Leaf -> Leaf
| Node (v, l, r) -> Node (f v, map f l, map f r)
end
module MyList :
sig
type 'a mylist = Nil | Cons of 'a * 'a mylist
val map : ('a -> 'b) -> 'a mylist -> 'b mylist
end
module Tree :
sig
type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree
val map : ('a -> 'b) -> 'a tree -> 'b tree
end
Awesome, now we have modules!
let lst = map succ (Cons (1, Nil))
File "[4]", line 1, characters 20-24:
1 | let lst = map succ (Cons (1, Nil))
^^^^
Error: This variant expression is expected to have type int tree
The constructor Cons does not belong to type tree
Hmm that still didn't work. That's because we need to specify the name.
let lst = MyList.map succ (Cons (1, Nil))
val lst : int MyList.mylist = MyList.Cons (2, MyList.Nil)
Note that we have an int MyList.mylist, not a MyList.int mylist or anything like that.
All three of these are valid ways of specifying the type of a tree node.
let t = Tree.Node(1, Tree.Leaf, Tree.Leaf)
let t = Tree.Node(1, Leaf, Leaf)
let t : int Tree.tree = Node(1, Leaf, Leaf)
val t : int Tree.tree = Tree.Node (1, Tree.Leaf, Tree.Leaf)
val t : int Tree.tree = Tree.Node (1, Tree.Leaf, Tree.Leaf)
val t : int Tree.tree = Tree.Node (1, Tree.Leaf, Tree.Leaf)