Extracting Leaf paths from n-ary tree in F#

Question

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

My approach is probably completely off course, but in the course of solving this problem, I'm trying to get a list of all the permutations of the digits 0-9.

I'm looking at solving it using a n-ary tree like so:

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

I'm quite pleased with myself, because I've managed to work out how to generate the tree that I want.

My problem now is that I can't work out how to traverse this tree and extract the 'path' to each leaf as an int. Thing thing that is confusing me is that I need to match on individual Nodes, but my 'outer' function needs to take a Node list.

My current attempt almost does 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 that this is tail-recursive.

(You're quite welcome to propose another solution for finding permutations, but I'm still interested in the solution to this particular problem)

EDIT: I've posted a generic permutations algorithm in F# here.

Answer 1

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

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

let rec visitor lst tree = 
  match tree with
  | Branch(n, sub) -> List.map_concat (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 'Leaf' case, we simply add the current number to the list and return the result as a list containing single list (we have to reverse it first, because we were adding numbers to the beginning). In the 'Branch' case, we add 'n' to the list and recursively call the visitor to process all the sub-nodes of the current branch. This returns a bunch of lists and we use 'map_concat' to turn them into a single list that contains all posble 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.map_concat (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 now calculate the number.

T.

Answer 2

Regarding laziness - You can make this lazy by using F# "seq" type instead of "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 };;

The "seq" thing is a sequence expression, which represents a lazy stream of values. I added "printfn" to the code, so we can track how things are executing:

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

You can probably use something like Seq.first to find the first value which represents the result.