1

处理一个给定 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)
4

1 回答 1

2

您的getIndices'实用程序函数被声明为采用 a 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变得多余：它将由getIndices'来自otherwise案例的递归调用然后是新Node []案例来处理。您可能还会考虑如何将您已经拥有的两个案例简化为一个案例。

于 2014-01-02T21:16:55.997 回答