在Haskell中实现顺序语言的“返回”

Question

[目前正在阅读《学习Haskell》，而我遇到了这个示例，用于搜索子列表是否在列表中：

searchSublist :: (Eq a) => [a] -> [a] -> [Bool]
searchSublist needle haystack =
  let nlen = length needle
  in foldl (\acc x -> if take nlen x ==  needle then True else acc) False (tails haystack)

抛开算法最优性（想到了Horspool的算法），Haskell使用折叠并在其达到“ True”时仅能“停止”时保持遍历值的效率低下。也就是说，例如，在Python中，我们可能会遇到...

def sublist_exists(needle, haystack):
  nlen = len(needle)
  if len(haystack) < nlen:
    return False
  elif haystack[:nlen] == needle:
    return True
  else:
    return sublist_exists(needle, haystack[1:])

并且如果达到True条件，我们将停止。

但是，对于Haskell代码，如果将fold切换为scan，则会得到...

searchSublist :: (Eq a) => [a] -> [a] -> [Bool]
searchSublist needle haystack =
  let nlen = length needle
  in scanl (\acc x -> if take nlen x ==  needle then True else acc) False (tails haystack)

ghci> searchSublist [3,4,5] [1..5]
[False,False,False,True,True,True,True]

似乎无法遍历整个列表。

Answer 1

Haskell使用折叠并在遍历True时可能只是“停止”时保持遍历值的效率低下。

如果使用foldr并使用(||)所使用的延迟，它可能从找到元素的那一刻起停止。例如，take nlen x不会首先计算整个列表，这也将延迟进行，因此(==)函数将逐元素检查，并且从两个元素之一不同的那一刻起，它将停止。

[我们可以使用isPrefixOf :: Eq a => [a] -> [a] -> Bool检查一个列表是否是另一个列表的前缀，这比用isPrefixOf :: Eq a => [a] -> [a] -> Bool编写的列表更优雅。

因此，我们可以将其实现为：

take nlen

或带有

searchSublist :: (Eq a) => [a] -> [a] -> Bool
searchSublist needle = foldr ((||) . isPrefixOf needle) False . tails

：

any :: Foldable f => (a -> Bool) -> f a -> Bool

还有一个any :: Foldable f => (a -> Bool) -> f a -> Bool函数似乎可以完成您在此实现的功能。

Answer 2

其中存在解决方案。切换到

searchSublist :: (Eq a) => [a] -> [a] -> Bool
searchSublist needle = any (isPrefixOf needle) . tails

，其结果通过

isInfixOf :: Eq a => [a] -> [a] -> Bool

在第一个isInfixOf :: Eq a => [a] -> [a] -> Bool值上停止：

scanl