在 Haskell 中实现 "return" 种顺序语言

Question

目前正在阅读 Learn You a 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" 时它可以 "stop" .也就是说，在 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

it seems inefficient for Haskell to use folds and keep iterating through values when it could just "stop" when it hits True.

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

我们可以使用 isPrefixOf :: Eq a => [a] -> [a] -> Bool 来检查一个列表是否是另一个列表的前缀，这比用 take nlen.

这样写更优雅

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

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

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

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

还有一个 isInfixOf :: Eq a => [a] -> [a] -> Bool 函数似乎可以执行您在此处实现的功能。

在 Haskell 中实现 "return" 种顺序语言

Implement "return" of sequential languages in Haskell

haskell

evaluation

fold

short-circuiting