F#unctional不变Trie (前缀树)

Question

为了学习该语言，我在F#中创建了trie的以下实现。我想知道怎样才能使它变得更地道。任何其他指针也是受欢迎的。

特别令人感兴趣的是：

• 我的测试足够了吗？有更好的方法来构造测试吗？
• 插入的逻辑能变得更清晰吗？
• 是否约束函数和参数的类型？
• 还需要做些什么才能将其归类为一个适当的收藏？

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``

Answer 1

看起来不错！只是几个音符：

插入的逻辑能变得更清晰吗？

已经很好了。“助手函数”将使您更容易理解和重构。类似于：

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' }

然后可以使用管道|>操作符重构insert以：

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

另外，如果您分析removeChild，您就会发现它可以重构为一行

let removeChild = Map.remove

还需要做些什么才能将其归类为一个适当的收藏？

再多一点。您可以通过重构测试来发现它们。例如：

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``

Answer 2

有几个用F#编写单元测试的库。例如：

• FsUnit
• 取消报价
• 福初

逻辑很清楚，但有几点评论

1. 而不是：

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

您可以使用defaultArg重写此代码

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

1. 您可以使用来自模块选项，so..instead的函数：

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

更好的是：

        Map.tryFind el trie.Children
        |> Option.exists (contains els)