F # вычислить высоту узла

Question

Я пытаюсь реализовать структуру Frie в F # с методом для вычисления высоты каждого узла.

Это то, что я до сих пор придумал:

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

Есть идеи, как мне переписать эту функцию, чтобы она работала? Или какие-либо идеи о том, как еще достичь моей цели, если это не будет правильной идеей?

Заранее спасибо

Answer 1

Вот более функциональная раскладка кода. Та же логика, что и у вашего кода. Я работаю над рабочим решением.

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)

Answer 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).Я заменил это на простой match.

• В вашей лямбде у вас было let res = nextLevel(node,curlevel+1) and - ключевое слово and там не принадлежит (вы могли бы написать let res = .. in, но этоне требуется из-за отступа).

• Ваша лямбда-функция использовала сопоставление с шаблоном для извлечения элемента кортежа (node:TrieNode,_,_), но subnodes не является списком кортежей - просто списокTrieNode значений.

Answer 3

Думая о Три еще, ваш первоначальный подход был близок, но требовал, чтобы все начиналось с одной и той же буквы.Вот рабочая три, которая использует символы, как ваша оригинальная идея, а не строки.Я оставляю это на усмотрение читателя в качестве упражнения для реализации строковых узлов и листьев.

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

Answer 4

Я бы выбрал другой подход:

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

На мой взгляд, это намного проще для чтения, чем версия, использующая свертывание, хотя она дважды просматривает список подузлов.