реализация попытки новичка F # пошла не так

Я пытаюсь реализовать структуру данных 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. Как заставить функцию вставки слова возвращать список объектов TrieNode, чтобы мне не приходилось заключать вызов в квадратные скобки ("[","]"). . Я думаю, что это ошибка.
3. Любые другие советы, которые вы можете дать мне по реализации этой структуры данных в F#, приветствуются. Я знаю, что, должно быть, делаю много вещей неправильно, так как я новичок в этом языке. Я знаю, например, что функция вставки слов несовершенна, потому что она не проверяет, пуст ли список или нет, поэтому он заканчивается преждевременно. Я хотел пересечь этот мост, когда доберусь до него.

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

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


f# trie
person Para    schedule 15.02.2011    source источник
comment
Не хотел редактировать, не убедившись - вы имеете в виду Дерево, верно? Расширение списка и бинарное дерево?   -  person Ramon Snir    schedule 15.02.2011
comment
значение trie в конце оказывается типа (Trie -> Trie) — что наводит меня на мысль, что оно частично оценивает insertWord   -  person Jimmy    schedule 16.02.2011
comment
попробуйте, как в префиксном дереве, а не в дереве, как в обычном дереве   -  person Para    schedule 16.02.2011

Ответы (2)


arrow_upward
4
arrow_downward

  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. Есть несколько проблем. Вот несколько для начала:

    • Try to avoid using Head, particularly since you don't always know that your lists are non-empty when you're calling it.
    • Когда вы вставляете слово в пустой Trie, вы отбрасываете все символы, кроме первого! Точно так же вам нужно пересмотреть и свои рекурсивные вызовы.
    • Что еще более важно, у вашего типа TrieNode есть небольшая проблема. Можете ли вы записать получившееся дерево, которое, как вы ожидаете, содержит только два слова "in" и "to"?
person kvb    schedule 15.02.2011
comment
спасибо за ваш ответ, но что касается пункта № 2, списки синглетонов - это именно то, чего я хочу избежать, чего я не знаю, так это того, как их избежать. Вместо этого я хочу настоящие списки - person Para; 16.02.2011
comment
@Para - если вы решите проблемы в пункте 3, пункт 2 должен позаботиться о себе сам, но я все равно добавил еще несколько мыслей. Попробуйте пройтись по нескольким очень простым примерам на бумаге. - person kvb; 16.02.2011

arrow_upward
1
arrow_downward

Что касается вашего первого вопроса, как сказал @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

person Alex    schedule 16.02.2011