December 2007 - Haskell-Cafe

Examples of useful functions of order >= 3?
by Ben Lippmeier 14 Dec '07

14 Dec '07

Hi all, I'm working on a type-based side effect analysis for a Haskell-like language, and need to test it against some more higher order functions. The situation is a bit icky because it uses bounded quantification and various related issues (ie covariance vs contravariance) only come into play when dealing with functions of order >= 3. Trouble is, the vast majority of useful higher order functions that I can think of are of order 2. Oh, I can certainly invent toys like: order3 f = f succ order4 b f = if b then f else order3 .. and so on, but I'm left feeling unsatisfied. I vaguely remember a paper called something like "Is there any use for a seventh order function?", but I forget why they were used, and I can't find it on Google, or ACM or any of the other likely places. Does anyone have any examples of code (in whatever language) which usefully uses functions of order >= 3?? Preferably up to 5? Thanks, Ben.

4 3

Hoogle error
by jim burton 14 Dec '07

14 Dec '07

Hoogling (->) (>>=) gives Error, your search was invalid: Parse Error: Unexpected character '>>=)' Is there a way to escape the input so it would work? (I wasn't really expecting the right results BTW as I think hoogle searches type signatures not patterns in definitions, right?) Thanks, Jim

2 3

Execution of external command
by Bulat Ziganshin 14 Dec '07

14 Dec '07

Hello haskell-cafe, please help me with selection of proper function to use i need to run external command with parameter and get its stdout, smth like this: output <- system "cmd param" the code should be compatible with unix and windows, and it should be possible to execute scripts (so afaiu it should execute command via cmd/sh). i use ghc 6.6.1 and it will be great if this function will not require any non-bundled libs and be compatible with later ghc versions -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

8 22

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