- Haskell-Cafe - Haskell.org

re: generics and grammars
by Greg Meredith 13 Dec '07

13 Dec '07

Ken, Thanks for the references! Have two-level types been applied to parser generation? Best wishes, --greg Greg Meredith <lgreg.meredith(a)biosimilarity.com> wrote in article <5de3f5ca0712111100l79ec280fl1d828b12125abbdc(a)mail.gmail.com > > in gmane.comp.lang.haskell.cafe: > > Here is an idea so obvious that someone else must have already thought > of it > > and worked it all out. Consider the following grammar. > > Hello! > > If I understand your basic idea correctly, it is to split a recursive > data type into two parts, a non-recursive type constructor and a > knot-tying recursive type. This idea has been christened "two-level > types" by > > Tim Sheard and Emir Pasalic. 2004. Two-level types and > parameterized modules. Journal of Functional Programming > 14(5):547-587. > > The idea dates earlier, to initial-algebra semantics and "functional > programming with bananas and lenses": > > Mark P. Jones. 1995. Functional programming with overloading and > higher-order polymorphism. In Advanced functional programming: > 1st international spring school on advanced functional programming > techniques, ed. Johan Jeuring and Erik Meijer, 97-136. Lecture > Notes in Computer Science 925. > http://web.cecs.pdx.edu/~mpj/pubs/springschool.html<http://web.cecs.pdx.edu/%7Empj/pubs/springschool.html> > > Erik Meijer, Maarten Fokkinga, and Ross Paterson. 1991. Functional > programming with bananas, lenses, envelopes and barbed wire. In > Functional programming languages and computer architecture: 5th > conference, ed. John Hughes, 124-144. Lecture Notes in Computer > Science 523. > http://research.microsoft.com/~emeijer/Papers/fpca91.pdf<http://research.microsoft.com/%7Eemeijer/Papers/fpca91.pdf> > > Cheers, > Ken > Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

2 1

parsebinaryoperations
by Ryan Bloor 13 Dec '07

13 Dec '07

hi I have a function parseInt... which needs an error guard for when the input is not an Int. parseInt :: ParserparseInt [] = []parseInt xs = let (digits, rest) = span isDigit (removeSpace xs) in [(EInt (read digits), removeSpace rest)] Also... I have a function that does this... parseBinaryOp "+" "(5 + 2) if" gives...[(Int 5, Int 2, "if")] so, op is '+' or "&&". I am unsure of how to begin... parseBinaryOp :: String -> String -> [(Expr, Expr, String)]parseBinaryOp op str Thankyou Ryan _________________________________________________________________ Celeb spotting – Play CelebMashup and win cool prizes https://www.celebmashup.com

3 2

Not sure where to send this: delivery failure to community.haskell.org
by Magnus Therning 13 Dec '07

13 Dec '07

I received the following response when sending an email to admin(a)community.haskell.org This is an automatically generated Delivery Status Notification THIS IS A WARNING MESSAGE ONLY. YOU DO NOT NEED TO RESEND YOUR MESSAGE. Delivery to the following recipient has been delayed: support(a)community.haskell.org Message will be retried for 2 more day(s) Technical details of temporary failure: TEMP_FAILURE: Could not initiate SMTP conversation with any hosts: [community.haskell.org (1): Connection refused] The email was sent from my gmail account (magnus.therning(a)gmail.com) but with from: set to magnus(a)therning.org. I wonder if that could be the cause of the problem (I've noticed I'm unable to post to any of the haskell mailing lists that way). /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus．therning＠gmail．com http://therning.org/magnus In order to understand recursion you must first understand recursion.

2 1

ANNOUNCE: dataenc-0.10.1
by Magnus Therning 12 Dec '07

12 Dec '07

Yesterday I uploaded a small update to the dataenc library: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dataenc-0.10.1 Dependencies base License LGPL Copyright Magnus Therning, 2007 Author Magnus Therning Maintainer magnus(a)therning.org Exposed modules Codec.Binary.DataEncoding, Codec.Binary.Base16, Codec.Binary.Base32Hex, Codec.Binary.Base32, Codec.Binary.Uu, Codec.Binary.Base64Url, Codec.Binary.Base64 The visible change is the addition of a function, decode', that allows lazier decoding by shifting some responisility to the user. /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus．therning＠gmail．com http://therning.org/magnus Time is a great teacher, but unfortunately it kills all its pupils. -- Hector Louis Berlioz

