Propagating information backwards in a recursive call

Question

How can I propagate information backwards in a recursive call-chain?

For example:

f :: [Int] -> [Int]
f (x:xs)
  | x `mod` 17 = ...
  | otherwise = (x + 1) : f xs
f [] = []

I want to stop the evaluation at the ..., and I also want to propagate that information back to the caller (the fact that it stopped). I tried to use return types like Maybe, but then I had to pattern-match the recursive call, and thus lost tail-call optimization, since I had to evaluate it after the call returned (note: one could easily transform the above code to TR form, but I left it like this for easier understanding).

Can you come up with a better solution that still benefits from TCO?

Answer 1

You can always use extra parameters, and return a tuple with the accumulated results. This way you still benefit from TCO, and get the information you needed.

An example:

f :: [Int] -> Bool -> [Int] -> (Bool, [Int])
f (x:xs) l accum
  | x `mod` 17 == 0 = (False, accum)
  | otherwise       = f xs l ((x+1) : accum)
f [] l accum = (True, accum)

Or in a more elegant way:

data CheckedValue a = Valid a | Invalid a
  deriving Show

f :: [Int] -> [Int] -> CheckedValue [Int]
f (x:xs) accum
  | x `mod` 17 == 0 = Invalid accum
  | otherwise       = f xs ((x+1) : accum)
f [] accum = Valid accum

Note: These functions also reverse the list, but pay no attention to that.