Re: [Haskell-cafe] Robert Harper on monads and laziness
2011/5/3 Manuel M T Chakravarty c...@cse.unsw.edu.au: Interestingly, today (at least the academic fraction of) the Haskell community appears to hold the purity of the language in higher regard than its laziness. I find Greg Morissett's comment on Lennart Augustsson's article pro lazy evaluation very interesting: http://augustss.blogspot.com/2011/05/more-points-for-lazy-evaluation-in.html#c7969361694724090315 What I find interesting is that he considers (non-)termination an effect, which Haskell does not manage to control like it does other types of effects. Dependently typed purely functional languages like Coq (or Agda if you prefer ;)) do manage to control this (at the cost of replacing general recursion with structural recursion) and require you to model non-termination in a monad (or Applicative functor) like in YNot or Agda's partiality monad (written _⊥) which models just non-termination. I have the impression that this separation of the partiality effect provides a certain independence of evaluation order which neither ML (because of side-effects) nor Haskell (because of non-strict semantics) manage to provide. Such an independence seems very useful for optimization and parallel purposes. Dominique ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Idea for Haddock: Specifying a syntax field when using template splicing
I just had an idea while I was working on a webserver in Haskell, where I not only enter Haskell code (obviously) but I also enter Javascript and CSS code in functions that use QuasiQuoting (i.e. TemplateHaskell). The idea is basically that with standard Haddock comments you can specify a 'tag' for function argument that has a QuasiQuoter as a type, the 'tag' specifying the syntax of the code inside of what is being spliced (for that specific function). The generated haddock documentation would then display the syntax tag for that specific function. The purpose for this would be that IDE's and Editors would pick up that the code going through the QuasiQuoter has a certain syntax, and the IDE/Editors can then apply syntax coloring (and indenting rules and whatnot) to that piece of code I guess this tag concept can be applied generally to any type of function (and any type of tag, not just tags for syntax) but there should be some standardization, (tag types especially should be static, tag values don't have to) Thoughts? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is Harper right that Haskell cannot model the natural numbers?
In this context, I'd suggest to have a look at the POPL'06 paper Fast and Loose Reasoning is Morally Correct http://www.comlab.ox.ac.uk/people/jeremy.gibbons/publications/fast+loose.pdf The paper is quite technical, so here the gist. It says that if you formally proof that two Haskell expressions do the same thing by reasoning *as if* you were using a total language (one without non-termination), then the two expressions are also morally the same in Haskell.[1] They formally define what morally the same means. In particular, the Introduction says: Our results justify the hand reasoning that functional programmers already perform, and can be applied in proof checkers and automated provers to justify ignoring ⊥-cases much of the time. In other words, yes, 'Nat' in Haskell is not the same as the natural numbers as axiomised by Peano. Does it matter? Not really. Manuel PS: Given that ML is impure, a lot of equational reasoning in ML is also no more than morally correct. [1] The paper doesn't show that statement for the entirety of Haskell, but for a core language with a comparable semantics using lifted types. Richard O'Keefe: In one of his blog posts, Robert Harper claims that the natural numbers are not definable in Haskell. SML datatype nat = ZERO | SUCC of nat Haskell data Nat = Zero | Succ Nat differ in that the SML version has strict constructors, and so only finite instances of nat can be constructed, whereas Haskell has lazy constructors, so inf = Succ inf is constructible, but that's not a natural number, and it isn't bottom either, so this is not a model of the natural numbers. Fair enough, but what about data Nat = Zero | Succ !Nat where the constructors *are* strict? It's perfectly good Haskell 98 as far as I can see. Now Nat itself isn't _quite_ a model of the naturals because it includes bottom, but then an SML function returning nat can also fail, so arguably SML's nat could or should be thought of as including bottom too. What am I missing? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Please add a method for optimized concat to the Semigroup class
Hi Edward, Thanks much for the very useful semigroups package. When using it in practice, it would be very useful to have an analogue to the mconcat method of Monoid. It has the obvious default implementation, but allows for an optimized implementation for specific instances. That turns out to be something that comes up all the time (at least for me) in real life. Thanks, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add a method for optimized concat to the Semigroup class
Does it have an obvious default implementation, bearing in mind it we might really want a total function? sconcat [] = error Yikes - I wish this was total! sconcat [a]= a sconcat (a:as) = a sconcat as Best wishes Stephen On 3 May 2011 12:12, Yitzchak Gale g...@sefer.org wrote: [SNIP] It has the obvious default implementation, but allows for an optimized implementation for specific instances. That turns out to be something that comes up all the time (at least for me) in real life. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add a method for optimized concat to the Semigroup class
Am 03.05.2011 um 13:39 schrieb Stephen Tetley: Does it have an obvious default implementation, bearing in mind it we might really want a total function? sconcat [] = error Yikes - I wish this was total! sconcat [a]= a sconcat (a:as) = a sconcat as You have to provide the neutral element by yourself: infixl 4 a [] = a a (b:bs) = a b bs Best wishes Stephen On 3 May 2011 12:12, Yitzchak Gale g...@sefer.org wrote: [SNIP] It has the obvious default implementation, but allows for an optimized implementation for specific instances. That turns out to be something that comes up all the time (at least for me) in real life. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add a method for optimized concat to the Semigroup class
There is that formulation, though usually I find I need to do it with an alternative instead: altconcat alt [] = alt altconcat _ (a:as) = go a as where go acc [] = acc go acc (b:bs) = go (acc b) bs Both are kind of, sort of bringing you up to a Monoid though... On 3 May 2011 12:56, Holger Siegel holgersiege...@yahoo.de wrote: You have to provide the neutral element by yourself: ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add a method for optimized concat to the Semigroup class
Stephen Tetley wrote: Does it have an obvious default implementation, bearing in mind it we might really want a total function? sconcat [] = error Yikes - I wish this was total! sconcat [a] = a sconcat (a:as) = a sconcat as Holger Siegel wrote: You have to provide the neutral element by yourself: a [] = a a (b:bs) = a b bs Yes, I think that would be the best interface. At first glance, one would be tempted to do something like returning a Maybe, as is often done in these kinds of cases. But here, the whole point of Semigroup is that we don't know what to do when the list is empty, so getting a Nothing result in that case is unhelpful. To illustrate the point, let's look at the conversion between those two approaches: sconcatNonempty x xs = fromJust . sconcat $ x : xs sconcatMaybe (x:xs) = Just $ sconcat x xs sconcatMaybe _ = Nothing I would much rather write sconcatMaybe when needed than to have to write unsafe code like sconcatNonempty. Presumably it's actually safe, since you would expect implementations to provide a result whenever the list is non-empty. But the type no longer provides that guarantee. Thanks, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add a method for optimized concat to the Semigroup class
Stephen Tetley wrote: There is that formulation, though usually I find I need to do it with an alternative instead: altconcat alt [] = alt altconcat _ (a:as) = go a as where go acc [] = acc go acc (b:bs) = go (acc b) bs But the whole reason we need this as a method is for the case that consecutive appends is inefficient. Both are kind of, sort of bringing you up to a Monoid though... altconcat and sconcatMaybe are doing that, because you need to decide what to do with an empty list when you define the instance. Holger's interface is not doing that, because the type does not require you to say anything about the case of an empty list in the instance. Another approach would be to depend on one of the packages that provides a non-empty list type, such as the NonEmptyList package. But I don't think this simple case justifies another dependency. You can wrap Holger's function in one of those types easily enough if you need to. Thanks, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Computational Semantics w/ Functional Programming, Jan van Eijck and Christina Unger, 2010. It's in #Haskell. :)
On Sat, Apr 30, 2011 at 21:21:04 -0400, cas...@istar.ca wrote: This may have already been mentioned but it is worth mentioning n times: Computational Semantics w/ Functional Programming, Jan van Eijck and Christina Unger, 2010. It's in #Haskell. :) Here's a link to the book homepage http://homepages.cwi.nl/~jve/cs/ You may also be interested in /Natural Language Processing for the Working Programmer/ by Daniël de Kok and Harm Brouwer, which is a work in progress http://nlpwp.org/book/ Finally, there is a small but growing community of people who are into Natural Language Processing and Haskell. We have a mailing list that you may want to sign up to http://projects.haskell.org/cgi-bin/mailman/listinfo/nlp Right now, people generally use the list for announcing their NLP and Computational Linguistics related Haskell packages. But the list could be much more! I think we're slowly creeping up to a point where the list will sort of explode into being. The thing I'm most looking forward to is people making combined use of packages, joining up work by two completely unrelated groups. -- Eric Kow http://www.nltg.brighton.ac.uk/home/Eric.Kow For a faster response, try +44 (0)1273 64 2905 or xmpp:ko...@jabber.fr (Jabber or Google Talk only) signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Fwd: Re: Binary and Serialize classes
-- Forwarded message -- De: Alberto G. Corona agocor...@gmail.com Fecha: 03/05/2011 11:24 Asunto: Re: [Haskell-cafe] Binary and Serialize classes Para: Antoine Latter aslat...@gmail.com E1610With the exception of heavy serialization usage, for example, in very optimized RPC applications (and even there SOAP shows that this is not ever the case), text serialization is better. The unwritten rules of good design says that data representation and compression must be orthogonal. The binary formats were designed for performing both functionalities in the times when memory were measured in Kbytes. 2011/4/28 Antoine Latter aslat...@gmail.com On Thu, Apr 28, 2011 at 10:00 AM, Evan Laforge ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Robert Harper on monads and laziness
On Tue, May 3, 2011 at 1:32 AM, Manuel M T Chakravarty c...@cse.unsw.edu.au wrote: ... Interestingly, today (at least the academic fraction of) the Haskell community appears to hold the purity of the language in higher regard than its laziness. As someone who implemented Haskell with quite a bit less laziness, I'm inclined to agree. That said, I think it's easy to underestimate just how much of the structure of the language really encourages a lazy evaluation strategy. One example: where blocks scope over groups of conditional RHSs. This is very handy, in that we can bind variables that are then used in some, but not all, of the disjuncts. Grabbing the first example that comes to hand from my own code: tryOne (gg, uu) e | not (consistent uu) = (gg', uu) | uu==uu' = (gg, uu) | otherwise = (gg', uu') where gg' = gg `addEquation` e uu' = uu `addEquation` e This kind of thing happens all over the place in Haskell code -- it's a very natural coding style -- but if you want to preserve purity it's tough to compile without laziness. -Jan-Willem Maessen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Please add instance Semigroup Text
Hi Edward, Could you please add a Semigroup instance for Text? Once you're doing that, I suppose you'd also want to add it for lazy Text and both kinds of ByteStrings. But what I currently need is strict Text. The reason, of course, is that in complex calculations is *so* much more readable than `mappend`. Obviously WrappedMonoid is useless there. Hmm, and now for Semigroup and Monoid we start down the same path as for Functor and Monad... Or should we give back to Monoid and use something different for Semigroup? That doesn't seem very nice either... Well, in the meantime, you really will make my life easier if you could add some more Semigroup instances for popular Monoids. Thanks, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is Harper right that Haskell cannot model the natural numbers?
Richard O'Keefe o...@cs.otago.ac.nz writes: In one of his blog posts, Robert Harper claims that the natural numbers are not definable in Haskell. SML datatype nat = ZERO | SUCC of nat Haskell data Nat = Zero | Succ Nat differ in that the SML version has strict constructors, and so only finite instances of nat can be constructed, whereas Haskell has lazy constructors, so inf = Succ inf is constructible, but that's not a natural number, and it isn't bottom either, so this is not a model of the natural numbers. I think Prof. Harper criticism is weak. Defining the set of natural numbers is not easy. What does he understand as natural number? Peano axioms fail in similar fashion given that PA has non standard models which include elements similar to your inf. You may used other approaches like second order logic or von Neumann ordinals, but they have their own set of drawbacks. Regards, Emilio ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add a method for optimized concat to the Semigroup class
On 3 May 2011 13:26, Yitzchak Gale g...@sefer.org wrote: Both are kind of, sort of bringing you up to a Monoid though... altconcat and sconcatMaybe are doing that, because you need to decide what to do with an empty list when you define the instance. Holger's interface is not doing that, because the type does not require you to say anything about the case of an empty list in the instance. Holger's interface is bringing you kind of, sort of up to a Monoid but it allows neutral of whatever value you fancy at the time. At which point, either you're working at directly at a type - so you don't really need the idea of a semigroup just its pretty () operator, or you do actually have a neutral and thus were working with a Monoid all along - again you just wanted the pretty () operator. My real contention is that Semigroup doesn't have a proper concat operation[*], though notationally it is seductive - I do use both altconcat and Holger's version in my own code. [*] I could be persuaded otherwise, but I can't see how it would be an analogue mconcat in Monoid. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add instance Semigroup Text
On Tue, May 3, 2011 at 8:00 AM, Yitzchak Gale g...@sefer.org wrote: Could you please add a Semigroup instance for Text? I'd strongly recommend writing an instance for the text package's Builder type instead. Vastly more efficient for non-trivial jobs. Once you're doing that, I suppose you'd also want to add it for lazy Text and both kinds of ByteStrings. Likewise, there's allegedly work afoot to write a builder for bytestrings. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add instance Semigroup Text
On Tue, May 3, 2011 at 12:04 PM, Bryan O'Sullivan b...@serpentine.comwrote: On Tue, May 3, 2011 at 8:00 AM, Yitzchak Gale g...@sefer.org wrote: Could you please add a Semigroup instance for Text? I'd strongly recommend writing an instance for the text package's Builder type instead. Vastly more efficient for non-trivial jobs. Unfortunately, I don't think I can really bring myself to do either. I was deliberately trying to keep the number of dependencies for the semigroups as low as possible in contrast to my previous efforts. In fact, I'll likely invert the dependencies from tagged and void, leaving only the dependency on containers, which is somewhat unavoidable, but still Haskell 98. My goal was to build a very small standardizable library. Data.Text requires dependencies that would take my package and a whole hierarchy of other Haskell 98 packages that are built on top of it, out of Haskell 98. -Edward Once you're doing that, I suppose you'd also want to add it for lazy Text and both kinds of ByteStrings. Likewise, there's allegedly work afoot to write a builder for bytestrings. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add a method for optimized concat to the Semigroup class
On Tue, May 3, 2011 at 7:12 AM, Yitzchak Gale g...@sefer.org wrote: Hi Edward, Thanks much for the very useful semigroups package. When using it in practice, it would be very useful to have an analogue to the mconcat method of Monoid. It has the obvious default implementation, but allows for an optimized implementation for specific instances. That turns out to be something that comes up all the time (at least for me) in real life. Thanks, Yitz I had considered an sconcat :: [a] - a - a with either the semantics you supplied or something like sconcat = appEndo . mconcat . map diff But it was somewhat unsatisfying, in part because of the need for a seed element. Another unsatisfying detail is no definition is in any way shape or form canonical when folding over a list. There are at least 3 definitions that make sense. The nice inductive Endo definition above (which differs in semantics from the one you proposed), something like what you propose, with its funny base case, and the option of placing something like the unit I placed in Endo on the other side. Finally, I wasn't able to get any such specialized sconcat to actually speed anything up. =/ I'm more than happy to revisit this decision, as it isn't particularly onerous to add an sconcat definition to Semigroup, but I've yet to see it pay off and it is somewhat disturbing to me that the type doesn't automatically offer up its meaning. As the Prelude has a general dearth of suitable container types that contain a guarantee of at least one element, my focus was instead upon the use of Foldable1 and Traversable1 from the semigroupoids package. This provides an optimization path, similar to those of Foldable and Traversable by optimizing the non-empty-by-construction *container* for its use of a semigroup, rather than optimizing the semigroup for its use of by one particularly inappropriate container. http://hackage.haskell.org/packages/archive/semigroupoids/1.1.2/doc/html/Data-Semigroup-Foldable.html http://hackage.haskell.org/packages/archive/semigroupoids/1.1.2/doc/html/Data-Semigroup-Traversable.html These offer up a wealth of combinators for manipulating Semigroups over suitable containers. Again, I'm more than happy to add it if only for symmetry with Data.Monoid, but I'd be much happier doing so with a compelling example where it actually sped things up, and if there was actually a better motivated inductive definition. -Edward ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: Leksah 0.10.0
On 03/05/2011 02:49, Mathew de Detrich wrote: The best thing that Leksah can turn into (and something that Haskell desperately needs) is a Haskell version of Eclipse, because as Java has a weakness of being incredibly verbose (which Eclipse gets around with very easily, try coding Java in vim!!!), Haskell being a statically typed language has a weakness that in non trivial code, types can become convoluted and 'piping' functions together becoming complicated, something that a very smart code completion along with very powerful refactoring techniques that Eclipse has would do wonders. The one thing that Haskell is missing is a proper editing environment, and at least in my opinion one of the major things that a language needs to become widely adopted (unless its a first like perl,C was) is a proper editing environment that is approachable for newer people but remains powerful for advanced users There is a Haskell version of eclipse - eclipsefp. (Unless you specifically meant an Eclipse written in Haskell.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add a method for optimized concat to the Semigroup class
Edward Kmett wrote: sconcat :: [a] - a - a with either the semantics you supplied or something like sconcat = appEndo . mconcat . map diff The sconcat we have been discussing is sconcat = flip $ appEndo . getDual . mconcat . map (Dual . Endo . flip ()) (avoiding the use of Dual.diff.Dual so that we don't need to define dualUnDual or some such messiness) But it was somewhat unsatisfying, in part because of the need for a seed element. Only because, as you said, there is no standard non-empty list type. Another unsatisfying detail is no definition is in any way shape or form canonical when folding over a list. While our definition doesn't look any better than the others when expressed in terms of those combinators, it certainly seems to be the most natural when defined directly as Holger did. It's also the direct analogue of mconcat when viewed as the same type with lists replaced by non-empty lists. I'm sure that's the definition most users will expect. But I would be happy with whichever you supply. ...I'm more than happy to add it if only for symmetry with Data.Monoid, but I'd be much happier doing so with a compelling example where it actually sped things up I'm currently doing some recognition algorithms on heterogeneous collections of graphical elements on a 2D canvas. Many types of elements have a location and a rectangular extent. You can often combine them, but there is no unit element because even an empty element needs to have a specific location. It would be very slow to combine a list of them incrementally; instead, you find the minimum and maximum X and Y coordinates, and combine the content using a fast algorithm. (I originally used Monoid instances by augmenting types with locationless empty elements. But that made a mess of my code and introduced a myriad of bugs and potential crashes. These are definitely semigroups, not monoids.) I'm sure there are countless other natural examples of semigroups in the wild, and that the typical non-trivial ones will benefit from an optimized sconcat. Thanks, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Functional dependencies and Peano numbers (and hoogle-bug?)
Hi Oscar, Sorry for the seriously late reply. I only just found this message in the bottom of my inbox: On an unrelated note: I hoogled to (i.e. http://haskell.org/hoogle/?hoogle=to) and just got a blank page. Nothing. Nil (not even html.../html). Is this a bug or a feature? :) It was a bug, fixed in hoogle-4.2.1. I had an incomplete pattern match on to, which crashed Hoogle. The reason to is treated specially is that when people search for a to b, they usually mean a - b, and my code to detect this was incorrect. All fixed now. Thanks for the report. In future, if you find a bug in Hoogle can you please email me directly, or raise it on my bug tracker: http://code.google.com/p/ndmitchell/issues/ Thanks, Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Crypto-api performance
Does anyone have experience with the crypto-api package? It seems to define a nice common API for block ciphers, hash functions and prng's. However, I get very low performance using it. I ran its benchmark on a NOP block cipher, where encryptBlock k = id, and it's still very slow. After expanded the included block cipher benchmark (which uses ECB) to include CBC and CTR I got the following: ECB: 30 MB/s -- somewhat slow CBC: 12 MB/s -- very slow CTR: 4 MB/s -- why is adding a counter so bad? Have anyone else benchmarked this and if so with what results? Are there any other high level crypto API? Here's my benchmark code for CTR (easily modified to use ECB/CBC): https://gist.github.com/954093 And here's my patched Benchmark/Crypto.hs: https://gist.github.com/954099 Package in question: http://hackage.haskell.org/package/crypto-api -- Johan Brinch, Dept. of Computer Science, University of Copenhagen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add instance Semigroup Text
I wrote: Could you please add a Semigroup instance for Text? Edward Kmett wrote: Unfortunately, I don't think I can really bring myself to do either. I was deliberately trying to keep the number of dependencies for the semigroups as low as possible... You are quite right. These should really be defined in their respective packages. I don't think it's too onerous for them to add a dependency on semigroups, even before you reverse the few lightweight dependencies that semigroups has. Bryan O'Sullivan wrote: I'd strongly recommend writing an instance for the text package's Builder type instead. Vastly more efficient for non-trivial jobs. Well, in my case, I'm iterating over many small Texts, slicing and dicing small groups of them in various ways to look for overlaps, and splicing the pieces back together in different combinations. It's quite fast as it is; what I'm looking for is to make the formulas look simpler and more understandable. I doubt that builders will be any help for that. Whereas using from semigroups instead of `T.append` or `mappend` is a huge help. Apart from my own use case, semigroups are a simple and fundamental idiom that I think will become much more widely used as people become more aware of them. Just like every Monad should have a Functor instance, every Monoid should have a Semigroup instance. Thanks, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Crypto-api performance
On Tuesday 03 May 2011 22:05:17, Johan Brinch wrote: Does anyone have experience with the crypto-api package? It seems to define a nice common API for block ciphers, hash functions and prng's. However, I get very low performance using it. I ran its benchmark on a NOP block cipher, where encryptBlock k = id, and it's still very slow. After expanded the included block cipher benchmark (which uses ECB) to include CBC and CTR I got the following: ECB: 30 MB/s -- somewhat slow CBC: 12 MB/s -- very slow CTR: 4 MB/s -- why is adding a counter so bad? Have anyone else benchmarked this and if so with what results? Neither benchmarked nor used it, but just to make sure: did you notice that the comment says 128KB strings for ps and lps, but they are in fact 1MB strings: -- 128KB strings ps = B.replicate (2^20) 0 lps = L.replicate (2^20) 0 ? If not, the throughput would look much better, wouldn't it? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add instance Semigroup Text
On Tue, May 3, 2011 at 1:14 PM, Yitzchak Gale g...@sefer.org wrote: You are quite right. These should really be defined in their respective packages. I don't think it's too onerous for them to add a dependency on semigroups, even before you reverse the few lightweight dependencies that semigroups has. Unfortunately, the semigroups package will have to go into the Platform before either text or bytestring can make use of it. I think that would be great to have, but the getting from here to there is not necessarily fun. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add instance Semigroup Text
Getting stuff into the HP is a different problem, and something I'm working on addressing in coming weeks... stay tuned. On Tue, May 3, 2011 at 2:33 PM, Bryan O'Sullivan b...@serpentine.com wrote: On Tue, May 3, 2011 at 1:14 PM, Yitzchak Gale g...@sefer.org wrote: You are quite right. These should really be defined in their respective packages. I don't think it's too onerous for them to add a dependency on semigroups, even before you reverse the few lightweight dependencies that semigroups has. Unfortunately, the semigroups package will have to go into the Platform before either text or bytestring can make use of it. I think that would be great to have, but the getting from here to there is not necessarily fun. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Robert Harper on monads and laziness
On Tue, May 3, 2011 at 2:26 AM, Dominique Devriese
dominique.devri...@cs.kuleuven.be wrote:
What I find interesting is that he considers (non-)termination an
effect, which Haskell does not manage to control like it does other
types of effects. Dependently typed purely functional languages like
Coq (or Agda if you prefer ;)) do manage to control this (at the cost
of replacing general recursion with structural recursion) and require
you to model non-termination in a monad (or Applicative functor) like
in YNot or Agda's partiality monad (written _⊥) which models just
non-termination.
Dependent typing isn't really necessary. Only totality. Of course,
there's some agreement that dependent types help you get back some of
the power you'd lose by going total (by helping you write precise
enough types for your programs to be accomplished in the more limited
recursive manner).
I have the impression that this separation of the partiality effect
provides a certain independence of evaluation order which neither ML
(because of side-effects) nor Haskell (because of non-strict
semantics) manage to provide. Such an independence seems very useful
for optimization and parallel purposes.
Total lambda calculi tend to yield the same results irrespective of
evaluation strategy. I guess that's useful for optimization, because
you can apply transformations wherever you want without worrying about
changing the definedness of something (because everything is
guaranteed to be well defined regardless of your evaluation strategy).
I don't see how it obviates strictness analysis, though. For instance:
sumAcc a (x:xs) = sumAcc (a + x) xs
sumAcc a [] = a
... case sumAcc 0 l of { n - ... }
Even in a total language, accumulating lazy thunks is likely to be
inefficient for when we go to use the accumulator, whereas one can
also construct examples (even in a total and inductive fragment) where
lazy evaluation will be superior. So you need to do analysis to
determine which things should be strict and which should be lazy for
efficiency, even if you aren't obligated to do it to determine whether
your optimizations are semantics-preserving.
-- Dan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Advertisement: the Haskell Stack Overflow Q A site
Hey all, I thought I'd just make a quick advertisement for the Haskell Stack Overflow community: http://stackoverflow.com/questions/tagged/haskell as a forum for questions and answers on beginner to advanced Haskell problems. The site is very active, with roughly as many questions being asked on SO as on haskell-cafe these days. One of the benefits of a site like SO as a forum is the ability to record and link to prior work, edit for technical errors, and easily search and categorize past answers. It is also less prone to noise, for those suffering from cafe overload. Cheers, Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Advertisement: the Haskell Stack Overflow Q A site
On Tue, May 3, 2011 at 3:00 PM, Don Stewart don...@gmail.com wrote: Hey all, I thought I'd just make a quick advertisement for the Haskell Stack Overflow community: http://stackoverflow.com/questions/tagged/haskell as a forum for questions and answers on beginner to advanced Haskell problems. The site is very active, with roughly as many questions being asked on SO as on haskell-cafe these days. One of the benefits of a site like SO as a forum is the ability to record and link to prior work, edit for technical errors, and easily search and categorize past answers. It is also less prone to noise, for those suffering from cafe overload. I would also recommend SO. If you have trouble following along you can also use twitter to see when new Haskell questions are posted: http://twitter.com/#!/haskellstoverfl Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add instance Semigroup Text
On Tue, May 3, 2011 at 3:14 PM, Yitzchak Gale g...@sefer.org wrote: I wrote: Could you please add a Semigroup instance for Text? Edward Kmett wrote: Unfortunately, I don't think I can really bring myself to do either. I was deliberately trying to keep the number of dependencies for the semigroups as low as possible... You are quite right. These should really be defined in their respective packages. I don't think it's too onerous for them to add a dependency on semigroups, even before you reverse the few lightweight dependencies that semigroups has. Bryan O'Sullivan wrote: I'd strongly recommend writing an instance for the text package's Builder type instead. Vastly more efficient for non-trivial jobs. Well, in my case, I'm iterating over many small Texts, slicing and dicing small groups of them in various ways to look for overlaps, and splicing the pieces back together in different combinations. It's quite fast as it is; what I'm looking for is to make the formulas look simpler and more understandable. I doubt that builders will be any help for that. Whereas using from semigroups instead of `T.append` or `mappend` is a huge help. Can you locally define an operator () for monoids? Apart from my own use case, semigroups are a simple and fundamental idiom that I think will become much more widely used as people become more aware of them. Just like every Monad should have a Functor instance, every Monoid should have a Semigroup instance. Thanks, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add a method for optimized concat to the Semigroup class
On Tue, May 3, 2011 at 3:43 PM, Yitzchak Gale g...@sefer.org wrote: Edward Kmett wrote: sconcat :: [a] - a - a with either the semantics you supplied or something like sconcat = appEndo . mconcat . map diff The sconcat we have been discussing is sconcat = flip $ appEndo . getDual . mconcat . map (Dual . Endo . flip ()) Holger's basically had this form, but I think Tetley's version is more useful, because it provides for the scenario you describe below where there is no value of the semigroup's type that you can merge with. But it was somewhat unsatisfying, in part because of the need for a seed element. Only because, as you said, there is no standard non-empty list type. I have a streams package which provides a number of non-empty list types, but it is fairly high up my module hierarchy, as it requires a number of compiler extensions, and other classes, and so isn't available to the class down here in the semigroups package. Another unsatisfying detail is no definition is in any way shape or form canonical when folding over a list. While our definition doesn't look any better than the others when expressed in terms of those combinators, it certainly seems to be the most natural when defined directly as Holger did. It's also the direct analogue of mconcat when viewed as the same type with lists replaced by non-empty lists. I'm sure that's the definition most users will expect. But I would be happy with whichever you supply. ...I'm more than happy to add it if only for symmetry with Data.Monoid, but I'd be much happier doing so with a compelling example where it actually sped things up I'm currently doing some recognition algorithms on heterogeneous collections of graphical elements on a 2D canvas. Many types of elements have a location and a rectangular extent. You can often combine them, but there is no unit element because even an empty element needs to have a specific location. It would be very slow to combine a list of them incrementally; instead, you find the minimum and maximum X and Y coordinates, and combine the content using a fast algorithm. This is a pretty good example. Even if in this case it is mostly saving you the boxing and unboxing of the intermediate rectangles You still probably want something closer to Stephen Tetley's version, otherwise you're going to have to magic up just that kind of empty rectangle that you don't want to give though! In fact you probably want something even stronger, that way you can signal the empty list result 'out of band' of the values you can fit in the Semigroup. This would avoid specifying an alternative directly, and his case can be derived with sconcat :: Semigroup a = [a] - Maybe a sconcat [] = Nothing sconcat (a:as) = Just (go a as) where go a (b:bs) = gs (ab) bs go a [] = a and effectively avoids fiddling with the empty case throughout the list. Then Stephen's version would look like tetley :: Semigroup a = a - [a] - a tetley alt = maybe alt id . sconcat Alternately Option could be used instead of Maybe to keep the package's API more self-contained, but I don't particularly care one way or the other. (I originally used Monoid instances by augmenting types with locationless empty elements. But that made a mess of my code and introduced a myriad of bugs and potential crashes. These are definitely semigroups, not monoids.) I'm sure there are countless other natural examples of semigroups in the wild, and that the typical non-trivial ones will benefit from an optimized sconcat. Sold! (modulo the semantic considerations above) -Edward ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Please add a method for optimized concat to the Semigroup class
Another option (upon reflection) would be to just transplant the NonEmpty type from http://hackage.haskell.org/packages/archive/streams/0.6.1.1/doc/html/Data-Stream-NonEmpty.html data NonEmpty a = a :| [a] http://hackage.haskell.org/packages/archive/streams/0.6.1.1/doc/html/Data-Stream-NonEmpty.htmlinto the semigroups package, which would give you the 'canonical non empty list' you seem to want. and then add the more pleasing and natural generalization sconcat:: NonEmpty a - a to the Semigroup class All I would need is to strip out the use of PatternGuards in a couple of locations. I would have to sprinkle a lot of instances through other packages on the way up the package tree NonEmpty isn't the most natural inductive version (Data.Stream.Future has that distinction), but it does implement efficiently and it can cheaply interconvert to [a]. -Edward On Tue, May 3, 2011 at 6:49 PM, Edward Kmett ekm...@gmail.com wrote: On Tue, May 3, 2011 at 3:43 PM, Yitzchak Gale g...@sefer.org wrote: Edward Kmett wrote: sconcat :: [a] - a - a with either the semantics you supplied or something like sconcat = appEndo . mconcat . map diff The sconcat we have been discussing is sconcat = flip $ appEndo . getDual . mconcat . map (Dual . Endo . flip ()) Holger's basically had this form, but I think Tetley's version is more useful, because it provides for the scenario you describe below where there is no value of the semigroup's type that you can merge with. But it was somewhat unsatisfying, in part because of the need for a seed element. Only because, as you said, there is no standard non-empty list type. I have a streams package which provides a number of non-empty list types, but it is fairly high up my module hierarchy, as it requires a number of compiler extensions, and other classes, and so isn't available to the class down here in the semigroups package. Another unsatisfying detail is no definition is in any way shape or form canonical when folding over a list. While our definition doesn't look any better than the others when expressed in terms of those combinators, it certainly seems to be the most natural when defined directly as Holger did. It's also the direct analogue of mconcat when viewed as the same type with lists replaced by non-empty lists. I'm sure that's the definition most users will expect. But I would be happy with whichever you supply. ...I'm more than happy to add it if only for symmetry with Data.Monoid, but I'd be much happier doing so with a compelling example where it actually sped things up I'm currently doing some recognition algorithms on heterogeneous collections of graphical elements on a 2D canvas. Many types of elements have a location and a rectangular extent. You can often combine them, but there is no unit element because even an empty element needs to have a specific location. It would be very slow to combine a list of them incrementally; instead, you find the minimum and maximum X and Y coordinates, and combine the content using a fast algorithm. This is a pretty good example. Even if in this case it is mostly saving you the boxing and unboxing of the intermediate rectangles You still probably want something closer to Stephen Tetley's version, otherwise you're going to have to magic up just that kind of empty rectangle that you don't want to give though! In fact you probably want something even stronger, that way you can signal the empty list result 'out of band' of the values you can fit in the Semigroup. This would avoid specifying an alternative directly, and his case can be derived with sconcat :: Semigroup a = [a] - Maybe a sconcat [] = Nothing sconcat (a:as) = Just (go a as) where go a (b:bs) = gs (ab) bs go a [] = a and effectively avoids fiddling with the empty case throughout the list. Then Stephen's version would look like tetley :: Semigroup a = a - [a] - a tetley alt = maybe alt id . sconcat Alternately Option could be used instead of Maybe to keep the package's API more self-contained, but I don't particularly care one way or the other. (I originally used Monoid instances by augmenting types with locationless empty elements. But that made a mess of my code and introduced a myriad of bugs and potential crashes. These are definitely semigroups, not monoids.) I'm sure there are countless other natural examples of semigroups in the wild, and that the typical non-trivial ones will benefit from an optimized sconcat. Sold! (modulo the semantic considerations above) -Edward ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Robert Harper on monads and laziness
I completely agree that laziness enables a number of nice coding idioms and, as Lennart described so eloquently, it does facilitate a combinator-based coding style among other things: http://augustss.blogspot.com/2011/05/more-points-for-lazy-evaluation-in.html (Note that even Bob admits that this is an advantage.) What I meant is that if asked what is more important about Haskell, its laziness or purity, I think most people would pick purity. (But then it's a strange decision to make as laziness implies a need for purity as discussed.) Manuel Jan-Willem Maessen: On Tue, May 3, 2011 at 1:32 AM, Manuel M T Chakravarty c...@cse.unsw.edu.au wrote: ... Interestingly, today (at least the academic fraction of) the Haskell community appears to hold the purity of the language in higher regard than its laziness. As someone who implemented Haskell with quite a bit less laziness, I'm inclined to agree. That said, I think it's easy to underestimate just how much of the structure of the language really encourages a lazy evaluation strategy. One example: where blocks scope over groups of conditional RHSs. This is very handy, in that we can bind variables that are then used in some, but not all, of the disjuncts. Grabbing the first example that comes to hand from my own code: tryOne (gg, uu) e | not (consistent uu) = (gg', uu) | uu==uu' = (gg, uu) | otherwise = (gg', uu') where gg' = gg `addEquation` e uu' = uu `addEquation` e This kind of thing happens all over the place in Haskell code -- it's a very natural coding style -- but if you want to preserve purity it's tough to compile without laziness. -Jan-Willem Maessen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Filtering / branching enumeratee
Hello, I am using enumerator-0.4.10, and I need to distribute processing of different parts of the incoming stream to different iteratees (I am parsing a huge XML file, and different sub-trees have different processing logic). Only a single iteratee will be active at a time since the sub-trees don't intersect. I wrote a simple example that filters the stream and passes the result to one iteratee; please see below. However, with multiple nested iteratees it seems to me that I can no longer use an enumeratee. Do I need to write my own multi-enumeratee that holds multiple inner iteratees? Any better ideas? Here is my (beginner's) code for a single nested iteratee: module Main ( main ) where import qualified Data.Enumerator as E ( Enumeratee, Step(..), Stream(..), checkDone, checkDoneEx, continue, enumList, joinI, run_, yield ) import Data.Enumerator ( ($$), (==) ) import qualified Data.Enumerator.List as EL ( consume ) -- cribbed from EL.concatMap concatMapAccum :: Monad m = (s - ao - (s, [ai])) - s - E.Enumeratee ao ai m b concatMapAccum f s0 = E.checkDone (E.continue . step s0) where step _ k E.EOF = E.yield (E.Continue k) E.EOF step s k (E.Chunks xs) = loop s k xs loop s k [] = E.continue (step s k) loop s k (x:xs) = case f s x of (s', ais) - k (E.Chunks $ ais) == E.checkDoneEx (E.Chunks xs) (\k' - loop s' k' xs) passFromTo :: Monad m = ((a - Bool), (a - Bool)) - Bool - E.Enumeratee a a m b passFromTo (from, to) pass0 = concatMapAccum updatePass pass0 where updatePass pass el = case (pass, from el, to el) of (True, _, to_el) - (not to_el, [el]) (False, True, _) - (True, [el]) (False, False, _) - (False, []) main :: IO() main = do E.run_ (E.enumList 3 [1..20] $$ E.joinI $ passFromTo ((\e - e == 3 || e == 13), (\e - e == 7 || e == 17)) False $$ EL.consume) = print $ ./dist/build/StatefulEnumeratee/StatefulEnumeratee [3,4,5,6,7,13,14,15,16,17] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: Leksah 0.10.0
Well I kind of meant an eclipse type of IDE tailored for Haskell programming (with complete refactoring and code completion for the Haskell language) On Wed, May 4, 2011 at 4:45 AM, John Smith volderm...@hotmail.com wrote: On 03/05/2011 02:49, Mathew de Detrich wrote: The best thing that Leksah can turn into (and something that Haskell desperately needs) is a Haskell version of Eclipse, because as Java has a weakness of being incredibly verbose (which Eclipse gets around with very easily, try coding Java in vim!!!), Haskell being a statically typed language has a weakness that in non trivial code, types can become convoluted and 'piping' functions together becoming complicated, something that a very smart code completion along with very powerful refactoring techniques that Eclipse has would do wonders. The one thing that Haskell is missing is a proper editing environment, and at least in my opinion one of the major things that a language needs to become widely adopted (unless its a first like perl,C was) is a proper editing environment that is approachable for newer people but remains powerful for advanced users There is a Haskell version of eclipse - eclipsefp. (Unless you specifically meant an Eclipse written in Haskell.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
