Re: FoldrW/buildW issues

13 Sep 2014

      Hi,

Am Samstag, den 13.09.2014, 00:01 -0400 schrieb David Feuer:
...
...
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
On Sep 12, 2014 2:35 PM, "Joachim Breitner" 
wrote:
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@joachim-breitner.de
  Homepage: http://www.joachim-breitner.de
  Jabber-ID: nomeata@joachim-breitner.de