Laziness inside a data type

Question

I thought I understood laziness well until I came up with the following code, which yields a <<loop>> error.

weird = ([1],[2]) <> weird
main = print (head $ fst weird)

Intuitively, here is what I thought Haskell would do : "I need first element of weird. And I need the head of this first element. So I need compute fst weird. Now I know that fst weird = [1] ++ fst weird (or do I ??) from the semigroup instance for pairs. So that's great, I should return 1"

Where did I get this wrong ?

Gastrotrich

Haskell does not really do so much advanced analysis. It is basically just functions producing data constructors where the parameters don't refer to real values, but just to expressions that are then evaluated. – Collett

So if Haskell was able to produce say "half pairs" where half of the pair is evaluated and the other not, the code above would work ? – Gastrotrich

no, here the <> operator is at fault for not being to lazy. – Collett

@willeM_VanOnsem that's exactly the question. Why isn't it lazy? It is lazy enough in foo = [1] <> foo, so that we are able to take head foo. Why wrapping it in a pair changes things? – Incorporeal

@n.m.couldbeanAI: it is the implementation of (a, b) <> (a', b') = (a <> a', b <> b'), the patterns are not lazy, so it first needs to make sure that these are 2-tuples, even if there is only one data constructor. So it works with irrefutable patterns: ~(a, b) <> ~(a', b') – Collett

Answer 1

It is pattern matching that is at fault here. Indeed, if we look at the instance of Semigroup for the 2-tuple instance ^[src], we see:

instance (Semigroup a, Semigroup b) => Semigroup (a, b) where
    (a,b) <> (a',b') = (a<>a',b<>b')
    stimes n (a,b) = (stimes n a, stimes n b)

so here it takes two 2-tuples and then it will combine the two. But this means it does pattern matching on the first and second operand. For the second operand, there is problem, since that is the result of a computation, so that triggers the system in evaluating these.

The matching might look unnecessary, but it is possible to pass undefined or some other mechanism that causes a loop, like it did here, and the code thus basically asks to check if the second operand is a 2-tuple.

What we can do is work with an irrefutable pattern, such that we will assume that the data constructor holds and only unpack it if necessary. So we can implement some sort of sum ourselves with:

(<^>) :: (Semigroup a, Semigroup b) => (a, b) -> (a, b) -> (a, b)
~(a,b) <^> ~(a',b') = (a<>a',b<>b')

and then our own implementation works with:

weird = ([1],[1]) <^> weird
main = print (head $ fst weird)

so we made the implementation more lazy to combine the two 2-tuples.

Personally I would think the combinations for Semigroups, etc. on 2-tuples (and any n-tuple) can be done with irrefutable patterns. I don't know if there are good reasons why that is not the case in the base package.

Collett

Very interesting! I can see an argument either way. The question comes down to whether (a, b) <> undefined should ever be allowed to be anything other than bottom (assuming (<>) on the underlying types doesn't evaluate its arguments). And I would personally argue that (a, b) <> undefined should bottom out, rather than treating the second argument as (undefined, undefined) (which is what an irrefutable pattern effectively turns it into). But I definitely see the case for the opposite way. – Quoth

Answer 2

As already explained, the issue is that <> is strict on pairs.

One way to work around the issue is to "lazify" the result in a more explicit way.

For instance,

weird = lazify $ ([1],[1]) <> weird
   where lazify ~(x,y) = (x,y)

works since lazify produces the top level pair constructor (_, _) before the recursion of weird is demanded, thanks to the lazy pattern matching in ~(x,y).

lazify could also be equivalently defined as lazify p = (fst p, snd p). Note how it looks like the identity on pairs but it is not exactly the identity: the output (_, _) is produced before the input is inspected. To stress the point, this does not crash:

case lazify (undefined :: (Int, Int)) of
   (_x, _y) -> 42

Indeed, this never forces the undefined.

It can be quite confusing at first, since one needs to keep in mind what is being evaluated at which time. Personally, I believe that theory helps a lot here. The denotational semantics of lambda calculi with recursion (PCF), with all its CPOs with bottoms, explains the result very well, in my eye.

Southwestwardly