Extracting leaf paths from an n-ary tree in F #

Question

Inspired by this question , I wanted to try my hand at the latest to ponder this problem using F #

My approach is probably completely disabled, but in the process of solving this problem, I try to get a list of all permutations of digits 0-9.

I look at his solution using n-ary tree:

type Node = | Branch of (int * Node list) | Leaf of int 

I am very pleased with myself because I managed to figure out how to generate the tree I want.

Now my problem is that I cannot decide how to go through this tree and extract the "path" to each sheet as an int. The thing that confuses me is that I need to map individual nodes, but my “external” function must accept a Node list.

My current attempt is almost the right thing, except that it returns me the sum of all the paths ...

 let test = Branch(3, [Branch(2, [Leaf(1)]);Branch(1, [Leaf(2)])]) let rec visitor lst acc = let inner n = match n with | Leaf(h) -> acc * 10 + h | Branch(h, t) -> visitor t (acc * 10 + h) List.map inner lst |> List.sum visitor [test] 0 //-> gives 633 (which is 321 + 312) 

And I'm not even sure if this is tail-recursive.

(You can suggest another solution for finding permutations, but I'm still interested in solving this particular problem)

EDIT: I published a general permutation algorithm in F # here .

Answer 1

regarding your question about traversing a list - you can start by writing a function that returns lists that represent the path, which I find easier, and later it will be easy to turn it into a function that returns a number.

This one takes the list as the first argument (the path so far) and the tree and returns the list> type - these are all possible paths from the current branch.

 let rec visitor lst tree = match tree with | Branch(n, sub) -> List.collect (visitor (n::lst)) sub | Leaf(n) -> [List.rev (n::lst)] // For example... > let tr = Branch(1, [Leaf(3); Branch(2, [Leaf(4); Leaf(5)] )]);; > visitor [] tr;; val it : int list list = [[1; 3]; [1; 2; 4]; [1; 2; 5]] 

In the case of "Sheet", we simply add the current number to the list and return the result as a list containing one list (we must cancel it first, because we added the numbers to the beginning). In the case of "Branch", we add "n" to the list and recursively call the visitor to process all the sub-nodes of the current branch. This returns a list of lists, and we use "map_concat" to turn them into a single list containing all possible paths from the current branch.

Now you can rewrite this to return a list of integers:

 let rec visitor2 lst tree = match tree with | Branch(n, sub) -> List.collect (visitor2 (lst * 10 + n)) sub | Leaf(n) -> [lst * 10 + n] // For example... > visitor2 0 tr;; val it : int list = [13; 124; 125] 

Instead of concatenating lists, we calculate a number.

Answer 2

Regarding laziness - you can make it lazy by using the F # type "seq" instead of the "list" type. Here is an example:

 let rec visitor2 lst tree = match tree with | Branch(n, sub) -> Seq.map_concat (visitor2 (lst * 10 + n)) sub | Leaf(n) -> seq { do printfn "--yielding: %d" (lst * 10 + n) yield lst * 10 + n };; 

"seq" is a sequence expression that is a lazy stream of values. I added "printfn" to the code, so we can track how things work:

 > visitor2 0 tr |> Seq.take 2;; --yielding: 13 --yielding: 124 val it : seq<int> = seq [13; 124] 

Perhaps you can use something like Seq.first to find the first value that represents the result.