новичок F # три реализации не так - PullRequest
Новая
       23

новичок F # три реализации не так

4 голосов
/ 15 февраля 2011

Я пытаюсь реализовать структуру данных Trie в 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) ->[ (List.filter(fun (this:TrieNode) -> this.Char = c) subnodes).Head ]

    member this.AWordEndsHere = match this with | Nil -> false
                                                | SubNodes(c,weh,subnodes) -> weh
module TrieFunctions = 
    let rec insertWord (wordChars:char list) = function
        | Nil -> SubNodes(wordChars.Head, false, [])
        | SubNodes(c, weh, subnodes) as node ->
            let child = node.GetChild(wordChars.Head)
            if child = [] then 
                SubNodes(wordChars.Head,false,[insertWord wordChars.Tail node])
            else
                SubNodes(wordChars.Head,false,[insertWord wordChars.Tail child.Head])


type Trie(inner : TrieNode) =

    member this.InsertWord(wordChars:char list) = TrieFunctions.insertWord(wordChars)


  let trie = Trie(SubNodes(' ',false,List.empty)).InsertWord(['g';'i';'g';'i'])

Итак, мои вопросы:
1. как получить отладочный доступ к функции insertWord? Почему я не получаю это сейчас? Почему я не вижу ошибки?
2. Как я могу заставить функцию insert word возвращать список объектов TrieNode, чтобы мне не пришлось заключать вызов в квадратные скобки ("[", "]"). Я думаю, что это ошибка.
3. Любой другой совет, который вы можете дать мне по реализации этой структуры данных в F #, приветствуется. Я знаю, что, должно быть, я делаю много неправильных вещей, поскольку я очень плохо знаком с этим языком. Например, я знаю, что функция вставки слов некорректна, потому что она не проверяет, пуст ли список или нет, поэтому преждевременно заканчивается. Я хотел пересечь этот мост, когда добрался до него.

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

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

Ответы [ 2 ]

4 голосов
/ 16 февраля 2011

  1. Возможно, вы не можете активировать свою точку останова, потому что вы не применяете полностью insertWords: она принимает два параметра карри, но вы передаете только один аргумент wordChars. Возможно, вы хотели определить ваш Trie тип, как это вместо этого? 

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

  2. Ну, вы могли бы обернуть все свои возвращаемые значения в [], чтобы сделать их одноэлементными списками, а затем не оборачивать рекурсивные вызовы insertWords. Однако, похоже, что с вашим алгоритмом что-то не так (так или иначе), поскольку вы получаете только одноэлементные списки ...

    Обратите внимание, что на данный момент вы полностью отбрасываете существующий список subnodes - если вы хотите добавить его в начало, используйте вместо него (insertWord wordChards.Tail node)::subnodes. Однако иногда вам нужно заменить существующую запись, а не добавить новую, что потребует дополнительных усилий.

  3. Есть несколько проблем. Вот несколько примеров, с которых можно начать:

    • Старайтесь избегать использования Head, тем более что вы не всегда знаете, что ваши списки не пусты при вызове.
    • Когда вы вставляете слово в пустой Trie, вы отбрасываете все символы, кроме первого! Точно так же вам нужно пересмотреть ваши рекурсивные вызовы.
    • Что еще более важно, ваш тип TrieNode имеет небольшую проблему. Можете ли вы выписать результирующее дерево, которое вы ожидаете увидеть, которое просто содержит два слова "in" и "to"?
1 голос
/ 16 февраля 2011

Относительно вашего первого вопроса, как сказал @kvb, вы частично применяете insertWord. При его определении вы указываете явный аргумент wordChars и, используя конструкцию function для сопоставления с образцом, вы в основном добавляете второй параметр типа TrieNode, чтобы ваша функция получала следующую подпись: 

insertWord : char list -> TrieNode -> TrieNode

Поскольку при вызове InsertWord (который является просто оболочкой для insertWord), вы предоставляете только один аргумент (список символов), функция не будет вызвана, но вы получите функцию, ожидающую TrieNode назад. Подпись InsertWord ясно показывает: 

InsertWord : wordChars:char list -> (TrieNode -> TrieNode)

Обратите внимание на круглые скобки.

Вы, вероятно, захотите указать Nil в вашем случае, так как концептуально вы расширяете пустое дерево: 

let trie = Trie(SubNodes(' ',false,List.empty)).InsertWord(['g';'i';'g';'i']) Nil

Пример реализации структуры дерева вы найдете здесь: http://lepensemoi.free.fr/index.php/2009/10/15/trie-and-anagrams-with-f

...