CODEWITHSUNDEEP
ocaml
Ockham
Ockham

Reputation: 3

How to use recursive types

I need a function that sums up all numbers in a tree, recursively.

So I defined:

  1. A tree type, which I have defined as type tree = [] | Intlist of int list | Treelist of tree list;;

  2. A sum function, like

let rec sum_list list = 
  match list with  
    Treelist (head::tail) -> (sum_list head) + (sum_list tail) 
  | Intlist (head::tail)  -> head + (sum_list tail) 
  | []                    -> 0

The error I get on trying to compile this is this:

Error: This expression has type tree list but an expression was expected of type tree

which refers to thesecond sumlist in the Treelist clause. For me it seems that an expression of type tree list should of type tree.

What is wrong? The function or my definition of a tree?

Upvotes: 0

Views: 183

Answers (2)

octachron
octachron

Reputation: 18892

First, it is better to not use the [] constructor in type definition when learning OCaml. Using this [] constructor is only useful when defining alternative list types (with GADTs for instance), and by doing so it shadows the usual [] constructor from the usual list type.

Let's thus replace it with Empty in the definition of tree:

type tree =
| Empty
| Intlist of int list 
| Treelist of tree list

Second, it sounds like you might be misreading the definition of TreeList in

type tree =
| Empty
| Intlist of int list 
| Treelist of tree list

This definition does not mean that a tree of list is a tree. It means that one can build a tree by applying the constructor TreeList on a tree of list:

let treelist (x:tree list): tree = TreeList x

Thus in

let rec sum_list list = match list with
  | Treelist (head::tail) -> sum_list head + sum_list tail
  | Intlist (head :: tail) -> head + sum_list tail
  | Empty -> 0

the typechecker is correctly complaining that tail is not a tree but a list of trees. The tree that contains the list of trees tail would be TreeList tail. The same is true for the IntList case, tail is not a tree but a list of integers, and the tree that would contain the list of integers tail would be IntList tail.

Upvotes: 4

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66808

Look at this expression:

(sum_list head) + (sum_list tail)

The type of the head is tree, but the type of the tail is tree list. So they can't both be a proper argument for the sum_list function. That's what the compiler is telling you.

Later in your code you also apply sum_list to a list of ints.

OCaml is a strongly typed language. You can't have a function that accepts an argument of different types (tree, tree list, int list). You most likely need three different functions, one for each type.

Your definition of tree is OK (though it's risky to redefine [] since you might need it elsewhere in your code with its usual type).

Upvotes: 6

Related Questions