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 ?

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.