1

我正在尝试使用一种计算每个节点高度的方法在 F# 中实现一个 trie 结构。

到目前为止，这是我想出的：

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")

现在我正在尝试编写我的高度计算功能。如果这是一棵二叉树，这将很容易编写，但是在这棵树中，每个节点都有一个子节点列表，所以我不知道如何在 F# 中反复遍历该事物。

这是我到目前为止使用列表折叠操作提出的，但它没有编译：

 module NodeFunctions = 
    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

有什么想法可以重写此函数以使其工作吗？或者关于如何实现我的目标的任何想法如果这不是正确的想法？

先感谢您

4

4 回答 4

2

这是一个更实用的代码布局。与您的代码相同的逻辑。我正在研究一个可行的解决方案。

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)

打印高度。

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)
于 2011-02-18T03:34:33.850 回答
2

您的代码似乎几乎是正确的。以下为我编译（我没有尝试运行它，因为创建trie值时出现异常，但递归方案听起来正确）：

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

我所做的改变：

  • 你写nextLevel(...) = function ...的。该function构造创建了一个函数，该函数采用一些值和模式匹配（因此您编写了带有两个TrieNode参数的函数）。我用 simple 替换了它match。

  • 在你的 lambda 中let res = nextLevel(node,curlevel+1) and-and关键字不属于那里（你可以写let res = .. in，但由于缩进不是必需的）。

  • 您的 lambda 函数使用模式匹配来提取元组的元素(node:TrieNode,_,_)，但subnodes不是元组列表 - 只是TrieNode值列表。

于 2011-02-18T00:48:01.653 回答
1

再考虑一下 Trie，您的初始方法很接近，但要求所有内容都以相同的字母开头。这是一个使用像你原来的想法一样的字符而不是字符串的工作尝试。我把它留给读者作为实现字符串节点和叶子的练习。

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

还有一些测试

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

输出

7
abc
abc132d
abc123d
abcd
abcde
abcdef
ab123cd
于 2011-02-18T06:13:34.353 回答
1

我会采取不同的方法：

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

对我来说，这比使用 fold 的版本更容易阅读，尽管它确实遍历了两次子节点列表。

于 2011-02-18T02:35:02.523 回答