new keyword: infixlr?
S. Doaitse Swierstra
doaitse at cs.uu.nl
Fri Sep 10 17:18:13 EDT 2010
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.
> Haskell-prime mailing list
> Haskell-prime at haskell.org
More information about the Haskell-prime