Рекурсивные определения scanl и scanr в Haskell

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