F# compute height of a trie node

I am trying to implement a trie structure in F# with a method to compute the height of every node.

This is what I came up with so far:

type TrieNode =
    | SubNodes of char * bool * TrieNode list
    | Nil
    member this.Char = match this with | Nil -> ' '
                                       | SubNodes(c,weh,subnodes) -> c
    member this.GetChild(c:char) = match this with  | Nil -> []
                                                    | SubNodes(c,weh,subnodes) -> if subnodes.Length > 0 then [ (List.filter(fun (this:TrieNode) -> this.Char = c) subnodes).Head ] else []

    member this.AWordEndsHere = match this with | Nil -> false
                                                | SubNodes(c,weh,subnodes) -> weh          

module TrieFunctions = 
    let rec insertWord (wordChars:char list) = function
        | Nil -> SubNodes(' ', false, (insertWord wordChars Nil)::[])
        //daca aici inca nu e cel putin un nod atunci fa nodul radacina standard adica nodul care nu e sfarsit de cuvant si
        //are caracterul ' ' si incepe sa ii construiesti lui subnodurile
        | SubNodes(c, weh, subnodes) as node ->

            if(wordChars.Length = 1) then
                SubNodes(wordChars.Head,true,[])
            else
                let child = node.GetChild(wordChars.Head)
                if child = [] then 
                    SubNodes(wordChars.Head,false,(insertWord wordChars.Tail node)::subnodes )
                else
                    SubNodes(wordChars.Head,false,(insertWord wordChars.Tail child.Head)::subnodes )
    let stringToCharList(s:string) = List.ofSeq s 


type Trie(inner : TrieNode) =
    member this.InsertWord(wordChars:char list) = Trie(TrieFunctions.insertWord wordChars inner)
    member this.InsertWord(str:string) = Trie(TrieFunctions.insertWord (TrieFunctions.stringToCharList str) inner)


  let trie = Trie(SubNodes(' ',false,List.empty))
                .InsertWord("abc")
                .InsertWord("abcd")
                .InsertWord("abcd")
                .InsertWord("abcde")
                .InsertWord("abcdef")
                .InsertWord("ab123cd")
                .InsertWord("abc123d")
                .InsertWord("abc132d")

Now I am trying to write my height computing function. This would be very easy to write if this were a binary tree but in this tree each node has a list of subnodes so I don't know how to recurrently traverse the thing in F#.

This is what I came up with so far using the list fold operation but it doesn't compile:

 module NodeFunc开发者_开发百科tions = 
    let rec nextLevel(node:TrieNode,curlevel:int) = function
                        | Nil -> curlevel
                        | SubNodes(_,_,subnodes) -> 
                            List.fold (fun acc (node:TrieNode,_,_) -> let res = nextLevel(node,curlevel+1) and 
                                                                      if( acc > res) then acc else res) curlevel subnodes

Any ideas how I might rewrite this function to make it work? Or any ideas about how else to achieve my goal should this not be the right idea?

Thank you in advance

