使Haskell List Recursion函数更有效

Question

我编写了一个函数,它将比较两个列表并检查第一个是否是第二个的前缀,并且必须使用递归完成.

例如:

prefix [1,2] [1,2,3]
>True
prefix [2,1,4] [2,1,13,4]
>False

现在我已经做到了这一点,但我觉得它效率低下:

prefix :: [Int] -> [Int] -> Bool
prefix (x:xs) (y:ys)
|   null xs                         =   True
|   x == y && head xs == head ys    =   True && prefix xs ys
|   head xs /= head ys              =   False

我希望它可以更有效地完成,并有一些更好的模式匹配.是真的吗？

Answer 1

您根本不需要使用该head功能.这使得比较的数量增加了一倍.试试这个:

prefix :: [Int] -> [Int] -> Bool
prefix [] _ = True
prefix _ [] = False
prefix (x:xs) (y:ys)
  | x == y = prefix xs ys
  | otherwise = False