new keyword: infixlr?

[S. Doaitse Swierstra]

On 10 sep 2010, at 20:13, Ian Lynagh wrote:

> On Fri, Sep 10, 2010 at 07:51:10PM +0200, S. Doaitse Swierstra wrote:
>> 
>> Currently Haskell has infix, infixl and infixr operators. I see a use for infixlr as well. This indicates that the implemtation may assume the operator to be associative, and thus has the freedom to "balance" an expression containing several operator occurrences.
> 
> Would it be restricted to use with operators with types that are (a -> a
> -> a) (or more specific)?

This is what I would normally expect from an infix operator. 

> 
> Otherwise e.g.
>   let (+:) = (:)
>       infixlr :+
>   in [] +: [] +: []
> could have type [[a]] or [[[a]]].
> 
>> The reason that I bring up this is that in a new combinator I have added to my parser library (the <||> in Text.ParserCombinators.UU.Derived) internally uses cartesian products, which are being constructed and updated. If the compiler had the right to interpret  the expressions a <||> b <||>c <||> d  as e.g. (a <||> b) <||> (c <||> d) then the updating time for would go down from O(n) to O(log n). 
> 
> How would the compiler work out which parsing to prefer? Or would it
> assume that infixlr expressions are best balanced?

Yes, that is the idea.


> 
> When first reading the proposal, I thought the idea was to allow the
> compiler to more easily perform optimisations like
>   a+b+c+2+3+d => a+b+c+5+d
> but I guess that wasn't something you were thinking about?

Indeed, but the behaviour would not be forbidden either. If you would expect this then I would probably also want to introduce "comm" for commutative operators, so a+2+b+c would get transformed into a+b+c+(2+4). The only suse for this is that after inlining  some further optimisations might take place, which would be hard for a programmer to achieve otherwise. My intention was however not to make things very complicated at this point.

Doaitse

> 
> 
> Thanks
> Ian
> 
> _______________________________________________
> Haskell-prime mailing list
> Haskell-prime at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-prime