Haskell中scanl与scanr递归定义求助：scanl已实现，scanr遇类型错误

Great work getting scanl' right—your recursive definition perfectly captures how scanl tracks left-to-right intermediate fold results. Let's break down how to build scanr' correctly, since right-associative folds (and their scan counterparts) have a slightly different structure that's easy to trip up on.

First, let's recap the core behavior of foldr to align with what scanr needs to do:

foldr f z (x:xs) = f x (foldr f z xs)

Unlike foldl (which starts at the left and accumulates inward), foldr starts at the rightmost element and works back to the left. scanr needs to capture all those right-to-left intermediate results—so for scanr f z [x1,x2,x3], we expect:
[x1 f(x2f(x3fz)), x2f(x3fz), x3f z, z]

The Correct Recursive scanr' Definition #

Here's the working recursive implementation, with explanations:

scanr' :: (a -> b -> b) -> b -> [a] -> [b]
scanr' f z [] = [z]  -- Base case: empty list only has the initial value
scanr' f z (x:xs) = 
  let tailScans = scanr' f z xs  -- First get all scan results for the tail
  in (f x (head tailScans)) : tailScans  -- Prepend the result of combining x with the tail's first scan value

Why Your Type Error Happened #

Chances are you tried to mirror the scanl' structure directly, which doesn't work for scanr because:

• Function argument order: scanr uses a function of type (a -> b -> b) (matching foldr), whereas scanl uses (b -> a -> b). If you reused the scanl' function type or mixed up the order of arguments to f, you'd get a type mismatch.
• Recursion direction: scanl builds results by prepending the current accumulator before recursing. scanr has to recurse first to get the tail's scan results, then prepend the new value derived from the head of those tail results. Trying to build the accumulator first (like scanl) breaks the right-associative flow and causes type errors.

Testing It Out #

Let's verify with a simple example:

scanr' (+) 0 [1,2,3]  -- Returns [6,5,3,0], which matches the expected scanr output

内容的提问来源于stack exchange，提问作者A.M.