Recursive definitions of scanl and scanr in Haskell

Question

I have searched but cannot find simple definitions of the functions scanr and scanl, only explanations that they show the intermediate calculations of the functions foldr and foldl (respectively).

I have written a recursive definition for scanl, based on the foldl property 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

This seems to work. However, there is a type error when I try to apply this analogy with the foldr property 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)

This fails as the second input for f needs to be a b not a [b]. However, I am unsure how to do this while also recursing on scanr'.

Answer 1

To compute

result = scanr' f x (y:ys)

you must have computed

partialResult = scanr' f x ys

after which you get

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

The complete implementation is

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