January 2010 - Haskell-Cafe

parallel and distributed haskell?
by Scott A. Waterman 12 Feb '10

12 Feb '10

It looks like there was a recent hackathon focusing on implementing distributed haskell. http://hackage.haskell.org/trac/ghc/wiki/HackPar I feel there is quite a bit of latent interest in the subject here, but relatively little active development (compared to erlang, clojure, etc.) Can anyone involved give a quick overview (or pointers to one)? It would be good to hear what directions people are taking, and why, and where it's going. Personally, I'd love to know the current thinking on a variety of subjects: * erlang-like port/actor implementations v. more implicit constructs * serialization * node failure/error handling * "grid" compatibility v. various ad-hoc cluster approaches. Anyone actively looking at this kind of question who would want to talk about it? Thanks, --ts

7 8

ANN: Happstack 0.4.1
by Jeremy Shaw 11 Feb '10

11 Feb '10

Happstack 0.4.1 STABLE is now available. We recommend that all users of Happstack update to 0.4.1 immediately. Migration from Happstack 0.3 should be trivial. There was one race condition in happstack-state which could cause a state event to fail under heavy congestion. Happstack is the Haskell Application Server Stack. It is a scalable framework for developing web applications. It is similar in purpose to Django, RoR, Turbogears, Grails, Seaside, etc. Using less buzzwords, it is a collection of libraries which can be used to develop a self-contained server application which does not require SQL or Apache (though it can integrate with both). It includes: * an HTTP server * a rich DSL for deconstructing HTTP Requests and generating Responses * HTML/XML/etc templating via HStringTemplate, HSP, or Text.XHtml * a persistent data store based on user defined Haskell data types with ACID properties and state migration * and more!! Happstack's modular nature means it is easy to integrate unrelated 3rd party modules such as Pandoc, or to add support for an alternative templating system. Additionally, it does not exclude you from using SQL, or supporting other protocols besides HTTP. HOMEPAGE: http://www.happstack.com/ SUPPORTED PLATFORMS: Happstack supports GHC 6.8, 6.10, and 6.12, under GNU/Linux, FreeBSD, OS X, and Windows. GHC 6.12 currently requires a minor patch to HJScript. Details here: http://groups.google.com/group/haskell-server-pages/browse_thread/thread/56… INSTALL: 1. ensure that ~/.cabal/bin is in your $PATH 2. cabal update 3. cabal install happstack * see SUPPORTED PLATFORMS for information about GHC 6.12 NOTABLE CHANGES: For a complete list of changes see: http://www.patch-tag.com/r/mae/happstack/snapshots/all/history Removed: * happstack-contrib has been completely removed. If you were using something in it, please complain on the mailing list. * removed Happstack.Server.S3 -- newer, better maintained S3 libraries are on hackage now * removed unsupported spread-based multimaster support fileServe: * now with sendfile() support! On supported platforms sendfile allows files to be served from the disk to the network in a zero-copy fashion. This means faster transfers, less memory and CPU usage, and no file handle leaks. (hopefully). sendfile uses native sendfile() support on Linux, Windows, OS X, and FreeBSD. Other platforms will use a sendfile emulation mode. We recommend that you use sendFile instead of sendFileStrict or sendFileLazy, unless you have specific needs and know some reason why you must use sendFileStrict or sendFileLazy. * FileServe internals majorly refactored. FileServe now provides a modular way of building your own fileServe-like functions. Also includes functions for serving a single file instead of the contents of a directory. * added more complete list of mime-types * automatically redirect from foo to foo/ if foo is a directory * filter . and .. from request path, but allow filenames and directories which start with . happstack-server: * ServerMonad instance for ErrorT * Added ServerMonad, FilterMonad, and WebMonad for XMLGenT * Added secure flag to cookies. Defaults to False. * fix supportsIPv6 to work with newer versions of network library * simpleHTTPWithSocket + bindPort for H.S.SimpleHTTP (you can use this to start the server as root, bind to the socket, and then drop privileges.) * Fixed Accept-Encoding parser to accepts encodings with a - in them. Added additional tests to acceptEncodingParserTest * fix so basicAuth sets correct response code and headers. * SimpleHTTP: added trailingSlash. Guard which checks that Request URI ends with a / * decode body of PUT requests not just POST * added ifModifiedSince guard * added host and withHost guards to SimpleHTTP (similar to dir and path, but for the requested hostname) other: * happstack-state: Correct an embarrassing race condition bug. * happstack-data: Exported getSafeGet and getSafePut * happstack: add state transition code to guestbook (add email to form, handler, and state), and tar of example _local state before transition experimental: * happstack-state: now has experimental replication support using Amazon Web Services. This support is disabled by default. This feature is highly experimental, may not work, and may even be completely removed in future versions (though, hopefully not). THANKS: Alex Jacobson David Himmelstrup / Lemmih Matthew Elder / mae Antoine Latter Erik Hesselink Pasqualino 'Titto' Assini Nils / McManiaC Thomas Hartman Creighton Hogg / wchogg John MacFarlane Jochem Berndsen / koeien MightByte And everyone who filed bug reports, tested RC1 and RC2, and anyone else I missed.

6 7

Examples/docs for simulated annealing bindings
by Dougal Stanton 11 Feb '10

11 Feb '10

I found the HsASA library [1] on Hackage, but there's no documentation and it's not particularly intuitive. I can't see any obvious way of choosing initial config or generating new configurations. Google reveals no one using it. Does anyone have ideas? [1]: http://hackage.haskell.org/package/HsASA-0.1 Cheers, D -- Dougal Stanton dougal(a)dougalstanton.net // http://www.dougalstanton.net

3 2

Spelling checker exercise
by Matthew Phillips 08 Feb '10

08 Feb '10

Hello all, sorry to bring up an old chestnut, but I’m trying to improve my Haskell-fu by writing a small program, and chose Peter Norvig’s spelling checker as my exercise material (http://norvig.com/spell-correct.html) While I’ve gotten it working, and found it quite illuminating, I also found it to to be very slow. And then I discovered that, of course, others have been here well before me ([1] and [2]). Those discussions were very interesting, but the code they refer to is mostly not available, so the most I’ve gotten out of it so far is that: (a) I should be using strict left folds and strict Map insertions for the word frequency map (this shaved off about a second: ~5s -> ~4s for a single word on my 2.4GHz MacBook Pro, GHC 6.10.4) (b) I should probably be using ByteString’s (c) Using Set’s for the edit permutations probably isn’t worth it (although I found using plain lists made it about a second slower) (b) is difficult because I’ve used matching patterns plus list comprehensions to generate the potential edits, and I really like how elegantly it pans out that way. Because ByteString’s are not lists, I can’t see a way to keep the current structure and use them. The code is at [3] (link to version at time of post). Profiling [4] shows: $ ./spelling becuase +RTS -p becuase -> because $ cat spelling.prof total time = 4.02 secs (201 ticks @ 20 ms) total alloc = 1,544,257,792 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc train Main 52.7 19.7 readFile Main 28.9 8.6 wordsBy Main 10.9 49.5 toLower Main 7.0 21.8 ... So it appears that “train" (building the freq map) and “readFile” in “nwords" are the places to hone. I will look at using Bloom Filters or Trie’s instead of Data.Map, but I wonder if readFile should be taking nearly %30 of the run time, even for a 6MB file? Sorry to dump such a long post on the list — I’ll understand if no one can be bothered rehashing this. But, in summary I’d like to know: (a) how could I use ByteString’s for this to speed up I/O and reduce memory usage without losing the nice readability? (b) should readFile be so slow? (c) any other tips Possibly all my questions could be answered if someone has the code from the old posts. Cheers, Matthew. [1]: http://haskell.markmail.org/search/?q=norvig%20spelling#query:norvig%20spel… [2]: http://thread.gmane.org/gmane.comp.lang.haskell.cafe/21780 [3]: http://github.com/scramjet/spelling/blob/44fd336ef4f62d49c7087dbc1ffb9c009b… [4]: http://github.com/scramjet/spelling/blob/f5146b24b77443c22975ff69fb91aa922c…

3 11

Trapping getChar before echo
by Mark Spezzano 05 Feb '10

05 Feb '10

Hi, Is there any way of trapping keystrokes in Haskell, modifying them, and then echoing? Basically I want to give the user a prompt like: > and then have whatever they type appear in UPPERCASE regardless of whether caps lock was on or not. By default Haskell seems to echo characters in whatever case they were typed. I want to sneak in a toUpper in before the Chars get echoed. Thanks Mark Spezzano

7 8

could we get a Data instance for Data.Text.Text?
by Jeremy Shaw 05 Feb '10

05 Feb '10

Hello, Would it be possible to get a Data instance for Data.Text.Text? This would allow us to create a Serialize instance of Text for use with happstack -- which would be extremely useful. We (at seereason) are currently using this patch: http://src.seereason.com/haskell-text-debian/debian/patches/add_Data_instan… which basically adds: +textType = mkStringType "Data.Text" + +instance Data Text where + toConstr x = mkStringConstr textType (unpack x) + gunfold _k z c = case constrRep c of + (CharConstr x) -> z (pack [x]) + _ -> error "gunfold for Data.Text" + dataTypeOf _ = textType + This particular implementation avoids exposing the internals of the Data.Text type by casting it to a String in toConstr and gunfold. That is similar to how Data is implemented for some numeric types. However, the space usage of casting in Float to a Double is far less than casting a Text to a String, so maybe that is not a good idea? Alternatively, Data.ByteString just does 'deriving Data'. However, bytestring also exports Data.ByteString.Internal, wheres Data.Text.Internal is not exported. Any thoughts? I would like to get this handled upstream so that all happstack users can benefit from it. - jeremy

9 20

Re: [Haskell-cafe] Very imperfect hash function
by John Lato 02 Feb '10

02 Feb '10

> From: Hans Aberg <haberg(a)math.su.se> > > On 28 Jan 2010, at 20:07, Steve Schafer wrote: > >> The data are currently in a large lookup table. To save space, I'd >> like >> to convert that into a sort of hash function: >> >> hash :: key -> value >> >> My question is this: Is there any kind of generic approach that can >> make >> use of the knowledge about the internal redundancy of the keys to come >> up with an efficient function? > > There are minimal perfect hash functions; there are some libraries > mentioned here, though they are not in Haskell code: > http://en.wikipedia.org/wiki/Perfect_hash_function > > This is suitable when you do a lot of lookups with few key updates. An > alternative might be Data.Map, where lookups have time complexity > O(log n), n = size of map. The minimal perfect hash function looks like the real algorithmic solution, but I would just use Data.IntMap for this. Cheers, John

3 7

Very imperfect hash function
by Steve Schafer 01 Feb '10

01 Feb '10

I'm looking for some algorithmic suggestions: I have a set of several hundred key/value pairs. The keys are 32-bit integers, and are all distinct. The values are also integers, but the number of values is small (only six in my current problem). So, obviously, several keys map to the same value. For some subsets of keys, examining only a small portion of the key's bits is enough to determine the associated value. For example, there may be 250 keys that all have the same most-significant byte, and all 250 map to the same value. There are also keys at the other extreme, where two keys that differ in only one bit position map to different values. The data are currently in a large lookup table. To save space, I'd like to convert that into a sort of hash function: hash :: key -> value My question is this: Is there any kind of generic approach that can make use of the knowledge about the internal redundancy of the keys to come up with an efficient function? Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/

5 4

Re: Non-termination of type-checking
by oleg＠okmij.org 01 Feb '10

01 Feb '10

Here is a bit more simplified version of the example. The example has no value level recursion and no overt recursive types, and no impredicative polymorphism. The key is the observation, made earlier, that two types c (c ()) and R (c ()) unify when c = R. Although the GADTs R c below is not recursive, when we instantiate c = R, it becomes recursive, with the negative occurrence. The trouble is imminent. We reach the conclusion that an instance of a non-recursive GADT can be a recursive type. GADT may harbor recursion, so to speak. The code below, when loaded into GHCi 6.10.4, diverges on type-checking. It type-checks when we comment-out absurd. {-# LANGUAGE GADTs, EmptyDataDecls #-} data False -- No constructors data R c where -- Not recursive R :: (c (c ()) -> False) -> R (c ()) -- instantiate c to R, so (c (c ())) and R (c ()) coincide -- and we obtain a recursive type -- mu R. (R (R ()) -> False) -> R (R ()) cond_false :: R (R ()) -> False cond_false x@(R f) = f x absurd :: False absurd = cond_false (R cond_false)

7 9

OT: Literature on translation of lambda calculus to combinators
by Dušan Kolář 01 Feb '10

01 Feb '10

Dear cafe, Could anyone provide a link to some paper/book (electronic version of both preferred, even if not free) that describes an algorithm of translation of untyped lambda calculus expression to a set of combinators? Preferably SKI or BCKW. I'm either feeding google with wrong question or there is no link available now... Thanks, Dušan

10 11