Loop in recursion in Haskell

Question

I have stumbled upon the following problem. Say I have a recursive function like

run :: [Int] -> [Int]
run [] = []
run (x:xs) = 1:x:run xs

The important thing about it is that it head $ run <whatever> is always 1. This means that the following will produce the output 1:

head $ run [error "shouldnt get here"]

This proves that Haskell doesn't evaluate the argument if it doesn't need to -- obviously, since that's one of the most famous Haskell features. However, if I were to use the result as an argument, like:

let out = run (cycle out) in head out

I get a runtime error <<loop>>.

How come?

I am using runghc 8.4.2. Is that a bug or am I missing something here?

chi · Accepted Answer · 2019-12-11 13:27:20Z

run (error "urk!") will error out.

Instead, run [error "urk!"] will successully return 1.

Why? Because run is defined by cases: empty list, nonempty list. Hence it has to evaluate its argument just enough to know if the list is empty or not. We don't have to evaluate the error in [error "urk!"] to see that the list is not empty, but we have if error "urk!" is the list itself.

In the posted code, we evaluate run (cycle out) so we have to check if cycle out is empty or not. This triggers the evaluation of cycle out, which in turn triggers the evaluation of out (cycle is defined by cases as well). Since out is what we are defining, we get an infinite recursion.

It happens that this infinite recursion is easy enough to be spotted by the GHC runtime, which kindly emits an exception <<loop>> instead of perform the non terminating computation.

To stress the concept, consider these functions

strictPrepend :: [Int] -> [Int]
strictPrepend []     = 1 : []
strictPrepend (x:xs) = 1 : x : xs

lazyPrepend :: [Int] -> [Int]
lazyPrepend xs = 1 : xs

One might think that these functions are equal. Indeed, the first one is defined by cases, but in both cases it performs the same operation (prepending 1), so it looks equivalent to the second.

Concretely, we have that for all bottom free lists ys, the result of strictPrepend ys is the same as lazyPrepend ys.

In the presence of bottoms (like error "..", undefined, or infinite recursion), these functions differ. For instance lazyPrepend undefined = 1 : undefined, while strictPrepend undefined = undefined since it raises an exception before producing the initial element 1.

Consequently,

let ys = strictPrepend ys
    zs = lazyPrepend zs

defines ys as bottom (infinite recursion) but zs = 1:1:1:1:..... is an infinite sequence of 1s. This is the effect of producing the 1 before needing to evaluate the argument.

Bergi · Accepted Answer · 2019-12-11 13:00:53Z

4

The important thing about it is that it head $ run <whatever> is always 1.

Actually, no. Only when whatever is a non-empty list. When you pass in [], the run function will return an empty list. The argument of run is evaluated, to the point where it can decide what case to match, in WHNF. This does not evaluate the content of the list or the tail of the list.

In let out = run (cycle out), the cycle function has exactly the same problem - it needs to pattern match the list. Since that depends on the result of cycle itself, you would have a recursive evaluation, which the runtime complains about.

answered Dec 11, 2019 at 13:00

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

Collectives™ on Stack Overflow

Loop in recursion in Haskell

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related