3

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?

user2407038
  • 14,400
  • 3
  • 29
  • 42
Anabra
  • 91
  • 6
  • I'm voting to close this question as off-topic because it's not a question anymore (OP figured it out) – luqui Mar 03 '17 at 02:33
  • 5
    Tail recursion is less important than guarded recursion in Haskell. https://wiki.haskell.org/Tail_recursion – chepner Mar 03 '17 at 03:22
  • Also relevant: [*Does Haskell have tail-recursive optimization?*](http://stackoverflow.com/q/13042353/2751851) – duplode Mar 03 '17 at 03:38
  • You're right about guarded recursion, it would still work here because of the Cons ctor. – Anabra Mar 03 '17 at 09:21

1 Answers1

3

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.

Anabra
  • 91
  • 6