[Haskell-cafe] Arrow preprocessor and *** combinator

Luke Palmer lrpalmer at gmail.com
Thu Apr 30 16:15:15 EDT 2009


On Thu, Apr 30, 2009 at 11:42 AM, Peter Verswyvelen <bugfact at gmail.com>wrote:

> Thanks Ross.
> Does anyone know how to tackle this? Combining GHC's builtin arrow
> processor and rewrite rules?
>

Another possibility is to make an "optimizer" arrow transformer that encodes
the rules.  Eg.

data Optimize a b c where
    Arr :: (b -> c) -> Optimize a b c
    (:>>>) :: Optimize a b c -> Optimize a c d -> Optimize a b d
    First :: Optimize a b c -> Optimize a (b,d) (c,d)
    Second :: Optimize a b c -> Optimize a (b,d) (c,d)
    (:***) :: Optimize a b b' -> Optimize a c c' -> Optimize a (b,b') (c,c')

optimize :: Optimize a b c -> Optimize a b c
optimize (First f :>>> Second g) = f :*** g
...

compile :: (Arrow a) => Optimize a b c -> a b c
compile (Arr f) = arr f
compile (f :>>> g) = compile f >>> compile g
...

I have of course handwaved over optimize, which will have some interesting
traversal structure; esp. if you want to take advantage of the associativity
of >>>.

Unfortunately, Arr is not quite transparent enough to do everything one
might want with this.  e.g.,this rule cannot be encoded:

swap (x,y) = (y,x)
first f >>> arr swap >>> first g = f *** g >>> arr swap

If you are serious about arrow optimizations, it might be worthwhile to
modify the original preprocessor to output a richer GADT (with cases for
things like ArrSwap) with all the information it knows, so that user code
can experiment with optimizations.

Godspeed on this interesting problem.  Please publish :-)

Luke


> On Wed, Apr 29, 2009 at 3:43 PM, Ross Paterson <ross at soi.city.ac.uk>wrote:
>
>> On Wed, Apr 29, 2009 at 03:07:25PM +0200, Peter Verswyvelen wrote:
>> > After doing some pragmatic tests, it seems that neither the arrow
>> preprocessor
>> > nor GHC's builtin one generate / optimize to the (***) combinator.
>>
>> Right, neither of them do that.  It might be possible to do that using
>> GHC rules, but it isn't done at the moment.
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090430/b24e47fc/attachment.htm


More information about the Haskell-Cafe mailing list