Your code seems to be almost correct. The following compiles for me (I didn't try running it, because I get an exception when creating the trie value, but the recursive scheme sounds right):

let rec nextLevel(node:TrieNode,curlevel:int) = 
  match node with
  | Nil -> curlevel
  | SubNodes(_,_,subnodes) -> 
      List.fold (fun acc (node:TrieNode) -> 
        let res = nextLevel(node,curlevel+1) 
        if (acc > res) then acc else res) curlevel subnodes

The changes I did:

• You wrote nextLevel(...) = function .... The function construct creates a function taking some value and pattern matching on it (so you wrote function taking two TrieNode arguments). I replaced this with simple match.

• In your lambda you had let res = nextLevel(node,curlevel+1) and - the and keyword doesn't belong there (you could write let res = .. in but it is not necessary because of the indentation).

• Your lambda function used pattern matching to extract element of a tuple (node:TrieNode,_,_), but subnodes isn't a list of tuples - just list of TrieNode values.

Here's a more functional code layout. Same logic as your code. I'm working on a working solution.

module Trie = 
    type Node = Node of (char * bool * Node list) Option

    let char = function
        | Node(None) -> ' '
        | Node(Some(c, _, _)) -> c

    let getChild (c:char) = function
        | Node(None) -> None
        | Node(Some(c, weh, subnodes)) -> 
            List.tryFind (fun (node:Node) -> (char node) = c) subnodes

    let rec insertWordChars (wordChars:char list) = function
        | Node(None) -> Node(Some(wordChars.Head, false, [insertWordChars wordChars.Tail (Node(None))]))
        | Node(Some(c, weh, subnodes)) as node ->
            if wordChars.Length = 1 then
                Node(Some(wordChars.Head, true, []))
            else
                match getChild (wordChars.Head) node with
                | None -> Node(Some(wordChars.Head, false, (insertWordChars wordChars.Tail node)::subnodes))
                | Some(child) -> Node(Some(wordChars.Head, false, (insertWordChars wordChars.Tail child)::subnodes))

    let insertWord (s:string) = insertWordChars (List.ofSeq s)

Print height.

let rec nextLevel (curlevel:int) = function
    | Trie.Node(None) -> curlevel
    | Trie.Node(Some(_, _, subnodes)) -> 
        List.fold (fun acc (node:Trie.Node) -> 
            let res = nextLevel (curlevel + 1) node
            if (acc > res) then acc else res) curlevel subnodes

let trie = 
    Trie.Node(Some(' ', false, []))
    |> Trie.insertWord("abc")
    |> Trie.insertWord("abcd")
    |> Trie.insertWord("abcd")
    |> Trie.insertWord("abcde")
    |> Trie.insertWord("abcdef")
    |> Trie.insertWord("ab123cd")
    |> Trie.insertWord("abc123d")
    |> Trie.insertWord("abc132d")

printf "%A" (nextLevel 0 trie)

Thinking about the Trie some more your initial approach was close but required everything to start with the same letter. Here's a working trie that uses chars like your original idea and not strings. I leave it up to the reader as an exercise to implement string nodes and leafs.

module Trie = 
    type Node = Node of (char * bool * Node) list

    let empty = Node([])

    let partition c = function
        | Node(nodes) -> List.partition (fun (ct, _, _) -> ct = c) nodes

    let rec insert wordChars node = 
        match wordChars, node with
        | c::cx, Node([]) -> Node([c, cx.IsEmpty, (insert cx empty)])
        | c::cx, _ -> 
            match partition c node with
            | (ct, weh, children)::_, others -> 
                Node((c, (weh || cx.IsEmpty), insert cx children)::others)
            | [] , others -> 
                Node((c, cx.IsEmpty, insert cx empty)::others)
        | [], _ -> node

    let insertWord (s:string) node = insert (List.ofSeq s) node

And some Test

let rec nextLevel (curlevel:int) = function
    | Trie.Node([]) -> curlevel
    | Trie.Node(nodes) -> 
        List.fold (fun acc (_, _, node) -> 
            let res = nextLevel (curlevel + 1) node
            if (acc > res) then acc else res) curlevel nodes

let rec print acc = function
    | Trie.Node(nodes) -> 
        List.iter (fun (c, w, node) ->
            let str = acc + c.ToString()
            if w then printfn "%s" str
            print str node) nodes

let trie = 
    Trie.empty
    |> Trie.insertWord("abc")
    |> Trie.insertWord("abcd")
    |> Trie.insertWord("abcd")
    |> Trie.insertWord("abcde")
    |> Trie.insertWord("abcdef")
    |> Trie.insertWord("ab123cd")
    |> Trie.insertWord("abc123d")
    |> Trie.insertWord("abc132d")

printf "%d\n" (nextLevel 0 trie)

print "" trie

Output

7
abc
abc132d
abc123d
abcd
abcde
abcdef
ab123cd

I'd take a different approach:

let rec depth = function
| Nil -> 0
| SubNodes(_,_,l) ->
    let d = l |> List.map depth |> List.max
    d + 1

To me, this is much easier to read than a version using fold, though it does traverse the list of subnodes twice.