Hello,
I am given a function:
let rec tfold (l:'a → 'b) (f:'a → 'b → 'b → 'b) (t:'a tree) : 'b =
match t with
| Leaf v → l v
| Fork (v, t1, t2) → f v (tfold l f t1) (tfold l f t2)
What does (l:'a → 'b) do?
Thank you.
It is an argument with a type annotation.
Without type annotations, the function would look like:
let rec tfold l f t =
...
OCaml most likely could infer the types of l, f, and t based on the implementation, but you can give the compiler hints to make sure the inferred types are correct.
In this case, you are hinting that l is of type 'a -> 'b (a function mapping a value of type 'a to a value of type 'b), f is of type 'a -> 'b -> 'b -> 'b, and t is of type 'a tree. The whole tfold function returns a value of type 'b (see the : 'b just before =).
Hope this helps.
1 Like
For example, I want to know the size of my tree. What is the role of function l beside function f in tfold?
I’m assuming this is an exercise/homework, so I’ll try not to give you direct answers.
First, I would need to ask, are you familiar with folds on lists? If so, can you implement a function to calculate the size of a list by using fold?
If you can do it already, the base idea is quite similar for trees.
l is a function that will be called when the current tree is a leaf. What is the size of a leaf-only tree?
f is a function that will be called when the current tree is a fork. A fork have two subtrees. Suppose you already know the size of the subtrees, how can you calculate the size of the current tree based on that information?
After you nailed them, recursion will do its magic 
3 Likes