It's more accurate to say that "until" is as lazy as its predicate argument.-- infinite loop, slow space leakuntil ((== 10) . (!! 3)) [1, 2, 3, 4] (\xs -> xs ++ xs)-- first-iteration errors out due to strictness of predicateuntil ((== 10) . (!! 3)) [1,2,3,undefined] (\xs -> xs ++ xs)Your proposed changes introduce arbitrary strictness which I don't see any particular benefit to. Is there a specific example you had in mind where the behavior is better?-- Dan BurtonOn Sun, Nov 9, 2014 at 11:14 AM, David Feuer <david.feuer@gmail.com> wrote:_______________________________________________2. If `p` is not lazy, then `until` is obviously strict in `x`.1. If `p` is lazy, then either it's `const True`, so `until p f x = x`, or it's `const False`, so `until p f x = _|_`. In the first case, it's certainly strict in `x`, and in the second case, it goes into an infinite loop, so it's trivially strict in `x`.I got to looking at the `until` function (in GHC.Base):This function doesn't immediately *appear* to be strict in its third argument (`x`), but it actually is:
-- | @'until' p f@ yields the result of applying @f@ until @p@ holds.
until :: (a -> Bool) -> (a -> a) -> a -> a
until p f = go
where
go x | p x = x
| otherwise = go (f x)I wondered, therefore, whether there might be some benefit, for strictness analysis, to redefining `until`, either like this:until p f = \ !y -> go ywhere
go x | p x = x
| otherwise = go (f x)or (probably not) like this:
until p f = go
where
go !x | p x = x
| otherwise = go (f x)The only *semantic* change here is that it can, potentially, replace an infinite loop with an exception. GHC definitely analyses the strictness differently; what I can't tell is whether this will actually help it produce better code in some cases. Specifically, the current `until` implementation gets
Str=DmdType <C(S),C(U)><L,C(U)><L,U>,whereas the modified ones get
Str=DmdType <C(S),C(U)><L,C(U)><S,1*U>,I don't actually know how to read these, but I can see they're different in the third argument. The two alternatives are also analyzed differently, with the `go` function getting different strictness info. I would speculate, however, that the one that modifies `go` could lead to double-forcing in the loop in some cases, which would presumably be bad.David
Libraries mailing list
Libraries@haskell.org
http://www.haskell.org/mailman/listinfo/libraries