Haskell 中 scanl 和 scanr 的递归定义

Question

我已经搜索过，但找不到函数 scanr 和 scanl 的简单定义，仅说明它们显示了函数 foldr 和 foldl 的中间计算（分别）。

我已经为 scanl 写了一个递归定义，基于 foldl 属性 foldl f y (x:xs) = foldl f (f y x) xs:

scanl' :: (b -> a -> b) -> b -> [a] -> [b]
scanl' f x [] = [x]
scanl' f x (y:ys) = x : scanl' f (f x y) ys

这似乎有效。但是，当我尝试将此类比应用于 foldr 属性 foldr f y (x:xs) = f x (foldr f y xs):

时出现类型错误

scanr' :: (a -> b -> b) -> b -> [a] -> [b]
scanr' _ x [] = [x]
scanr' f x (y:ys) = y : f x (scanr' f x ys)

这会失败，因为 f 的第二个输入需要是 b 而不是 [b]。但是，我不确定如何在 scanr'.

上递归执行此操作

Answer 1

计算

result = scanr' f x (y:ys)

你一定计算过

partialResult = scanr' f x ys

之后你得到

result = (y `f` head partialResult) : partialResult

完整的实现是

scanr' _ x [] = [x]
scanr' f x (y:ys) = (y `f` head partialResult) : partialResult
    where partialResult = scanr' f x ys

Answer 2

scanl1 (\acc x -> if x > acc then x else acc)[3,4,5,3,7,9,2,1]

来自 Learn You A Haskell 似乎只有两个参数：函数和列表。但它有效。如果您将其写为：

，它甚至可以工作

scanl1 (\x acc -> if x > acc then x else acc)[3,4,5,3,7,9,2,1]

有点不明白为什么有效。

Recursive definitions of scanl and scanr in Haskell