Implementation of "until"

[Edward Kmett]

Neither of your examples have their strictness changed by David's proposed
modification, no?

>From what I can see with a cursory glance, he's just proposing
acknowledging the strictness that is already there but which is buried
behind a conditional, and replacing the 'bad' looping bottom that leaks
forever and can't be caught with the argument bottom which can be given
right away.

-Edward

On Sun, Nov 9, 2014 at 2:47 PM, Dan Burton <danburton.email at gmail.com>
wrote:

> It's more accurate to say that "until" is *as lazy as* its predicate
> argument.
>
> -- infinite loop, slow space leak
> until ((== 10) . (!! 3)) [1, 2, 3, 4] (\xs -> xs ++ xs)
> -- first-iteration errors out due to strictness of predicate
> until ((== 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 Burton
>
> On Sun, Nov 9, 2014 at 11:14 AM, David Feuer <david.feuer at gmail.com>
> wrote:
>
>> 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
>>
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://www.haskell.org/mailman/listinfo/libraries
>>
>>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141109/3ce462d8/attachment-0001.html>