2 1

Folding Integrals
by Mattias Bengtsson 12 Dec '07

12 Dec '07

I found myself writing this for an Euler-problem: > digits :: Int -> [Int] > digits i | i < 10 = [i] > | otherwise = i `mod` 10 : digits ( i `div` 10 ) And i realised it was quite some time ago (before this function) i had actually written any explicitly recursive function. I managed to finish the Euler problem however and i was happy about that. However it frustrated me that i couldn't find a nice way to abstract away that explicit recursion but today i managed to! :) My first thought was that the solution probably was using some function like scanr, mapAccum or unfoldr to do it (especially the name of unfoldr made me think that it would be the solution). After abstracting my digits function i realised that it wasn't anything more than a fold over the Int type (treating the Int as a sequence of digits). "i `mod` 10" and "i `div` 10" would be nothing more than the head and tail functions (that corresponds to the (:) pattern matching). This is what i came up with finally: (I'm not 100% sure on the foldr- and foldl names though. Not sure if the semantics are correct, perhaps the function names should be switched?) > module FoldIntegral (foldr, foldl) where > import Prelude hiding (foldr,foldl,head,tail) > > head, tail :: Integral a => a -> a > head i = i `mod` 10 > tail i = i `div` 10 > > foldr :: Integral a => (a -> b -> b) -> b -> a -> b > foldr f z i > | i == 0 = z > | otherwise = foldr f (h `f` z) t > where h = head i > t = tail i > > foldl :: Integral b => (a -> b -> a) -> a -> b -> a > foldl f z i > | i == 0 = z > | otherwise = (foldl f z t) `f` h > where h = head i > t = tail i Which would make the digits function a one-liner: > digits = foldr (:) [] I hope someone enjoys this. Mattias

6 6

ANNOUNCE: A ReadP style parser for ByteStrings
by Gracjan Polak 12 Dec '07

12 Dec '07

I'm happy to announce a ReadP style parser for ByteStrings, Text.ParserCombinators.ReadP.ByteString. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bytestringreadp Text.ParserCombinators.ReadP.ByteString is an adaptation of Text.ParserCombinators.ReadP to work over Data.ByteString as input stream representation. This gives enormous improvements in terms of parsing speed but most significantly in memory usage. Features: * ReadP style parser over ByteString input * Drop-in replacement for Text.ParserCombinators.ReadP * Fast * Good memory usage The algorithm is slightly modified to exploit ByteString as random access data input structure. Unlike original ReadP, that stressed garbage collection very much by creating a lot of conses (:), this parser has very good memory allocation behaviour. Package works out of the box with GHC 6.8.1, with slight (cabal) modifications also with GHC 6.6.1. Thanks to everyone for their support! Happy hacking! -- Gracjan

2 1

announcing darcs 2.0.0pre1, the first prerelease for darcs 2
by David Roundy 12 Dec '07

12 Dec '07

We are happy to announce the first prerelease version of darcs 2! Darcs 2 will feature numerous improvements, and this prerelease will also feature a few regressions, so we're looking for help, from both Haskell developers and users willing to try this release out. Read below, to see how you can benefit from this new release, and how you can help us to make the final darcs 2 release the best ever! (for the latter, see http://wiki.darcs.net/index.html/DarcsTwo/HowToHelp) (for an expanded version of this announcement, see http://wiki.darcs.net/index.html/DarcsTwo) Darcs 2 features user-visible changes two broad categories, and several under-the-hood improvements designed to improve code stability and safety. The user-visible changes are a new "hashed" repository format, and the new darcs-2 conflict handling. The new "hashed" repository format can be used in a manner that is interchangeable with older darcs--although older versions of darcs cannot read the hashed format, darcs 2 can allows you to exchange patches between repositories in new and old formats. The new conflict handling benefits from the new hashed format, but also requires a repository conversion that is not backwards-compatible, so projects switching to darcs-2 format will have require that all their users upgrade to darcs 2. === Getting darcs 2 === You can get a prerelease version of darcs 2 either by getting the latest unstable darcs darcs get http://darcs.net/repos/unstable or by downloading the prerelease tarball from http://darcs.net/darcs-2.0.0pre1.tar.gz. Once you've compiled your new darcs, you could take it for a test drive by getting a fresh copy of darcs with the hashed repository format: darcs get http://darcs.net/repos/unstabled-hashed = Hashed repository format = We expect that most testers of darcs 2 will only try the hashed repository format. While we'd prefer to also have many users testing out actual darcs-2 format repositories, the two codebases have much in common, so tests of the hashed format will greatly help us in improving darcs 2 as a whole. The hashed repository format has a number of changes that are visible to users. 1. The hashed format allows for greater atomicity of operations. This makes for greater safety and simultaneously greater efficiency. These benefits, however, have not been fully realized in this release. For instance, with a hashed repository, there is no need for darcs push to require a repository lock, so you could record patches while waiting for a push to finish (for instance, if it's waiting on the test suite). 2. The _darcs/pristine directory no longer holds the pristine cache. This disallows certain hackish short-cuts, but also dramatically reduces the danger of third-party programs (e.g. DreamWeaver) recursing into the pristine cache and corrupting darcs repositories. 3. Darcs get is now much faster, and always operates in a "lazy" fashion, meaning that patches are downloaded only when they are needed. This gives us much of the benefits of --partial repositories, without most of their disadvantages. This approach, however, does have several new dangers. First, some operations may unexpectedly require the download of large numbers of patches, which could be slow (but you could always interrupt with ^C). Secondly, if the source repository disappears, or you lose network connectivity, some operations may fail. I do not believe these dangers will prove particularly problematic, but we may need to fine-tune the user interface to make it more clear what is going on. 4. Darcs now supports caching of patches and file contents to reduce bandwidth and save disk space. See below for how to enable this. In my opinion, this is actually the most exciting new feature, as it greatly speeds up a number of operations, and is essentially transparent. The only reason we don't enable it by default is because I'm uncomfortable creating a large directory in ~/.darcs/cache without the user's explicit consent. === Creating a repository in the hashed format === Creating a hashed repository is as easy as darcs get --hashed oldrepository newrepository or alternatively you could create a fresh repository with darcs initialize --hashed You can push, pull and send patches at will between hashed and old-fashioned repositories, so you should be able to experiment with this format even on projects that you do not control. === Enabling a global cache === It is very simple to enable a global cache. Simply execute $ mkdir -p $HOME/.darcs/cache $ echo cache:$HOME/.darcs/cache > $HOME/.darcs/sources This will cause darcs to store hard links in ~/.darcs/cache. It is always safe to delete this directory. = Darcs-2 merging = The future of darcs is in the darcs-2 repository format, which features a new merge algorithm that introduces two major user-visible changes 1. It should no longer be possible to confuse darcs or freeze it indefinitely by merging conflicting changes. However, this feature '''needs to be tested''', so please, do your worst, and let us know how darcs can handle it! 2. Identical primitive changes no longer conflict. This is a long-requested feature, and has far-reaching implications. See below (the section on "new semantics") for a discussion of these implications. === Creating a repository in the darcs-2 format === Converting an existing repository to the darcs-2 format is as easy as darcs convert oldrepository newrepository However, the convert command does run rather slowly. Moreover, you should ideally only perform this command once per project, as the conversion is not reversible, and its result is dependent on the order of patches in your repository. Of course, you can experiment all you like, but projects should switch to darcs-2 format in unison, and only after the final release of darcs 2. You can also create a fresh repository with darcs initialize --darcs-2 == Changes in semantics == When using the darcs-2 format, darcs treats identical primitive patches as the''same''patch. This has dramatic implications in how darcs-2 will define dependencies. In particular, dependencies (except those explicitly created by the use with --add-deps) are always dependencies on a given''primitive''patch, not on a given named patch. This means that the change named "foo" may in effect depend on''either the change named "bar" or the change named "baz"''. This prerelease of darcs 2 has not been fully converted to always take advantage of these new semantics--it will not cause corruption, but under unusual circumstances, could exit with an error. We need to decide how to handle these semantics in the user interface. === A simple example === Let me illustrate what could happen with a story. Steve creates changes "A" and "B": steve$ echo A > foo steve$ darcs add foo steve$ darcs record -m A steve$ echo B > foo steve$ darcs record -m B Meanwhile, Monica also decides she'd like a file named foo, and she also wants it to contain A, but she also wants to make some other changes: monica$ echo A > foo monica$ darcs add foo monica$ echo Z > bar monica$ darcs add bar monica$ darcs record -m AZ At this point, Monica pulls from Steve: monica$ darcs pull ../steve but she decides she prefers her AZ change, to Steve's A change, and being a harsh person, she decides to obliterate his change: monica$ darcs obliterate --match 'exact A' --all At this point, darcs 1 would complain, pointing out that patch B depends on patch A. However, darcs 2 will happily obliterate patch A, because patch AZ provides the primitive patches that B depends upon. At this point, however, we run into the limitations of this prerelease version of darcs 2: If Steve pulls from Monica, his darcs will fail, because the common set of patches (which is only B) cannot exist without either A or AZ. I plan to fix this behavior, but the internal API for doing so is not at all clear to me, which is why I'm looking for input from others. But note that this situation can only occur if users take advantage of the new semantics, which I suspect will be relatively seldom, until we give them tools to more easily do so (see below). === A few implications === At first this may look like a regression. Certainly, it took me a long conversation (with Steve, immortalized in the above example--but in truth, Monica would never be so unkind as to obliterate Steve's change) to determine that this behavior is actually a Good Thing, and that the potential confusion among users is a relatively small danger. The main lesson regarding these new semantics is that''patches depends on primitive patches, not on named patches''. A named patch is really just a set of primitive patches. Once we train darcs to take advantage of this feature, several tantalizing possibilities open up: 1. As the above example illustrates, in certain circumstances we can obliterate patches that are depended upon by other patches. We could automate this, by enabling obliterate (perhaps given a flag?) to break apart the patch it's trying to obliterate, and leave behind only those primitive patches which are depended upon by other patches. Perhaps we could call this new feature "atomization". Of course, this applies equally well to unrecord. 2. Recognizing that amend-record is equivalent to unrecord followed by record in a clean repository, it becomes clear that with atomization we could amend even patches that later patches depend upon. I guess these two (three?) examples are all that come to mind, but they're big examples, features that have been requested many times over the years. Of course, there would be some debris left over, a portion of the patch that got atomized, but this debris would be minimal, and seems to me to be necessary. ======================================== The version of this announcement on the wiki has more discussion of implementation plans and how you can contribute. I urge you to join in the fun of testing and optimizing this new version of darcs! David

2 1

Re: [Haskell-cafe] IO is a bad example for Monads
by Hans van Thiel 12 Dec '07

12 Dec '07

On Wed, 2007-12-12 at 16:27 +0100, Hans van Thiel wrote: > [snip] > > > > I fear those people can do vast amounts of damage. :( > > > > When inept programming yields the wrong result, it is clear (even to the > > inept) that the program is bad. > > > > When the result is correct but there are egregious time or space leaks, > > it is "clear" to everyone but the Haskell guru that it "must" be the > > programming language that is deficient, and will be duly flamed far and > > wide. This perception will be impossible to reverse when it gains > > traction (and nothing ever goes away on the Internet). > > > > Seeming "deus ex machina" code changes (perhaps helpfully offered on > > haskell-cafe) to minimize or correct the undesirable runtime behavior > > appear even to many Haskellites to be black magic, accompanied by the > > runes of profile dumps (like knowing what generation 0 and generation 1 > > garbage collection is). > I see your point, but maybe there should be better analyzing tools then, > as well as tutorials which explain that problem. > > > > >> Haskell is not a quick-and-dirty language but quite the opposite. Haskell’s > > >> unique selling propositions are features like type classes, higher order > > >> functions and lazy evaluation which make life easier in the long term. The > > >> downside of these features is that they might make life harder in the short > > >> term. > > > I don't know. In a sense Haskell is easier than, for example, C, because > > > the concept of a function definition is more natural that that of > > > assignments and loops. The idea that x = 5; x = x + 7 makes sense > > > requires a complete new way of thinking. OK, once you've been doing it > > > for a few years switching back to x = 5 + 7 is hard. > > > > I would limit that to say that *denotational* semantic intuition is easy > > to wield in Haskell. Operational semantic intuition is Haskell is very > > non-obvious to the imperative (and many functional) programmers. > > > > Making matters worse, the first is an advantage well-hyped by > > functionistas, the second hurdle is rarely admitted to. > I admit I don't understand this. > > > > >> That said, I definitely think that we should make learning the language as > > >> easy as possible. But our ultimate goal should be to primarily show > > >> newcomers the Haskell way of problem solving, not how to emulate Python or > > >> Java programming in Haskell. > > > Again, is there a danger of that happening? > > > > Yes. Those absent the necessary humility to approach haskell-cafe with > > open mind and flame-retardant dialog will fall back on what they know: > > transliterated Java/Python with a morass of do blocks and IO monads, > > then (rightly) bash how "ugly" Haskell syntax is when used in this way. > > > > This type of programmer looking to use Haskell casually should sign a > > "benefit of the doubt" contract whereby they assume that any runtime > > suboptimalities derive from their own coding and not from Haskell's > > defects. This is the innate assumption of the curious, the > > self-motivated, the clever. This is not typically the starting > > assumption of the "I'm an expert at Joe-imperative language" hacker who > > took 10 years to perfect his Java skills and expects thereby to jump to > > at least year 5 of Haskell without effort. > But that person will be used to all the help he's gotten from the Java > and/or Eclipse, with tutorials and reference implementations. Now he has > to depend on dissertations and JFP articles for anything that's less > than 10 years old, and a few helpful experts (much appreciated, I want > to add) who are willing to spend the time to answer questions. > > > > I do strongly believe in stimulating the curiosity of all comers, just > > not in giving the false impression that a quick read-through of a few > > tutorials will let you write lightning-fast code, or know when to > > abandon [Char] for something more clever, or where to insert those bangs > > and fold left instead of right, and how ad hoc and parametric > > polymorphism differ, and what Rank-n and existential means (and why you > > can just pickle any object in Python but need to know a half dozen > > abstract things including who Peano was to do the same in Haskell), and > > what the heck an infinite type is, and on and on. > It's possible, IMO, that Haskell requires a higher skill level in > information science that the imperative languages. Many working > programmers come from different backgrounds and are not experts in > computer science. But, like a skyscraper is not built just by the > architects, maybe those 'lower' skills have their place too. Maybe not, > or not in Haskell. Could be, though I don't think so, myself. > > Haskell has definitely been teaching me some serious humility! Possibly > > it is best that those not ready for that lesson might better stick with > > Python. > If they read this, I'm sure they will. > > Best Regards, > > Hans van Thiel > >

1 0

ANNOUNCE: dataenc-0.10.1
by Magnus Therning 12 Dec '07

12 Dec '07

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Yesterday I uploaded a small update to the dataenc library: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dataenc-0.10.1 Dependencies base License LGPL Copyright Magnus Therning, 2007 Author Magnus Therning Maintainer magnus(a)therning.org Exposed modules Codec.Binary.DataEncoding, Codec.Binary.Base16, Codec.Binary.Base32Hex, Codec.Binary.Base32, Codec.Binary.Uu, Codec.Binary.Base64Url, Codec.Binary.Base64 The visible change is the addition of a function, decode', that allows lazier decoding by shifting some responisility to the user. /M -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFHX9G+iMWTaatN+6QRAqclAKC6/BM7/e9jRAjVCMYYAZd7D/fAPACfe0sd EfPoHw4HW7snU3RilejfIIY= =XPUb -----END PGP SIGNATURE-----

1 0

do
by PR Stanley 12 Dec '07

12 Dec '07

Hi I've probably asked about the do construct, if that's the right label. Unfortunately I'm still not quite sure of its role and more specifically its syntax. Something to do with generators perhaps? A description plus some examples would be most gratefully received. Thanks, Paul

26 52