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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-prime
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-prime
