December 2006 - Haskell-Cafe

multi parameter type classes for NP problems
by Joshua Ball 20 Dec '06

20 Dec '06

Hi all, For my own study, I've been playing around with various NP complete problems. Previuosly I was doing so in Java, but because I want to learn Haskell, I'm trying to port the algorithms. In Java, I had an abstract class called AbstractNPProblem which looked like this: public abstract class AbstractNPProblem implements NPProblem { public abstract boolean validates(Certificate c); public abstract List<Certificate> certificates(); public boolean decide() { for (Certificate c : certificates()) { if (validates(c)) { return true; } } return false; } } This has one problem, however: it is slightly dynamically typed. Anybody that implements the verify method must cast the object c to a particular type (could be a bitmask, a list of integers, a subgraph, etc.) I'd like to get rid of this problem in porting to Haskell. Here is how I am trying to solve the problem, using multi-parameter type classes. class NPProblem inst cert where validates :: cert -> inst -> Bool certificates :: inst -> [cert] decide :: inst -> Bool decide i = any (\x -> x `validates` i) $ certificates i Unfortunately, ghc throws the following type error: NPProblem.hs:5:45 Could not deduce (NPProblem inst a) from the context (NPProblem inst cert) arising from use of `certificates' at NPProblem.hs:5:45-58 Possible fix: add (NPProblem inst a) to the class or instance method `decide' In the second argument of `($)', namely `certificates i' In the expression: (any (\ x -> x `validates` i)) $ (certificates i) In the definition of `decide': decide i = (any (\ x -> x `validates` i)) $ (certificates i) Could somebody explain what is wrong with my intuitive approach? Also, is multi parameter type classes the way to go, or is there a better way?

2 2

Origins of (x:xs)?
by Toby Hutton 20 Dec '06

20 Dec '06

Hi, This may have been asked before, sorry if so. I've wondered where the convention of pattern matching a list to (x:xs) came from? I've read a couple of old papers recently which let me believe it may have started back in the '70s with Miranda and its ilk. Does anyone know why (x:xs)? Is xs meant to be a synonym for 'excess'? Yours curiously, Toby.

4 3

YAHT "bug"
by Johan Grönqvist 20 Dec '06

20 Dec '06

Hi, As noted on e.g. http://paste.lisp.org/display/30002, there seems to be a misprint in YAHT. The code on page 124 for law3a does not use g, and uses y without introducing it. The page says this was corrected in the wikibook, but it seems not to have been fixed in the darcs repository at haskell.org. I found no mentioning on the YAHT page of ways to change this, so sending a mail to this list seemed simplest to me. Thanks for all good tutorials! Johan

2 1

#haskell irc channel reaches 300 users
by dons＠cse.unsw.edu.au 20 Dec '06

20 Dec '06

A small announcement :) 5 years after its inception, under the guiding hand of Shae Erisson (aka shapr), the #haskell IRC channel[1] on freenode has finally reached 300 users! We reached 200 users in January, 250 users for the first time in August, and didn't expect hit to reach 300 for a while. Then last night: 12:50 lambdabot> Maximum users seen in #haskell: 305 This puts the channel at around position 15 of the 4000 freenode channels. For comparision, a sample of the state of the other language communities: #perl 484 #php 474 #c 381 #c++ 379 #ruby 368 > #haskell 305 #python 303 #lisp 214 #java 213 #javascript 156 #scheme 112 #lua 72 #ocaml 56 #sed 35 #d 33 You can see the growth of the channel over here: http://www.cse.unsw.edu.au/~dons/irc/nick-activity.png If you've not dropped by the channel yet, feel free to come and chat, and toss around some lambdas! :) Cheers, Don 1. http://www.haskell.org/haskellwiki/IRC_channel

2 1

FD problem in GHC 6.6
by Robert 20 Dec '06

20 Dec '06

Fellow Haskellers, I have a package that uses some light typeclass hackery to automaticly build parsing algorithms based on the type of a function. I was recently informed that my package doesn't compile on GHC 6.6 due to the new restrictions on FD resolution; in particular I have instance declarations which fail the coverage condition. I can use undecidable instances to make the package compile again, but I'd prefer not to if I can avoid it. Are there any easy tricks I can use to make this work? I only sort-of understand the new restrictions, so I'm at something of a loss as to how to work around them. The problem is fairly isolated in my code: the affected section begins at line 140 in http://www.eecs.tufts.edu/~rdocki01/shellac/src/System/Console/Shell/Comman… I've reproduced the class and a few of the instance declarations here: class CommandFunction f st | f -> st where parseCommand :: String -> f -> CommandParser st commandSyntax :: f -> [Doc] instance CommandFunction (Sh st ()) st where parseCommand wbc m str = -- list monad do (x,[]) <- runRegex (maybeSpaceBefore (Epsilon (CompleteParse m))) str return x commandSyntax _ = [] instance CommandFunction r st => CommandFunction (Int -> r) st where parseCommand = doParseCommand Nothing intRegex id commandSyntax f = text (show intRegex) : commandSyntax (f undefined) instance CommandFunction r st => CommandFunction (Integer -> r) st where parseCommand = doParseCommand Nothing intRegex id commandSyntax f = text (show intRegex) : commandSyntax (f undefined) -- Robert robdockins(a)fastmail.fm -- http://www.fastmail.fm - IMAP accessible web-mail

4 3

Success with Takusen (was: Type problem with simple takusen code)
by Paul Moore 20 Dec '06

20 Dec '06

On 12/12/06, Paul Moore <p.f.moore(a)gmail.com> wrote: > Should be, but isn't, unfortunately. The Setup.hs file includes some > code defining configPG etc, but there's nothing I can see for the user > control how it works. Maybe something in the cabal infrastructure > handles this, but I've not had time yet to dive into the cabal > documentation on the hope of finding something. Just a brief note to let people on the list know that, with a lot of extremely patient help from Alistair Bayley, I have managed to resolve the issues I was having. The fundamental issue I was hitting was that I was treating GHC as an interpreted system, rather than a compiler/linker. I was therefore not thinking about the errors I was seeing as I would if I hit (say) a C link error. To summarise, the following works fine: To install Takusen, make sure that an Oracle home is in your PATH. You don't need PostgreSQL or sqlite. Your Oracle install can be simply a client build - all you need is oci.dll, not the full OCI development package. runhaskell Setup.hs configure runhaskell Setup.hs build runhaskell Setup.hs install That's it, and it works fine. To build a program, you need to do ghc --make db.hs -o db D:\Oracle\Ora92\bin\oci.dll (put the path to your oci.dll here). This compiles your program, and links it with oci.dll to get the Oracle externals resolved. Runhaskell doesn't seem to work, as it tries to link all the DB backends at runtime, regardless of whether you use them. That really is all there is to it. Arguably, the error messages you get when you mess up bits of this aren't too helpful, but if you've ever seen a C++ compilation fail with compile or link errors, you'll know not to expect much here (or at least you should!) GHC is certainly no worse than that. Once again, thanks to Alistair for his patience. Now I'll go off and reproduce my success on a clean environment just to be sure, and then write up what I've learnt for the Wiki and the Takusen readme. Paul.

2 2

Re: [Haskell] Haskell Weekly News: December 20, 2006
by Arthur van Leeuwen 20 Dec '06

20 Dec '06

On 20-dec-2006, at 2:17, Donald Bruce Stewart wrote: > ---------------------------------------------------------------------- > ----- > Haskell Weekly News > http://sequence.complete.org/hwn/20061220 > Issue 54 - December 20, 2006 > ---------------------------------------------------------------------- > ----- > > Announcements > > Haskell Vim plugin. Arthur van Leeuwen [15]announced a new [16]vim > plugin for Haskell providing some preliminary folding support, easy > insertion of type signatures into programs, and support for > handling > .hi files. > > 15. http://article.gmane.org/gmane.comp.lang.haskell.cafe/17675 > 16. http://www.cs.uu.nl/~arthurvl/haskell.vba Read that as 'support for automatically ignoring .hi files' (which really helps when editing large programs consisting of multiple files... it makes tab Do The Right Thing). Doei, Arthur. -- /\ / | arthurvl(a)cs.uu.nl | Work like you don't need the money /__\ / | A friend is someone with whom | Love like you have never been hurt / \/__ | you can dare to be yourself | Dance like there's nobody watching

1 0

WANTED: grey line layout boxes in vim and emacs
by dons＠cse.unsw.edu.au 20 Dec '06

20 Dec '06

I'd like some more help from the editors in getting 2d layout right without trying. Here's a mockup of vim with vertical grey bars delimiting layout: http://www.cse.unsw.edu.au/~dons/tmp/haskell+boxes.png Does anyone know how to get this effect in vim (or emacs)? Bonus points if the grey bars are draggable, changing the indenting. More bonus points for box-based navigation. -- Don

5 8

Possible commercial FP/Haskell job
by dons＠cse.unsw.edu.au 19 Dec '06

19 Dec '06

Noticed this in the blargh-o-sphere, some people might be interested: http://www.nnseek.com/e/comp.lang.python/lisp_python_programmers_among_othe… Senior applications developer: Our advanced applications work is currently being done in Common Lisp, but that could change depending on who we find to fill this position. If you are the sort of person who has always wanted an opportunity to prove that Haskell or OCaml is the Best Way to write software, this could be your chance. But CL is currently our first choice. -- Don

1 0

Haskell Weekly News: December 20, 2006
by dons＠cse.unsw.edu.au 19 Dec '06

19 Dec '06

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20061220 Issue 54 - December 20, 2006 --------------------------------------------------------------------------- Welcome to issue 54 of HWN, a weekly newsletter covering developments in the Haskell community. A new release of the Edison data structures library, along with several other new libraries, and some new Haskell articles in the blogspace. Announcements Edison 1.2.1. Robert Dockins [1]announced the 1.2.1 release of [2]Edison. Edison is a famous library of efficient, purely-functional data structures in Haskell. Notable changes from the previous version include: a new sequence implementation based on finger trees; documentation fixes dealing with the licence; added a few methods to EnumSet for wrapping and unwrapping the underlying Word 1. http://article.gmane.org/gmane.comp.lang.haskell.general/14662 2. http://www.eecs.tufts.edu/~rdocki01/ Basic serialisation library using SYB. Stefan O'Rear [3]announced GenericSerialize, [4]a library for serialization using the existing generic-programming framework. It is often advocated that support for serialization should be added to the compiler (e.g. in the form of a deriving(Binary)). With this project Stefan wants to show that the existing infrastructure is sufficient, and has some advantages over a dedicated serialization interface. GenericSerialize supports multiple serialization modes. 3. http://article.gmane.org/gmane.comp.lang.haskell.general/14656 4. http://members.cox.net/stefanor/genericserialize vty 1.0. Stefan O'Rear [5]announced vty 1.0, a simple [6]terminal interface library. It provides: handling of suspend/resume, window resizes, computation of minimal differences, minimizes repaint area, automatically decodes keyboard keys into (key,modifier) tuples, and more! 5. http://article.gmane.org/gmane.comp.lang.haskell.general/14670 6. http://members.cox.net/stefanor/vty Monad.Reader call for copy. Wouter Swierstra [7]reminded us that its still not too late to write something for the next issue of [8]The Monad.Reader! We have a nice issue slowly shaping up, but your contribution is still very welcome. Get in touch with Wouter if you intend to submit something -- the sooner you let him know what you're up to, the better. 7. http://article.gmane.org/gmane.comp.lang.haskell.general/14638 8. http://www.haskell.org/haskellwiki/TheMonadReader Ranged Sets. Paul Johnson [9]announced that Ranged Sets now have a Monoid instance, and singletons (i.e. a range holding a single value), thanks to Jean-Philippe Bernardy. 9. http://article.gmane.org/gmane.comp.lang.haskell.general/14663 CalDims 1.0 (RC 1). schneegloeckchen [10]announced CalDims, a calculator aware of units. Its available from [11]the Haskell wiki. It includes support for user defined basic units and derrived units; user defined functions; work sheets can be modified/saved via shell; (1/3)*3 == 1 (No rounding errors); built-in feature to simplify units and easy unit-conversion. 10. http://article.gmane.org/gmane.comp.lang.haskell.general/14671 11. http://www.haskell.org/haskellwiki/CalDims JoinCabal. Dougal Stanton [12]announced an alternative to mkcabal, for initialising new cabal projects: [13]JoinCabal, available [14]via darcs. JoinCabal will create stub sources files with a license header, and appropriate license for you code, making it easier to set up a valid cabal build system. 12. http://article.gmane.org/gmane.comp.lang.haskell.cafe/17600 13. http://brokenhut.no-ip.org/~dougal/cgi-bin/darcsweb.cgi?r=JoinCabal;a=summa… 14. http://brokenhut.no-ip.org/~dougal/darcs/joincabal/ Haskell Vim plugin. Arthur van Leeuwen [15]announced a new [16]vim plugin for Haskell providing some preliminary folding support, easy insertion of type signatures into programs, and support for handling .hi files. 15. http://article.gmane.org/gmane.comp.lang.haskell.cafe/17675 16. http://www.cs.uu.nl/~arthurvl/haskell.vba Haskell' This section covers the [17]Haskell' standardisation process. * [18]Strictly matching monadic let and overloaded Bool 17. http://hackage.haskell.org/trac/haskell-prime 18. http://thread.gmane.org/gmane.comp.lang.haskell.prime/1956/focus=1974 Discussion Automonadization of code. Adam Megacz [19]asked if there any work on automatic translation of code in some tiny imperative language into Haskell code that uses the ST and/or IO monads (or perhaps even pure functional code)? 19. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/17326/focus=17326 What are the points in pointfree style?. Steve Downey [20]wondered about the origin of the term 'points' in pointfree style. 20. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/17560/focus=17560 Rebinding >>= for restricted monads. David Roundy [21]pondered rebinding the >>= syntax in order to provide a more restricted monad. 21. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/17646/focus=17646 #haskell reaches 300 users. Don Stewart [22]noticed that the [23]#haskell IRC channel has now reached the 300 user mark, making it one of the top 15 channels on the freenode network. 22. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/17705/focus=17705 23. http://haskell.org/haskellwiki/IRC_channel Blog noise [24]Haskell news from the blogosphere. * [25]Do-notation considered harmful * [26]Reddit discussion considered productive * [27]The Dot-Matrix Printhead: a Haskell Toy * [28]The Revised Dot-Matrix Printhead * [29]The monad laws * [30]On documentation * [31]Software requirements do not change * [32]Haskell and the web: some ideas in progress * [33]Using Haskell in Python: haskellembed * [34]Literate programming * [35]The lambda revolution, Episode V, the deb strikes back * [36]On syntax * [37]Syntax: adding Lisp macros * [38]More on syntax * [39]UCBLogo and the Fibonacci sequence * [40]Linguistic comparisons: string reversal * [41]New Software Technology: Blockage On Line * [42]More silver bullets * [43]Preventing NullPointerExceptions, Maybe * [44]Adventures in Haskell: the Parsec magic weapon * [45]Advertising Haskell * [46]Programming Haskell: part 1 * [47]Programming Haskell: part 2 * [48]Programming Haskell: part 3 * [49]Introductory Haskell Programming in the UNIX Environment * [50]On Haskell, Intuition And Expressive Power * [51]Your order is ready sir * [52]It's alive (the French Haskell community) * [53]Maybe monad in Java * [54]Secret Santas in Haskell I: Preliminaries * [55]Secret Santas in Haskell II: Orbits and Lists * [56]Why Closures in Dolphin is a Good Idea * [57]Haskell Stacks : Two Different Ways * [58]Haskell Golf Scores * [59]Languages * [60]Questions on Haskell Style (and Polynomials redux) * [61]A simple RSS aggregator in 50 lines of Haskell using HXT 24. http://planet.haskell.org/ 25. http://syntaxfree.wordpress.com/2006/12/12/do-notation-considered-harmful/ 26. http://syntaxfree.wordpress.com/2006/12/13/reddit-discussion-considered-pro… 27. http://praisecurseandrecurse.blogspot.com/2006/12/dot-matrix-printhead-hask… 28. http://praisecurseandrecurse.blogspot.com/2006/12/revised-dot-matrix-printh… 29. http://cale.yi.org/index.php/The_Monad_Laws 30. http://blog.milkfarmsoft.com/?p=29 31. http://blog.tmorris.net/software-requirements-do-not-change/ 32. http://haskell-web.blogspot.com/2006/12/some-ideas-in-progress_13.html 33. http://www.kuarepoti-dju.net/index.php?p=86 34. http://benjisimon.blogspot.com/2006/12/programs-as-stories.html 35. http://pupeno.com/blog/the-lambda-revolution-episode-v-the-deb-strikes-back 36. http://cgi.cse.unsw.edu.au/~dons/blog/2006/12/14#on-syntax 37. http://nominolo.blogspot.com/2006/12/syntax.html 38. http://www.cse.unsw.edu.au/~dons/blog/2006/12/15#on-syntax-again 39. http://sob.apotheon.org/?p=171 40. http://sob.apotheon.org/?p=170 41. http://cogito.blogthing.com/2006/12/14/new-software-technology-blockage-on-… 42. http://clabs.org/blogki/blogki.cgi?page=/ComputersAndTechnology/AndTheNomin… 43. http://rickyclarkson.blogspot.com/2006/09/using-strong-typing-to-eliminate.… 44. http://jpmoresmau.blogspot.com/2006/12/adventures-in-haskell-parsec-magic.h… 45. http://neilmitchell.blogspot.com/2006/12/advertising-haskell.html 46. http://cgi.cse.unsw.edu.au/~dons/blog/2006/12/16#programming-haskell-intro 47. http://www.cse.unsw.edu.au/~dons/blog/2006/12/17#programming-haskell-part-2 48. http://cgi.cse.unsw.edu.au/~dons/blog/2006/12/18#ph-3 49. http://blog.kfish.org/software/haskell/intro-haskell-unix.html 50. http://www.defmacro.org/ramblings/haskell-productivity.html 51. http://lambda-the-ultimate.org/node/1905#comment-23273 52. http://koweycode.blogspot.com/2006/12/its-alive.html 53. http://blog.tmorris.net/maybe-monad-in-java/ 54. http://mult.ifario.us/articles/2006/12/18/secret-santas-in-haskell-i-prelim… 55. http://mult.ifario.us/articles/2006/12/18/secret-santas-in-haskell-ii-orbit… 56. http://rickyclarkson.blogspot.com/2006/12/why-closures-in-dolphin-is-good-i… 57. http://progexpr.blogspot.com/2006/11/haskell-stacks-two-different-ways.html 58. http://progexpr.blogspot.com/2006/11/haskell-golf-scores.html 59. http://computativestylings.blogspot.com/2006/12/languages.html 60. http://sambangu.blogspot.com/2006/12/questions-on-haskell-style-and 61. http://cale.yi.org/index.php/HRSS Quotes of the Week * Cale: I spent a whole summer being paid to write a nondeterministic search program in the list monad * monochrom: 007 titles for Haskellers: fromForeignPtr withCString; You Only lift Twice; Bottoms Are Forever; The Monad with the Pure Function; For Your Types Only; A view to A seq; Licence to killThread; iterate Never Dies; unsafePerformIO Is Not Enough. * DavidRoundy: ... fun of haskell-cafe is that it's where all the cool people hang out * dons: Coding drunk in Haskell is ok though, its like drinking on a passenger plane flight -- the stewards will prevent you from hurting anyone. However, coding drunk in C is just scary, DUI territory, and should not be allowed. * JulianMorrison: Small startup companies are the expendable sensory and feeding apparatus of the mainstream. * droundy: With a higher-kinded monad and phantom existential witness types, darcs would be very fun... * dons: The alien rulers of the galaxy must surely use a statically typed language with type inference * dibblego: Java programmers prefer referential transparency too, they just call it 'design patterns' or something * tessier: After the last newbies head exploded trying to read everything on that monad link there was a lot of paperwork. We'd like to avoid doing that again. Code Watch Fri Dec 8 21:03:34 PST 2006. Andy Gill. [62]Adding tracing support (HPC) 62. http://article.gmane.org/gmane.comp.lang.haskell.cvs.ghc/18263 Wed Dec 13 08:45:38 PST 2006. simonpj. [63]You can now have an MVar with a polymorphic contents 63. http://article.gmane.org/gmane.comp.lang.haskell.cvs.ghc/18279 About the Haskell Weekly News Each week, new editions are posted to [64]the Haskell mailing list as well as to [65]the Haskell Sequence and [66]Planet Haskell. [67]RSS is also available, and headlines appear on [68]haskell.org. Headlines are available as [69]PDF. The Haskell Weekly News is also [70]available in Spanish translation. To help create new editions of this newsletter, please see the [71]contributing information. Send stories to dons at cse.unsw.edu.au. The darcs repository is available at darcs get [72]http://www.cse.unsw.edu.au/~dons/code/hwn 64. http://www.haskell.org/mailman/listinfo/haskell 65. http://sequence.complete.org/ 66. http://planet.haskell.org/ 67. http://sequence.complete.org/node/feed 68. http://haskell.org/ 69. http://www.cse.unsw.edu.au/~dons/code/hwn/archives/20061220.pdf 70. http://haskell.org/haskellwiki/HWN/es 71. http://haskell.org/haskellwiki/HWN 72. http://www.cse.unsw.edu.au/~dons/code/hwn

1 0