Convert tree to list

Question

How can I convert a tree to a list: So far I have the following code but its giving several issues:

type 'a tree = Lf | Br of 'a * 'a tree * 'a tree;;

let rec elementRight xs = function
  | LF ->false
  | Br(m,t1,t2) -> if elementRight xs t1 = false then t1::xs else element xs t1;; //cannot find element
let rec elementLeft xs = function
  | LF ->false
  | Br(m,t1,t2) -> if elementLeft xs t2 = false then t2::xs else element xs t2 ;; //cannot find element
let rec element xs = function
  | LF ->[]
  | Br(m,t1,t2) -> xs::(elementRight xs t1)::(elementRight xs t2)::(elementLeft xs t1)::(elementLeft xs t2);;

Answer 1

There are a number of problems with your code:

1. You shouldn't have ;; at the end of lines (I'm guessing this means you're copy and pasting into the repl, you should really use an fsx file instead and use "send to repl").

2. This: | LF ->false is returning a bool, while this: | Br(m,t1,t2) -> if elementRight xs t1 = false then t1::xs else element xs t1 is returning an 'a list. An expression can only have one type, so returning two is a compile error. I'm guessing what you really are meaning to do is have the leaf return [] and then check for empty list in your branch case something like this:

let rec elementRight xs = function
  | LF ->[]
  | Br(m,t1,t2) -> if elementRight xs t1 = List.empty then t1::xs else element xs t1

3 . when using mutually recursive functions you need to use the and keyword for all declarations but the first like this:

let rec elementRight xs = function
  ...
and elementLeft xs = function
  ...
and element xs = function
  ...