Reputation: 207
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
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
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