Re: new keyword: infixlr?
My prosaic solution would be to have more stock implementations of mconcat (here balancedMconcat, though some parallelMconcat's would also be fun) that make use of the associativity guarantee. Then use that explicitly:-- balancedMconcat . fmap Sum $ [a, b, c, 2, 3, d] rather than asking the compiler to be magic for you. Freddie On 14 September 2010 13:11, Bas van Dijk wrote: > Oops, I mixed up associative with commutative. > > On Tue, Sep 14, 2010 at 1:27 PM, Bas van Dijk > wrote: > > On Mon, Sep 13, 2010 at 4:23 PM, Nick Bowler > wrote: > >> ... not all Num instances have an associative (+). > > > > Indeed: > > > > $ cabal install repr# [1] > > ... > > $ ghci > > Prelude> :m Text.Repr > > Prelude Text.Repr> show (1 + 2 :: Repr Int) == show (2 + 1 :: Repr Int) > > False > > > > because: > > show (1 + 2 :: Repr Int) == "1 + 2" > > show (2 + 1 :: Repr Int) == "2 + 1" > > > > but note: > > Prelude Text.Repr> (1 + 2 :: Repr Int) == (2 + 1 :: Repr Int) > > True > > > > Bas > > > > [1] http://hackage.haskell.org/package/repr > > > ___ > 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
Re: new keyword: infixlr?
Oops, I mixed up associative with commutative. On Tue, Sep 14, 2010 at 1:27 PM, Bas van Dijk wrote: > On Mon, Sep 13, 2010 at 4:23 PM, Nick Bowler wrote: >> ... not all Num instances have an associative (+). > > Indeed: > > $ cabal install repr # [1] > ... > $ ghci > Prelude> :m Text.Repr > Prelude Text.Repr> show (1 + 2 :: Repr Int) == show (2 + 1 :: Repr Int) > False > > because: > show (1 + 2 :: Repr Int) == "1 + 2" > show (2 + 1 :: Repr Int) == "2 + 1" > > but note: > Prelude Text.Repr> (1 + 2 :: Repr Int) == (2 + 1 :: Repr Int) > True > > Bas > > [1] http://hackage.haskell.org/package/repr > ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
Re: new keyword: infixlr?
On Mon, Sep 13, 2010 at 4:23 PM, Nick Bowler wrote: > ... not all Num instances have an associative (+). Indeed: $ cabal install repr# [1] ... $ ghci Prelude> :m Text.Repr Prelude Text.Repr> show (1 + 2 :: Repr Int) == show (2 + 1 :: Repr Int) False because: show (1 + 2 :: Repr Int) == "1 + 2" show (2 + 1 :: Repr Int) == "2 + 1" but note: Prelude Text.Repr> (1 + 2 :: Repr Int) == (2 + 1 :: Repr Int) True Bas [1] http://hackage.haskell.org/package/repr ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
Re: new keyword: infixlr?
In message , "S. Doaitse Swierstra" writes: >Currently Haskell has infix, infixl and infixr operators. I see a use for infi >xlr as well. This indicates that the implemtation may assume the operator to b >e associative, and thus has the freedom to "balance" an expression containing >several operator occurrences. How would this compare with the GHC's RULES pragma? I think you might be able to express associativity with the rewrite rules? For example, GHC's Control.Category library already specifies associativity for the Category class in rewrite rules. It's not clear to me whether the rewrite rules allow the compiler to do this balancing in practice, but in principle the information content in the corresponding rewrite rule is the same. -- Esa Pulkkinen ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
Re: new keyword: infixlr?
On 2010-09-10 19:13 +0100, Ian Lynagh wrote: > 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 Of course, since I don't think fixity can be specified per-instance of Num, one would not be able to use this proposal for this; not all Num instances have an associative (+). -- Nick Bowler, Elliptic Technologies (http://www.elliptictech.com/) ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
Re: new keyword: infixlr?
I don't think a syntactic property (how operators are parsed) should be mixed up with a semantic property (being associative). At least not in Haskell. On Fri, Sep 10, 2010 at 7:51 PM, 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. > > 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). > > I admit it is probably a minor point, but given the increased use of "type > level" programming, and the use of cartesian products to keep "lists of > values of a different type", I can also see many good uses for this. > > Any comments? > > Doaitse > > > > ___ > 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
Re: new keyword: infixlr?
On Fri, Sep 10, 2010 at 11:14:53PM +0200, S. Doaitse Swierstra wrote: > > 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. I assume you mean "an associative operator", but even then it's not true for (.). And just because it is what you would expect, does not mean that people will only use it in that way if the type system does not enforce it! A detail is whether x ^^^ y = x ^ y infixlr ^^^ is rejected, or gives (^^^) :: (Num a, Integral a) => a -> a -> a Although I guess if you require the compiler to give you the balanced parse, there's no technical need to restrict the type of the operator as it's deterministic. Overall, my feeling is that this syntax feels very specialised and fiddly, and would be better handled by a more general machanism similar to GHC's RULE pragma, or by quasi-quotes or TH, or even by a domain specific optimiser plugin which can see the result of inlining etc. Thanks Ian ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
Re: new keyword: infixlr?
Am Freitag, den 10.09.2010, 23:18 +0200 schrieb S. Doaitse Swierstra: > On 10 sep 2010, at 20:13, Ian Lynagh wrote: > > 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. To me, it seems weird that optimization should be done at the level of syntax. Note that optimization would only trigger if you write concrete applications of the infix operator, not if you construct them programmatically. Best wishes, Wolfgang ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
Re: new keyword: infixlr?
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
Re: new keyword: infixlr?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 9/10/10 14:13 , Ian Lynagh wrote: > 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? That strikes me as a trivial application of the proposal; in Haskell it's not clear to me that there's a significant different between the two, thanks to laziness. - -- brandon s. allbery [linux,solaris,freebsd,perl] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH -BEGIN PGP SIGNATURE- Version: GnuPG v2.0.10 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkyKfvgACgkQIn7hlCsL25Xt7QCggYY7LvGcj+F8Or91931pPOQR OlIAoM0BwQt+/+MqDXGhoeIjCoBCnEo6 =Nh7X -END PGP SIGNATURE- ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
Re: new keyword: infixlr?
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 ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
new keyword: infixlr?
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. 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). I admit it is probably a minor point, but given the increased use of "type level" programming, and the use of cartesian products to keep "lists of values of a different type", I can also see many good uses for this. Any comments? Doaitse ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime