2
\$\begingroup\$

I've created the following implementation of a trie in F# as an effort to learn the language. I would like to know what could be done to make it more idiomatic. Any other pointers are welcome as well.

Of particular interest are:

  • Are my tests sufficient? Is there a better way to construct the tests?
  • Can the logic for insert be made cleaner?
  • To constrain type or not for functions and parameters?
  • What remains to be done to classify this as a proper collection?
type Trie<'T when 'T : comparison> = {
    IsTerminal: bool;
    Children: Map<'T, Trie<'T>>;
}

module Trie =
    let empty = {
        IsTerminal = false;
        Children = Map.empty;
    }

    let rec insert branch trie =
        match branch with
        | [] ->
            { trie with IsTerminal = true; }
        | el::els ->
            let child = 
                match Map.tryFind el trie.Children with
                | Some t -> t
                | None -> empty
            let child' = insert els child
            let children =
                if Map.containsKey el trie.Children
                then Map.remove el trie.Children
                else trie.Children
            let children' = Map.add el child' children
            { trie with Children = children' }

    let rec contains branch trie =
        match branch with
        | [] -> trie.IsTerminal
        | el::els ->
            match Map.tryFind el trie.Children with
            | Some t -> contains els t
            | None -> false

    let rec toSeq trie =
        seq {
            for KeyValue(label, trie) in trie.Children do
                if trie.IsTerminal then yield [label]
                let children = toSeq trie
                for child in children do
                    yield label :: child
        }

    module Test =
        let ``insert can insert char into root`` =
            let result = empty |> insert ['a']
            Map.containsKey 'a' result.Children
        do assert ``insert can insert char into root``

        let ``insert can insert char into multiple levels`` =
            let result = empty |> insert ['a'..'d']
            Map.containsKey 'd' (((result.Children |> Map.find 'a').Children |> Map.find 'b').Children |> Map.find 'c').Children
        do assert ``insert can insert char into multiple levels``

        let ``contains finds branches that exist in tree`` =
            let result = empty |> insert ['a'..'d']
            contains ['a'..'d'] result
        do assert ``contains finds branches that exist in tree``

        let ``contains does not find incomplete branches`` =
            let result = empty |> insert ['a'..'d']
            result |> contains ['a'..'c'] |> not
        do assert ``contains does not find incomplete branches``

        let ``contains does not find extended branches`` =
            let result = empty |> insert ['a'..'d']
            result |> contains ['a'..'e'] |> not
        do assert ``contains does not find extended branches``
\$\endgroup\$
8
  • \$\begingroup\$ module for tests it makes sense to put separately \$\endgroup\$
    – user110704
    Nov 5, 2016 at 13:03
  • 1
    \$\begingroup\$ Since posting this, I've tried searching for other f# implementation of trie and I'm honestly proud of this code. I hope to get more feedback. \$\endgroup\$
    – psaxton
    Nov 5, 2016 at 22:14
  • \$\begingroup\$ @psaxton: Just a question: what's the purpose with inserting a branch to a Trie? If for instance inserting ´["A";"to";"tea";"ted";"ten";"i";"in";"inn"]´ shouldn't it be "Trieed" it self? \$\endgroup\$
    – user73941
    Nov 7, 2016 at 16:50
  • \$\begingroup\$ branch is a poor name choice. I'm trying to keep this implementation generic. If the consumer intends to store individual words (i.e. autocomplete), they would pass in a char array. If a consumer intends to store sentences or phrases (i.e. Markov chain) they could pass in a string array. If the consumer is intending to store bytes (i.e. compression dictionary) they could pass in a byte array. I'm not certain what to call the path in the trie which the inserted array creates, so I chose branch. Suggestions are quite welcome. I'm not fond of el::els either. \$\endgroup\$
    – psaxton
    Nov 7, 2016 at 17:17
  • \$\begingroup\$ @HenrikHansen I've also placed an updated version in a Github gist where I changed from insert to add to feel more like the other collection types \$\endgroup\$
    – psaxton
    Nov 7, 2016 at 18:38

2 Answers 2

2
\$\begingroup\$

Looks good! Just a few notes:

Can the logic for insert be made cleaner?

It's very good already. "helper functions" would make it easier to understand and refactor. Something like:

let removeChild el children = 
    if Map.containsKey el children
    then Map.remove el children
    else children

let findChild el children = // left as an exercise :)

let rec insert branch trie =
    match branch with
    | [] ->
        { trie with IsTerminal = true; }
    | el::els ->
        let child = findChild el trie.Children
        let child' = insert els child
        let children = removeChild el trie.Children
        let children' = Map.add el child' children
        { trie with Children = children' }

Then you can use the pipe |> operator to refactor the insert to:

    | el::els ->
        let child' = trie.Children |> findChild el  |> insert els
        let children' = trie.Children |> removeChild el |> Map.add el child'
        { trie with Children = children' }

Also if you analyze removeChild, you'll realize it can be refactored to just one line

let removeChild = Map.remove

What remains to be done to classify this as a proper collection?

A bit more. You can discover them by refactoring your tests. For example:

module Trie = 
    let fromSeq s = insert s empty
    let containsKey key trie = // todo

module Test = 
    let ``insert can insert char into root`` =
        let result = Trie.fromSeq ['a']
        result |> Trie.containsKey 'a'
    do assert ``insert can insert char into root``
\$\endgroup\$
3
\$\begingroup\$

There are several libraries for writing unit tests in F#. For example:

The logic is pretty clear, but there are a couple of comments

1. Instead of:

        let child = 
            match Map.tryFind el trie.Children with
            | Some t -> t
            | None -> empty

you can rewrite this code with using defaultArg

        let child = 
            Map.tryFind el trie.Children
            |> defaultArg  <| empty

2. You can use functions from a module Option, so..instead:

        match Map.tryFind el trie.Children with
        | Some t -> contains els t
        | None -> false

better:

        Map.tryFind el trie.Children
        |> Option.exists (contains els)
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the review. I've implemented the changes in a gist and found ways to clean up some other pieces, such as the child -> child' assignments. I'm researching the collection types and will post another review after I feel I have made this feel more like the base collections. \$\endgroup\$
    – psaxton
    Nov 7, 2016 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.