OCaml Explicit polymorphic type annotations

Question

I would enjoy to receive some helpful comments concerning an example given on:
http://caml.inria.fr/pub/docs/manual-ocaml-400/manual021.html#toc79

7.12 Explicit polymorphic type annotations

type 'a t = Leaf of 'a | Node of ('a * 'a) t

let rec depth : 'a. 'a t -> 'b = function
|Leaf _ -> 1
| Node x -> 1 + depth x

I understand this example function, but when I try to define a 'map-like' function of type

'a. 'a t -> ('a -> 'b) -> 'b t

e.g.:

let rec tmap: 'a. 'a t ->(f:'a->'b) -> 'b t = function
|Leaf x ->  Leaf( f x) 
|Node x -> let res = tmap x in Node(res);;

I get the following error:

Characters 67-77:
  |Leaf x ->  Leaf( f x)
              ^^^^^^^^^^

Error: This expression has type 'c t but an expression was expected of type
         (f:'a -> 'b) -> 'b t

which I do not completely understand. I would appreciate any helpful comment.

Answer 1

You forgot to get the second argument.

let rec tmap:
 'a. 'a t ->(f:'a->'b) -> 'b t = (* asking for two arguments *)
 function (* takes only the first argument *)
|Leaf x -> Leaf( f x)
|Node x -> let res = tmap x in Node(res);; 

Also, 'b must be polymorphic too, as you want to generate nested tuples as long as you descend through the tree.

This should be, thanks to ivg:

let rec tmap : 'a 'b. 'a t -> f:('a->'b) -> 'b t =  fun t ~f ->
  match t with
  |Leaf x -> Leaf( f x)
  |Node x -> let f (a,b) = (f a, f b) in Node ( tmap x ~f ) ;;

Answer 2

You have a few problems, like improperly placed parenthesis around f, forgotten argument to the tmap function in the Node branch, and you've forget the quantifier for 'b. So, finally, with the help of PatJ we can write the following:

type 'a t = Leaf of 'a | Node of ('a * 'a) t

let rec depth : 'a. 'a t -> 'b = function
  | Leaf _ -> 1
  | Node x -> 1 + depth x


let rec tmap: 'a 'b. 'a t -> f:('a -> 'b) -> 'b t =
  fun t ~f -> match t with
    | Leaf x -> Leaf (f x)
    | Node x ->
      Node (tmap ~f:(fun (x,y) -> f x, f y) x)

tmap (Node (Leaf (7,8))) ~f:(fun x -> x + 1, x + 2);;
- : (int * int) t = Node (Leaf ((8, 9), (9, 10)))