Convert Tree to List-CodePudding

everyone! I have a list type:

type ConsList<'value> =
    | Cons of head: 'value * tail: ConsList<'value>
    | Empty

And a tree type:

type Tree<'value> =
    | Node of value: 'value * children: ConsList<Tree<'value>>
    | Leaf of value: 'value

I would like a function that could collect all values in nodes and leaves of a Tree and convert them into a ConsList in order starting from the root and following from left to right.

For example, if I have: Node(1, Cons(Leaf 2, Cons(Leaf 3, Empty)))

Then I expect the output to be: Cons(1, Cons(2, Cons(3, Empty)))

I have fold-functions, if they can be useful:

let rec fold folder acc lst =
    let f = fold folder

    match lst with
    | Empty -> acc
    | Cons (hd, tl) -> f (folder acc hd) tl

let rec fold folder acc tree =
    let f = fold folder

    match tree with
    | Leaf value -> folder acc value
    | Node(value, children) -> ConsList.fold f (folder acc value) children

CodePudding user response：

Use the tree fold to build up a list of values. Something like this:

Tree.fold (fun currentStateOfList value ->
    // add value to currentStateOfList here
    ) initialStateOfList aTree

You need to figure out:

What is the initial state of the list?
What should be done to add a value to the current state of the list?

Depending on the requirements, you might also have to reverse the order of the list at the end.