F# Finding paths in an n-ary tree

Question

Given this tree type:

type T<'a> = N of 'a * T<'a> list

which could be declared as:

let ta = N("b", [N("c", [])])

How would I get all the possible paths in this tree? I've tried by applying the method mentioned in this post, but it just returns an empty list. This is how I've implemented it:

let rec isPath is t = 
    match t with
    | N(x, t) -> List.collect (isPath (x::is)) t

isPath [] ta |> (printf "isPath: %A")

but it only returns isPath: []. What am I doing wrong? My secondary goal would then be to make a second function where I can pass a list of ints to check if there are any paths that correspond to this list.

score 3 · Accepted Answer · answered May 20 '17 at 16:38

You need another match condition that catches empty lists and doesn't iterate through them. Right now your List.collect, when t is empty, is iterating through an empty list and is therefore returning an empty list to the "previous" level of your recursive function. Which is then appending all those empty lists together to get... an empty list, and so on.

Add the following match case and you should get what you need:

| N(x, []) -> is

Note that this should come before your other match case in order to work: since F# processes match cases from top to bottom, N(x, t) will match anything, and N(x, []) won't ever be checked if it's second.

So you want your function to look like:

let rec isPath is t = 
    match t with
    | N(x, []) -> is
    | N(x, t) -> List.collect (isPath (x::is)) t

Again, if you don't see why this works, let me know and I'll explain further.

F# Finding paths in an n-ary tree

1 Answers1