FoldrW/buildW issues

[David Feuer]

Your scanl wrapper might be right for scanl, but it does not satisfy the
condition Joachim proposed. In particular, if we define

(!!) :: [a] -> Int -> a
xs !! n
  | n < 0 = error "Negative index."
  | otherwise = foldrW indexWrap indexCons (error "Large index.") xs n
  where
    indexCons x _ 0 = x
    indexCons _ r n = r (n-1)
    indexWrap = isoSimple

then the simple test

print $ (reverse $ eft 1 1000) !! 50

works just fine. If we replace isoSimple with scanlWrap isoSimple, then the
test fails. That is, this produces wrap and unwrap so that wrap . unwrap is
not much like the identity; it needs to interact with scanlCons in some
fashion to work properly. This does not seem to be at all unusual for
worker/wrapper pairs, but i believe it means we need to find a more general
local correctness criterion than Joachim proposed, if I understood him
correctly.

David


On Sun, Sep 14, 2014 at 2:08 PM, Dan Doel <dan.doel at gmail.com> wrote:

> Which scanl wrapper are you referring to?
>
> The first one I figured out was quite wrong in certain ways. But I think
> the new one is less controversial; it's a lot like the reverse one.
>
> On Sun, Sep 14, 2014 at 1:03 PM, David Feuer <david.feuer at gmail.com>
> wrote:
>
>> Joachim Breitner wrote:
>>
>>> Am Samstag, den 13.09.2014, 00:01 -0400 schrieb David Feuer:
>>> > On Sep 12, 2014 2:35 PM, "Joachim Breitner" <mail at joachim-breitner.de>
>>> > wrote:
>>> > > Interesting. I assumed that some wrap.unwrap=id law would hold, or
>>> > at
>>> > > least some moral approximation (e.g. disregarding bottoms in an
>>> > > acceptable manner). But if the wrappers have to do arbitrary stuff
>>> > that
>>> > > can arbitrarily interact with how the producer calls them, this
>>> > becomes
>>> > > a bit less appealing.
>>> >
>>> > No, nothing pleasant like that, I'm afraid. isoSimple is like that of
>>> > course, but once it gets to foldl, the fusion rule is handing the
>>> > builder a wrap/unwrap pair that isn't even close to that.
>>>
>>> and parametricity doesn't help here? Note that due to the forall in the
>>> type of buildW, you can probably reason about what kind of values buildW
>>> can produce, as it can only use whatever the consumer handed to it.
>>> Maybe there is an invariant for that type, and the worker/wrapper pair
>>> is the identity for values that fulfill that invariant.
>>>
>>
>> That seems reasonable, and I suspect without any proof that Takano Akio's
>> wrapper for foldl and Dan Doel's wrapper for reverse probably satisfy it.
>> Scans seem to be more of a challenge. It appears to me that Dan's scanl
>> wrapper probably does *not* satisfy that requirement, and I don't know
>> enough to have much chance of finding one that does.
>>
>> David
>>
>> _______________________________________________
>> ghc-devs mailing list
>> ghc-devs at haskell.org
>> http://www.haskell.org/mailman/listinfo/ghc-devs
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20140914/6344026a/attachment.html>