# Use fold to Convert a tree to a list

Hello,
I am using a tree fold function as below to convert my tree into a list:

`````` let rec btfold acc f tree =
match tree with
| Empty -> acc
| Node(lt, x, rt) -> f (btfold acc f lt) x (btfold acc f rt)
``````

and when I implement my function:

`````` let btf_to_list mytree =
let acc = [] in
let f (myleft_tree:list) (x:'a) (myright_tree:list) = [x]::((myleft_tree) @ (myright_tree))
in btfold acc f mytree
``````

I got an error message on the line “let acc = [] in…” that

Error: The type constructor list expects 1 argument(s),
but is here applied to 0 argument(s)

Why is this?

Thank you!

The problem is on the next line. You have

(myleft_tree:list)

But what is this a list of?

@rdavison
Hi,
I am not sure Richard.
If I use recursion, it is very easy to understand:

`````` let rec bt_to_list mytree = match mytree with
|Empty -> []
|Node(lt,x,rt) -> List.rev ([x]:: (bt_to_list lt)) @ (bt_to_list rt)
``````

But here using btfold, I am confused how to implement fold. Ok. My base case is an empty list. I get that. Otherwise, I want to put element x in to my accumulator (acc) and then go to left tree, do the same thing and then go to the right tree, do the same thing.
While I am writing this post, I am thinking that myleft_tree should be a tree instead of a list.

I guess what I mean is that the error that you are getting has to do with the fact that you’re not specifying the complete type.

Example showing your error

let f (x:list) = [];;
Error: The type constructor list expects 1 argument(s),
but is here applied to 0 argument(s)

vs.

let f (x:'a list) = [];;
val f : 'a list -> 'b list = < fun >

The difference being that in the bottom example, the list is of type `'a list`

@rdavison
Hi Richard,
even when I fixed that:

``````let f (myleft_tree:'a list) (x:'a) (myright_tree:'a list) = ([x]::(myleft_tree)) @ (myright_tree)
``````

I have a new error:

`````` Error: This expression has type 'a list but an expression was expected of type
'a list list
The type variable 'a occurs inside 'a list``````

Sure. What it’s telling you is that the code that you have written is creating a value of type `'a list list` but the compiler was expecting the type to be `'a list`. I suspect the problem has to do with this

`([x]::(myleft_tree))`

because you’re saying “put a list with an x in it into a list called ‘myleft_tree’”, thereby creating a list of lists

Probably what you meant to do is

`(x::myleft_tree)`

1 Like

@rdavison
Thank you Richard. I appreciate your help!

1 Like