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。

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

如果我们定义一个函数，则首先需要为其定义某个模型。列表 l1 什么时候列表 l2 的前缀？如果 l1 是一个空列表，那么 l1 始终是前缀，无论第二个列表的值如何

prefix [] _ = True

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

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

现在，问题是在x == y时如何处理prefix (x:xs) (y:ys)。在这种情况下，我们在两个列表上重复出现，因此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，以便它可与Eq实例一起使用任何 type a（因此，在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

Answer 2

刚在这里留下我的两分钱，并结合了序曲的功能：

isPrefix :: Eq a => [a] -> [a] -> Bool
isPrefix l1 l2 = take (length l1) l2 == l1