new keyword: infixlr?

Ian Lynagh igloo at earth.li
Fri Sep 10 14:13:33 EDT 2010


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)?

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?

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?


Thanks
Ian



More information about the Haskell-prime mailing list