Implementation of "until"

[David Feuer]

I got to looking at the `until` function (in GHC.Base):

-- | @'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)

This function doesn't immediately *appear* to be strict in its third
argument (`x`), but it actually is:

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`.

2. If `p` is not lazy, then `until` is obviously strict in `x`.

I wondered, therefore, whether there might be some benefit, for strictness
analysis, to redefining `until`, either like this:

until p f = \ !y -> go y
  where
    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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141109/95972516/attachment.html>