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