Haskell: ошибка алгебраических типов (деревья суффиксов: рекурсия)

Question

Работая над функцией, для которой в качестве входных данных задано SuffixTree, выводится список целых чисел в этом дереве суффиксов. Например. getIndices tree1 = [2,4,1,3,5,0] . Порядок списка целых чисел не имеет значения. Я получаю сообщение об ошибке во второй последней строке функции: "Couldn't match expected type 'SuffixTree' with actual type '[SuffixTree]'"Я долго думал об этом и не повезло. Любая помощь будет принята с благодарностью.

data SuffixTree = Leaf Int | Node [ ( String, SuffixTree ) ] 
            deriving (Eq,Ord,Show)

text1 :: String
text1 = "banana"

tree1 :: SuffixTree
tree1 = Node [("banana",Leaf 0),
              ("a",Node [("",Leaf 5),
                         ("na",Node [("",Leaf 3),
                                     ("na",Leaf 1)])]),
              ("na",Node [("",Leaf 4),
                          ("na",Leaf 2)])]

------------------------------------------------------------------

getIndices :: SuffixTree -> [ Int ]
getIndices sufTree = getIndices' sufTree [] 
  where getIndices' :: SuffixTree -> [Int] -> [Int]
        getIndices' (Node ((_, Node xs):ys)) c 
          | Node xs == Node [] = c
          | otherwise = getIndices' ((Node xs):([Node ys])) c
        getIndices' (Node ((_,Leaf i):xs)) c = getIndices' (Node xs) (i:c)

Answer 1

Ваш getIndices' функция полезности объявлена ​​принять SuffixTree, но в otherwise если вы передаете это (Node xs:[Node ys]) который имеет тип [SuffixTree],

Учитывая, что все, что вы хотите сделать, это собрать целые числа в дереве, возможно, ваш otherwise дело просто нужно позвонить getIndices' дважды:

| otherwise = getIndices' (Node xs) (getIndices' (Node ys) c)

У вашего кода также есть некоторые другие проблемы. Если вы компилируете с предупреждениями (-Wall) компилятор предупредит вас о неполных совпадениях с образцом. Ваш код также дает сбой во время выполнения из-за них.

Неполнота заключается в том, что getIndices' не охватывает все возможные виды SuffixTree, Вы также должны заполнить дела для getIndices' (Leaf Int) а также getIndices' (Node []),

Кроме того, ваш существующий случай для | Node xs == Node [] в пределах Node ((_, Node xs):ys case становится излишним: он будет обработан рекурсивным вызовом getIndices' от otherwise случай, а затем новый Node [] дело. Вы также можете подумать о том, как упростить два случая, которые у вас уже есть, в один случай.