Haskell：检查第一个列表是否是第二个列表的前缀

Question

我正在尝试编写一个程序来检查第一个列表是否是第二个列表的前缀。例如，[5,6] 是 [1,5,6,7] 的前缀。这是我的工作代码，但基本上我不知道如何去做。

prefix [Int] -> [Int] -> Bool 
prefix [] [] = [] 
prefix y (x:xs)  
| x == y    = prefix y xs 
| otherwise = 0 

有什么帮助吗？

Answer 1

如果我们查看类型，您的代码没有多大意义：

prefix [Int] -> [Int] -> Bool 
prefix [] [] = [] 
prefix y (x:xs)  
| x == y    = prefix y xs 
| otherwise = 0

由于两个参数是列表 ( [Int])，因此这意味着y是[Int]、x是Int、xs是[Int]。但是然后你比较x == y，你不能比较一个列表和一个元素。(==)被定义为(==) :: Eq a => a -> a -> Bool。

这里还有其他问题：你在第一个子句中返回一个列表，但返回类型是 a Bool，然后你返回 a 0（同样，它应该是 a Bool）。

如果我们定义一个函数，我们首先需要为它定义一个特定的模型。什么时候列表l1是列表l2的前缀？如果l1是一个空列表，那么l1总是一个前缀，不管第二个列表的值是什么，所以：

prefix [] _ = True

如果l1是一个列表（即(x:xs)），那么它在两种情况下不是前缀：（1）如果l2是一个空列表；和 (2) 如果l2的第一项（yin(y:ys))不等于x，所以：

prefix _ [] = False
prefix (x:xs) (y:ys) | x /= y = False
                     | otherwise = ...

现在的问题是prefix (x:xs) (y:ys)万一如何处理x == y。在这种情况下，我们对两个列表进行递归，因此prefix (x:xs) (y:ys) == prefix xs ys（仅在情况下x == y）的结果，因此：

                     | otherwise = prefix xs ys

或者现在完整：

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

我们可以进一步将表达式概括为Eq a => [a] -> [a] -> Bool这样，它适用于作为实例的任何类型（因此在 上定义了一个实例）：aEq(==)a

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

我们也可以交换条件，因为通常正逻辑比负逻辑更容易理解：

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

现在我们可以进一步移除守卫，并使用一个(&&) :: Bool -> Bool -> Bool代替：

prefix :: Eq a => [a] -> [a] -> Bool
prefix [] _ = True
prefix _ [] = False
prefix (x:xs) (y:ys) = x == y && prefix xs ys