FoldrW/buildW issues

[Joachim Breitner]

Hi,


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.

> > > Do you have any ideas?
> >
> > Directly related to foldrW, no.
> >
> > About list fusion and foldl in general, some half-baked.
> >
> > I once experimented with a magic "oneShot :: (a -> b) -> (a -> b)"
> > function, semantically the identity, but tell the compiler not to share
> > the result of the computation. Using that in the definition of
> > foldl-as-foldr, one can get the same effect as Call Arity, but a bit
> > more reliable. I need to investigate if that solves the sumConcatInits
> > problem.
> 
> How does that work exactly? Where do you stick the oneShot/

Quite simple, see the attached patch. I think I lost the corresponding
patch to base due to the merge, but all it did was to write

        foldl k z xs = foldr (\v fn -> oneShot (\ z -> fn ( k z v ))) id xs z

also see http://www.joachim-breitner.de/publications/CallArity-TFP.pdf
§6.2.

> why is it valid?

Because the type of build allows the builder to use each result of the
„constructor“ to be used once, and the whole result is called once, by
foldl, with z as the argument.

... at least if the list is finite. If build re-uses a result, then
because it builds an infinite list (e.g. in
        repeat x = build $ \c _ -> let r = x `c` r in r
) and I’m not quite sure if that is a problem. Probably not here,
because foldl applied to an infinite list is is ⊥ anyways. But with
others (e.g. scanl) I might be wrong and the oneShot trick might not
work there.


> > Another idea, probably with the same effect: What happens if we extend
> >         build :: (forall b. (a -> b -> b) -> b -> b) -> [a]
> > to
> >         buildI :: (forall b. (a -> b -> b) -> b -> (b -> b) -> b) -> [a]
> > where the extra argument is the identity, but magically „improves values
> > of type b“. So with
> >
> >         enum = buildI $ \c n imp -> go 0
> >           where go i = imp $ case i of 100 -> n ; _ -> i `c` go (i+1)
> >
> > and
> >
> >    foldl f a0 = foldrI (\x k a -> k (f x a)) id (\k a -> k a) a0
> >
> > we might get good code (but this is half-baked and written as I go).
> 
> It sounds a lot like the foldrW/buildW thing again, but maybe you can
> do better with it.

Yes, it is very much inspired by it, but possibly simpler, and much
weaker: It doesn’t try to undo the continuation style of foldl, but only
helps the compiler a bit. I don’t like it a lot, though.

Gruß,
Joachim

-- 
Joachim Breitner
  e-Mail: mail at joachim-breitner.de
  Homepage: http://www.joachim-breitner.de
  Jabber-ID: nomeata at joachim-breitner.de

-------------- next part --------------
A non-text attachment was scrubbed...
Name: oneShot.patch
Type: text/x-patch
Size: 3246 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20140913/af162919/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20140913/af162919/attachment.sig>