Haskell: Algebraic types error (Suffix trees: recursion)

Question

Working on a function that given a SuffixTree as input, outputs the list of integers in that suffix tree. For example. getIndices tree1 = [2,4,1,3,5,0] . The order of the list of integers does not matter. I am getting the error, on the second last line of the function: "Couldn't match expected type 'SuffixTree' with actual type '[SuffixTree]'". I have thought about this for a long time now and have had no luck. Any help would be greatly appreciated.

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

Your getIndices' utility function is declared to take a SuffixTree, but in the otherwise case you're passing it (Node xs:[Node ys]) which has type [SuffixTree].

Given that all you want to do is to collect up the integers in the tree, perhaps your otherwise case just needs to call getIndices' twice:

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

Your code also has some other problems. If you compile with warnings (-Wall) the compiler will warn you about incomplete pattern matches. Your code also fails at runtime because of them.

The incompleteness is because getIndices' doesn't cover all possible kinds of SuffixTree. You also need to fill in cases for getIndices' (Leaf Int) and getIndices' (Node []).

Also, your existing case for | Node xs == Node [] within the Node ((_, Node xs):ys case then becomes redundant: it'll be handled by the recursive call to getIndices' from the otherwise case and then the new Node [] case. You might also think about how to simplify the two cases you have already into a single case.