Use fold to Convert a tree to a list

Learning
1

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!

2

The problem is on the next line. You have

(myleft_tree:list)

But what is this a list of?

3

@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.

4

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

5

@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
6

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
7

@rdavison
Thank you Richard. I appreciate your help!

1 Like