CODEWITHSUNDEEP
haskelllazy-evaluation
Darren Smith
Darren Smith

Reputation: 207

Is pattern matching tuples not fully lazy?

I ran across some very unintuitive behavior in Haskell and am not sure if it is a bug in Haskell or not. If this is intended behavior, what specifically causes the infinite loop?

import Data.Function (fix)

main=putStrLn$show$fst$
    fix (\rec-> (\(a1,a2)->(3,7)) rec)

Infinite loops, I assume because to pattern match rec into rec (a1,a2) it evaluates. But I feel like it shouldn't need to because everything will match. For example these all work correctly:

    fix (\rec-> (\a->(3,7)) rec)
    fix (\rec-> (\a->let (a1,a2)=a in (3,7)) rec)

Interestingly this exits with error

    fix (\rec-> (\(a1,a2)->(3,7)) undefined)

But I could have sworn the original code where I encountered this behavior (which was more complicated) would actually work in this case. I could try to recreate it.

Upvotes: 3

Views: 318

Answers (2)

Will Ness
Will Ness

Reputation: 71119

Tuple (or any other) pattern match is lazy if in let, not lazy if in case. apparently, a lambda application is reduced via case, not via let.

(correction: for a refutable pattern pat, (\pat -> ...) val is the same as (\x -> case x of pat -> ...) val == let x = val in case x of pat -> ..., so it's not that the reduction is done via case, but that the identity (\pat -> ...) == (\x -> case x of pat -> ...) must hold).

Thus your code reduces as

fix (\rec-> (\(a1,a2)->(3,7)) rec)
=
let { x = (\rec-> (\(a1,a2)->(3,7)) rec) x } in x
=
let { x = (\(a1,a2)->(3,7)) x } in x
=
let { x = (\y -> case y of (a1,a2)->(3,7)) x } in x
=
let { x = case x of {(a1,a2)->(3,7)} } in x

and that's why the pattern match for x against (_,_) is performed before it is revealed that it is would be (3,7) (but isn't!).

So, Haskell is not a declarative language. Its semantics is by least fixed point.

Upvotes: 1

Daniel Wagner
Daniel Wagner

Reputation: 153352

Correct, tuple pattern matches are not lazy. In fact, with two notable exceptions, no pattern match is lazy. To a first approximation, the "point" of pattern matching is to force evaluation of the scrutinee of the match.

Of course, a pattern match may appear in a place where laziness means it is never performed; for example,

const 3 (case loop of (_, _) -> "hi!")

will not loop. But that's not because the match is lazy -- rather, it's because const is lazy and never causes the match to be performed. Your let example is similar, as the semantics of let is that variables bound by it are not forced before evaluating the body of the let.

One of the two notable exceptions is a special pattern modifier, ~; putting ~ before a pattern says to make the match lazy and, consequently, is a claim to the compiler that the modified pattern always matches. (If it doesn't match, you get a crash once one of the bound variables is forced, not the usual fall-through-to-next-pattern behavior!) So, one fix for your fix is:

fix (\rec -> (\ ~(a1, a2) -> (3, 7)) rec)

Of course, the explicit name for rec isn't needed. You could just as well write:

fix (\ ~(a1, a2) -> (3, 7))

The other notable exception is newtype matching, which is not relevant here.

Upvotes: 13

Related Questions