Recursion in Go

Question

Я разработчик Javascript по профессии и решил дать вращаться. В качестве учебного упражнения я решил перенести функцию в один из моих проектов узлов, но не могу заставить ее работать для меня. Целью функции является отображение всех допустимых английских слов, которые могут быть сделаны из букв, представленных другим словом (я создаю многопользовательскую версию Text Twist). Например, findAllWords («танцы») вернется ['can', 'scan', 'dance', 'dances' и т. Д.]. Я достиг этого, перейдя на три, построенный из английского списка слов.

Вот реализация функция в Javascript:

self.findAllWords = function(letters = [], trie = dictionary, curString = '') { 
    let words = []; 
    letters = typeof letters === 'string' ? letters.split('') : letters; 
    letters.forEach((letter,i,ar) => { 
     if (!trie[letter]) return; 
     let curWord = curString + letter; 
     let newTrie = trie[letter]; 
     let newLetters = [...ar.slice(0,i),...ar.slice(i+1)]; 
     if (trie[letter][FLAG_INDEX]) words.push(curWord); 
     if (self.isValidPrefix(curWord, dictionary)) words = [...words,...self.findAllWords(newLetters,newTrie,curWord)]; 
    }); 
    return uniq(words); 
} 

и вот моя попытка тиражирования его в Go (с помощью реализации this TRIE):

func FindAllWords(letters []rune, node *Node, curString string) []string { 

words := []string{} 
for i, let := range letters { 
    n, ok := node.Children()[let] 

    if !ok { 
     return words 
    } 
    curWord := curString + string(n.val) 
    newLetters := []rune{} 
    newLetters = append(newLetters, letters[:i]...) 
    newLetters = append(newLetters, letters[i+1:]...) 

    if n.term { 
     words = append(words, curWord) 
    } 

    words = append(words, FindAllWords(newLetters, n, curWord)...) 
} 
return words 
} 

Очень хотелось бы знать, почему это провал , как я могу заставить его работать, и любые соглашения, которые я злоупотребляю/не использую. Благодаря!

Answer 1

Это может быть или не быть единственной проблемой с кодом Go, но оператор return в цикле for не делает то же самое, что и оператор return в javascript forEach.

Возврат внутри анонимной функции в коде javascript возвращается с анонимной функции с точностью до функции findAllWords. Возврат в цикле Go for возвращается с FindAllWords. Это преждевременно останавливает операцию, когда она встречается с буквой, не входящей в корень trie. Я предполагаю, что проблема связана с возвратом []string пустым или неполным.

Вместо return words вы должны использовать break.

Answer 2

ОК, есть две проблемы в реализации ФП в:

• Действие, если блок проверки для детского существования должен «продолжать» петлю вместо возвращения слов в результате (попробовать другие ветви дерева) ,
• Условие блокировки if, проверяющее, должен ли текущий узел быть терминалом (словом), для размещения github.com/derekparker/trie авторского решения о создании терминала в качестве дочернего узла, соответствующего последней букве слово, введенное в его родительское имя как руна 0.

Вот рабочая версия:

func FindAllWords(letters []rune, node *trie.Node, curString string) []string { 
    words := []string{} 
    for i, let := range letters { 
     n, ok := node.Children()[let] 
     if !ok { 
      continue 
     } 
     curWord := curString + string(n.Val()) 
     newLetters := []rune{} 
     newLetters = append(newLetters, letters[:i]...) 
     newLetters = append(newLetters, letters[i+1:]...) 
     if n.Children()[0x0] != nil { 
      words = append(words, curWord) 
     } 
     words = append(words, FindAllWords(newLetters, n, curWord)...) 
    } 
    return words 
} 

Вот несколько более удобочитаемый вариант (на мой вкус, конечно):

func FindAllWords2(s string, n *trie.Node, w string) []string { 
    r := []string{} 
    for i, l := range s { 
     n1, ok := n.Children()[l] 
     if !ok { 
      continue 
     } 
     s1 := s[:i] + s[i+1:] 
     w1 := w + string(l) 
     if n1.Children()[0x0] != nil { 
      r = append(r, w1) 
     } 
     r = append(r, FindAllWords2(s1, n1, w1)...) 
    } 
    return r 
} 

Вторая проблема, конечно, наступающем от зависимости внешнюю библиотеку с несколько протекающим API, который предоставляет детали реализации клиентскому коду.

Чтобы избежать такого рода неприятностей для этого простого случая, я бы рекомендовал построить простую реализацию TRIE, которая может прийти так легко, как это:

type Node struct { 
    Char  rune 
    Term  bool 
    Children map[rune]*Node 
} 

func (n *Node) Add(s []rune) { 
    if len(s) == 0 { 
     n.Term = true 
     return 
    } 
    r := s[0] 
    c, ok := n.Children[r] 
    if !ok { 
     c = &Node{Char: r, Children: make(map[rune]*Node)} 
     n.Children[r] = c 
    } 
    c.Add(s[1:]) 
} 

func Empty() *Node { 
    return &Node{Children: make(map[rune]*Node)} 
} 

Используя эту структуру это, как я загрузил английский список слов :

func English() *Node { 
    f, err := os.Open("/usr/share/dict/american-english") 
    if err != nil { 
     panic(err) 
    } 
    defer f.Close() 
    t := Empty() 
    s := bufio.NewScanner(f) 
    for s.Scan() { 
     t.Add([]rune(strings.ToLower(s.Text()))) 
    } 
    return t 
} 

Эта структура может быть использована в том же алгоритме с очень незначительными изменениями и не misteries реализации:

func FindAllWords3(s string, n *Node, w string) []string { 
    r := []string{} 
    for i, l := range s { 
     n1, ok := n.Children[l] 
     if !ok { 
      continue 
     } 
     s1 := s[:i] + s[i+1:] 
     w1 := w + string(l) 
     if n1.Term { 
      r = append(r, w1) 
     } 
     r = append(r, FindAllWords3(s1, n1, w1)...) 
    } 
    return r 
} 

Вот результаты трех реализаций выше применительно к слову «танцы» и тот же английский словник загружен выше:

[d dan dance dances dane danes dean deans den dena dens dec a ad aden ads an and andes ac acne ace aced aces as ascend n nd na ne ned c cd ca cad cads can cane caned canes cans case cased cs e ed edna end ends es s sad sade san sand sane sac sn snead sc scad scan se sedan sedna sea sean sen send sec] 
[d dan dance dances dane danes dean deans den dena dens dec a ad aden ads an and andes ac acne ace aced aces as ascend n nd na ne ned c cd ca cad cads can cane caned canes cans case cased cs e ed edna end ends es s sad sade san sand sane sac sn snead sc scad scan se sedan sedna sea sean sen send sec] 
[d dan dance dances dane danes dean deans den dena dens dec a ad aden ads an and andes ac acne ace aced aces as ascend n nd na ne ned c cd ca cad cads can cane caned canes cans case cased cs e ed edna end ends es s sad sade san sand sane sac sn snead sc scad scan se sedan sedna sea sean sen send sec]