= Solution
Use a type with distinct values `a` and `n`, and let `s _ y = y`. Suppose a direct <right fold> with the same result type represented this <left fold>. The empty <list> forces `k = n`. The singleton <lists> force `c n n = n` and `c a n = a`. But then
``
foldr c k [a,n] = c a (c n n) = c a n = a,
foldl s n [a,n] = n.
``
Since `a /= n`, this is a <counterexample>. A direct <right fold> cannot recover whether its tail result `n` came from the empty <list> or from the singleton `[n]`. The obstruction already occurs on finite total inputs, so it also rules out an implementation valid on all <lazy lists>.
Back to article page
