如何找到一个列表显示为另一个列表的子列表的索引？

Question

我已经使用 Haskell 一个多星期了，所以我正在练习一些可能对某些事情有用的函数。我想递归地比较两个列表。当第一个列表出现在第二个列表中时，我只想 return 列表开始匹配的索引。索引将从 0 开始。以下是我要执行的示例：

subList [1,2,3] [4,4,1,2,3,5,6]

结果应该是 2

我已经尝试编码了：

subList :: [a] -> [a] -> a
subList [] = []
subList (x:xs) = x + 1 (subList xs)
subList xs = [ y:zs | (y,ys) <- select xs, zs <- subList ys]
        where select []     = []
              select (x:xs) = x

我收到 "error on input"，但我无法弄清楚为什么我的语法不起作用。有什么建议吗？

Answer 1

我们先来看看函数签名。你想接受两个列表，其内容可以比较相等和 return 一个像这样的索引

subList :: Eq a => [a] -> [a] -> Int

现在我们对参数进行模式匹配。首先，当第二个列表为空时，我们无能为力，所以我们将 return -1 作为错误条件

subList _ [] = -1

然后我们看递归步骤

subList as xxs@(x:xs)
  | all (uncurry (==)) $ zip as xxs = 0
  | otherwise                       = 1 + subList as xs

尽管您可能不熟悉 @ 语法，但您应该熟悉我使用的保护语法。本质上，这意味着 xxs 只是一个子项，如果我们使用 (x:xs).

您可能不熟悉 all、uncurry，可能还有 zip，所以让我详细说明一下。 zip 具有函数签名 zip :: [a] -> [b] -> [(a,b)]，因此它需要两个列表并将它们的元素配对（如果一个列表比另一个长，它只会砍掉多余的部分）。 uncurry 很奇怪所以让我们看看 (uncurry (==))，它的签名是 (uncurry (==)) :: Eq a => (a, a) -> Bool，它本质上检查对中的第一个和第二个元素是否相等。最后，all 将遍历列表并查看每对中的第一个和第二个是否相等，如果是，return 为真。

如何找到一个列表显示为另一个列表的子列表的索引？

How can I find the index where one list appears as a sublist of another?

recursion

haskell

list

sublist