- Haskell-Cafe - Haskell.org

[ANN] bloomfilter 1.0 - Fast immutable and mutable Bloom filters
by Bryan O'Sullivan 03 Jun '08

03 Jun '08

I'm pleased to announce the availability of a fast Bloom filter library for Haskell. A Bloom filter is a probabilistic data structure that provides a fast set membership querying capability. It does not give false negatives, but has a tunable false positive rate. (A false positive arises when the filter claims that an element is present, but in fact it is not.) The library is easy to use. As an example, here's a reimplementation of the Unix "spell" command. import Data.BloomFilter.Easy (easyList, elemB) main = do filt <- (easyList 0.01 . words) `fmap` readFile "dictionary.txt" let check word | word `elemB` filt = "" | otherwise = word ++ "\n" interact (concat . map check . lines) It is also carefully tuned for performance. On my laptop, I can sustain a construction or query rate well in excess of a million ByteStrings per second. Source code: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bloomfilter Latest bits: darcs get http://darcs.serpentine.com/bloomfilter <b

10 12

ghc 6.8.2 issue
by Galchin, Vasili 03 Jun '08

03 Jun '08

Hello, I have been developing new code for the "unix" package. I have run into what I think are ghc 6.8.2 anomalies but couldn't see a pattern. Possibly now I do. I have been using the 32-bit x86 ghc binary that I downloaded from http://www.haskell.org and running on Ubuntu Linux. I am pretty I can repeat now. Everything is ok until I do "sudo runhaskell Setup.hs install" which installs a new "unix" package that I just built. Of course the "intall" installs into /usr/local/lib/unix-2.3.0.0/ghc-6.8.2. The "install" seems to destroy some ghc compiler state under /usr/local ... This is of course just a theory. However, once I re-install ghc et. al. from the binary download then things are ok again. I have tried the ghc re-install at least 4 times. Hope I am not misleading anybody .. just trying to help! Kind regards, Vasili

3 7

hs-plugins compile error
by Edsko de Vries 03 Jun '08

03 Jun '08

Hi, I'm getting the compilation error that is actually logged on Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/plugins Below is a small diff file that resolves these problems; I don't know what the proper protocol is for submitting these diffs but it may be useful to someone. - E diff -ur plugins-1.2-orig/src/System/Plugins/Env.hs plugins-1.2/src/System/Plugins/Env.hs --- plugins-1.2-orig/src/System/Plugins/Env.hs 2008-06-02 14:57:59.000000000 +0100 +++ plugins-1.2/src/System/Plugins/Env.hs 2008-06-02 15:00:25.000000000 +0100 @@ -73,7 +73,7 @@ import Control.Concurrent.MVar ( MVar(), newMVar, withMVar ) -import Distribution.Package +import Distribution.Package hiding (packageName) import Text.ParserCombinators.ReadP import qualified Data.Map as M diff -ur plugins-1.2-orig/src/System/Plugins/PackageAPI.hs plugins-1.2/src/System/Plugins/PackageAPI.hs --- plugins-1.2-orig/src/System/Plugins/PackageAPI.hs 2008-06-02 14:57:59.000000000 +0100 +++ plugins-1.2/src/System/Plugins/PackageAPI.hs 2008-06-02 14:59:49.000000000 +0100 @@ -40,7 +40,7 @@ #if CABAL == 1 || __GLASGOW_HASKELL__ >= 604 import Distribution.InstalledPackageInfo -import Distribution.Package +import Distribution.Package hiding (depends, packageName) #else import System.Plugins.Package #endif diff -ur plugins-1.2-orig/src/System/Plugins/ParsePkgConfCabal.hs plugins-1.2/src/System/Plugins/ParsePkgConfCabal.hs --- plugins-1.2-orig/src/System/Plugins/ParsePkgConfCabal.hs 2008-06-02 14:57:59.000000000 +0100 +++ plugins-1.2/src/System/Plugins/ParsePkgConfCabal.hs 2008-06-02 14:58:56.000000000 +0100 @@ -6,7 +6,7 @@ ) where import Distribution.InstalledPackageInfo -import Distribution.Package +import Distribution.Package hiding (depends) import Distribution.Version import Data.Char ( isSpace, isAlpha, isAlphaNum, isUpper, isDigit )

5 7

Rewrite class with fundeps in pure h98?
by Darrin Thompson 03 Jun '08

03 Jun '08

I thought that I should be able to write something like the toHtml function below with pure H98, but when I went to write it I ended up needing fundeps. Is there a way to express this without using any extensions? The idea was to take a remotely Dom-like tree and flatten it into a string, but not require any particular string type. Mostly I'm ripping off HStringTemplate for the fun of it. {-# OPTIONS -fglasgow-exts #-} module Control.WebWidget where import Data.Monoid import Data.String data (IsString s, Monoid s) => Dom s = Element s [Attr s] [Dom s] | Text s data (IsString s, Monoid s) => Attr s = Attr s s class (Monoid s, IsString s) => HTML d s | d -> s where toHtml :: d -> s instance (Monoid s, IsString s) => HTML (Dom s) s where toHtml (Element name attrs children) = mconcat [ fromString "<", name, mconcat $ map toHtml attrs, fromString ">", mconcat $ map toHtml children, fromString "</", name, fromString ">" ] toHtml (Text s) = s instance (Monoid s, IsString s) => HTML (Attr s) s where toHtml (Attr key value) = mconcat [ fromString " '", key, fromString "'='", value, fromString "' " ] -- Darrin

3 2

ANN (2 Libs) -- hvac 0.1b, a lightweight web framework and HStringTemplate 0.3
by Sterling Clover 03 Jun '08

03 Jun '08

1) hvac 0.1b: transactional, declarative framework for lightweight web applications. 2) HStringTemplate 0.3 1) hvac 0.1b hvac (short for http view and controller) has been my project for the last little while, and is finally in a fairly usable state, so I'm opening up the repo (darcs get http://community.haskell.org/~sclv/ hvac/) for folks to play with and to get some feedback. While not quite yet ready for hackage, the package as provided should be fully cabal installable. Documentation is available at http:// community.haskell.org/~sclv/hvac/html_docs/hvac/ The aim of hvac is to provide an environment that makes the creation of lightweight fastcgi based web applications as simple as possible, with an emphasis on concise, declarative style code, correct concurrent transactional logic, and transparency in adding caching combinators. There are two included example programs, naturally neither of which is feature complete. They share a common login module of about 50 lines of code, excluding imports, templates, and database schema. The first program is a classic, greenspun-style message board with basic login functionality. It totals roughly 40 lines and tends to use just under 4mb of resident memory on my system. The second is a wiki based on Pandoc and the PandocWiki code. The code totals roughly 30 lines (rendering borrowed from PandocWiki aside) and uses about 5mb of memory. hvac processes all requests in the STM monad, with some bells attached to properly interleave STM with session, database and filesystem operations such that they all conceptually occur together in a single transaction per request. Currently it is only fully tested with sqlite, but it should operate, modulo a few tweaks, with any database accessible via HDBC. hvac is particularly designed to use the HStringTemplate library as an output layer, in a simple declarative fashion. As the StringTemplate grammar is explicitly sub-turing, this ensures a clean separation of program logic from presentation, while providing a nonetheless fairly powerful language to express typical display tasks. The included cache combinators, still experimental, should allow a simple and fine-grained control over the level of caching of various disk-bound operations. Phantom types are used to ensure that no functions that modify state may be cached. To give a flavor of hvac code, the following is the complete (twenty lines!) source of the wiki controller (due to sql statements, some lines are rather long): wikiController tmpl = h |/ "login" *> login_plug tmpl <|> (h |/ "wiki" |\\ \pageName -> h |// "POST" *> withValidation [ ("contents", return) ] (\ [contents] -> do pageId <- selectVal "id from pages where name=?" [toSql pageName] maybe (addErrors [("Login","must be logged in.")] >> continue) (\user -> case fromSql pageId of Just (_::Int) -> execStat "insert into page_hist (pageId,contents,author) values(?,?,?)" [pageId, toSql contents, toSql . userName $ user] Nothing -> do execStat "insert into pages (name,locked) values(?,?)" [toSql pageName, toSql (0::Int)] pid <- selectVal "max(id) from pages" [] execStat "insert into page_hist (pageId,contents,author) values(?,?,?)" [pid, toSql contents, toSql . userName $ user]) =<< getSes continue) <|> do pageId <- selectVal "id from pages where name=?" [toSql pageName] (join $ renderf (tmpl "showPage") ("pageName", pageName) <$> "pageContents" |= selectRow "* from page_hist where pageId=? order by time desc limit 1" [pageId] )) <|> (redirect . ( ++ "/wiki/Index") =<< scriptName) Future directions for work on hvac include: Stress testing for correctness of transactional logic and benchmarks. Exploration of various efficiency tweaks. Unit tests. Further development of the cache combinator API. Improvement of the example apps and addition of a few others (a blog maybe). Expansion of the library of validator functions. Exploration of transferring hvac to the standard FastCGI bindings (currently it uses a custom modified version to work properly with STM). Improvement of the database layer, particularly with regards to common paging functions. Creation of a set of simple combinators for generating CRUD (create read update delete) pages. Creation of a minimal set of standard templates (maybe). 2) HStringTemplate 0.3.1 This release of HStringTemplate (up now at Hackage) fixes a number of bugs pointed out to me by its small but growing user base (thanks, cinema, elliottt!) ranging from the minor (a particular two-level iteration pattern wasn't working properly) to the truly irritating (poor handling of file groups). It's still unfortunately skimpy on the docs, outside of the haddocks and the main StringTemplate grammar documentation at http://www.stringtemplate.org (although the examples from hvac should also prove helpful). However, it does have a set of very nice and handy new features for development. * renderf, a function similar in spirit to printf, that takes an arbitrary number of heterogeneous (String, value) tuples as arguments. This should cut down considerably on long setAttribute chains. Additionally, with custom instances (not, I'll grant, trivial to write) it can be used to declaratively chain together strings of attribute retrieval functions in arbitrary monads, as in the above code example from hvac. * dumpAttribs, a function/template that prints out the tree of the entire attribute environment a template is operating in -- extremely handy for development. * nullGroup, also for use in development, a simple way to display more information about templates that can't be found. Error messages in usafeVolatileDirectoryGroup have also been significantly improved. * getStringTemplate', a version of getStringTemplate guaranteed not to be inlined. While the optimizer will still sometimes rearrange code such that a volatile group is not updated properly, this at least helps remedy the situation (I think). * Some minor changes: For grammar reasons, dots have been removed from template names -- however, underscores and slashes are now available. Additionally, there's a much improved logic for which aspects of a local environment are overridden and preserved when a template is called from another. For both of these libraries, patches, comments, bug reports, requests, and of course contributions more than welcome! Regards, Sterl.

3 3

type-level integers using type families
by Peter Gavin 03 Jun '08

03 Jun '08

Has anyone else tried implementing type-level integers using type families? I tried using a couple of other type level arithmetic libraries (including type-level on Hackage) and they felt a bit clumsy to use. I started looking at type families and realized I could pretty much build an entire Scheme-like language based on them. In short, I've got addition, subtraction, & multiplication working after just a days worth of hacking. I'm going to post the darcs archive sometime, sooner if anyone's interested. I really like the type-families based approach to this, it's a lot easier to understand, and you can think about things functionally instead of relationally. (Switching back and forth between Prolog-ish thinking and Haskell gets old quick.) Plus you can do type arithmetic directly in place, instead of using type classes everywhere. One thing that I'd like to be able to do is lazy unification on type instances, so that things like data True data False type family Cond x y z type instance Cond True y z = y type instance Cond False y z = z will work if the non-taken branch can't be unified with anything. Is this planned? Is it even feasible? I'm pretty sure it would be possible to implement a Lambda like this, but I'm not seeing it yet. Any ideas? Pete

7 9

Implementing ParseChart with Data.Map
by Krasimir Angelov 03 Jun '08

03 Jun '08

Hi, I have to write ParseChart implementation with Data.Map/Set. The chart is type like this: type Chart k v = Map k (Set v) now I need operation like: insert :: k -> v -> Chart k v -> Maybe (Chart k v) where the result is (Just _) if the (k,v) is actually added to the chart or Nothing if it was already there and nothing have to be done. The straight forward implementation is: case Map.lookup k chart of Nothing -> Just (Map.insert k (Set.singleton v) chart) Just set | Set.member v set -> Nothing | otherwise -> Just (Map.insert k (Set.insert v set) chart) The problem with this is that both the Map and the Set are traversed twice. The first time from lookup/member and the second time from insert. Does someone have an idea how to do this with the current libraries? There are the Map.updateLookupWithKey and the Map.alter functions: updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a,Map k a) alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a which are the closest that I need. The problem is that the first doesn't allow the client function to be called if there isn't matching key in the map and the second is doesn't allow to return value from the client function. What I really need is an alterLookúp function: alterLookúp :: Ord k => (Maybe a -> (b,Maybe a)) -> k -> Map k a -> (b,Map k a) The chart manipulation is in the tight loop of my application so I need fast code. Any other ideas? Regards, Krasimir

6 8

Rotating backdrop (aka learning Haskell)
by Yann Golanski 03 Jun '08

03 Jun '08

To help me learn Haskell, I decided on a simple (AH!) problem: given a list of images, display a random one as my desktop backdrop. After some time, change the image. Simple? What I actually want to do is a little more specific: Read a list of images (one per line) from a file. Given that a working day is about 8 hours, I want to see all the images during the day. So, the time between changes should be (nbr_of_images) / (8 * 60 * 60) seconds. Of course, if the file changes (I add or remove any number of images) this need to change and be recalculated. Clearly, I want some interaction with a pseudo-random number generator. Because this is a learning exercise, I want to have a pretty GUI for this. Three buttons: Exit (which quits the application), Reset (re-reads the file whether it changed or not) and Next (display the next image). Then I want a counter and a progress bar telling me when the next change will occur. 1- Get a list out of a file: I managed to do that using the following: parseImageFile :: FilePath -> IO [String] parseImageFile file = do inpStr <- readFile file return $ filter (/="") (breaks (=='\n') inpStr) Nice, simple and I understand what it is doing. 2- Get a random element from a list and remove it: Okay, this I understand less well. I looked at the solutions of problems 23 and 20 in http://www.haskell.org/haskellwiki/99_questions so there is a skeleton there. However, my list is IO [String].... Hum, monads. Any pointers as to how to do that? 3- Wait and do something later.... How, I have no idea how to do that! Help? 4- I guess that progress bars and updating text will be somewhere in the GUI (I chose wxHaskell)... Again, no idea where. 5- How do you call an external program in Haskell? Either xv or Esetroot will do the job of displaying the image. Is there a Haskell native way to do that? Once this is done and I have commented to the code, I will be happy to put it onto the wiki as a teaching aid. Thanks. -- yann(a)kierun.org -= H+ =- www.kierun.org PGP: 009D 7287 C4A7 FD4F 1680 06E4 F751 7006 9DE2 6318

7 8

Mutually Recursive Modules
by Richard Giraud 03 Jun '08

03 Jun '08

Hello I'm using GHC 6.8.2 with mutally recursive modules. I'm familiar with how to do simple cases in GHC ({-# SOURCE #-} and .hs-boot files) but I can't figure out how to get it to work for a particular set of modules. Is it known (i.e., proven) that GHC 6.8.2 can compile any set of mutually recursive modules without refactoring? Are there known limitations? Thanks, Richard G.

3 2

[Newbie question] -- Looping stdin until condition is met
by Martin Blais 02 Jun '08

02 Jun '08

Allright, this is a definitely a newbie question. I'm learning Haskell and going through the exercises in the beautiful Hutton book, and one of them requires for me to write a loop that queries a line from the user (stdin), looping until the user enters a valid integer (at least that's how I want to implement the interface to the exercise). I have tried tons of variants and modifications of code, and I can't find the way to implement this. Here is what my emacs buffer is at now:: import Text.Read import System.IO import qualified Control.Exception as C getNum :: IO Int getNum = do line <- (hGetLine stdin) x <- (C.catch (do return (read line :: Int)) (\e -> getNum)) return x main = do x <- getNum putStr ((show x) ++ "\n") Now, I've tried the Prelude's catch, the Control.Exception catch, I've tried moving it at the top of getnum, I've tried without catch, I've tried a ton of other shtuff, so much that I'm starting to think that Emacs is going to run out of electrons soon. I asked some half-newbie friends who are insanely enthousiastic about Haskell and they can't do it either (I'm starting to think that those enthousiastic friends are dating a beautiful girl with 3 PhDs, but she has a 2-inch thick green and gooey wart smack on her nose and they're so blindly in love that they can't admit that she does). I've asked some university profs and they sidetrack my question by saying I shouldn't do I/O so early. Can anyone here restore my faith in the Haskell section of humanity? 1. How do I catch the exception that is raised from "read"? 2. Where do I find the appropriate information I need in order to fix this? I'm probably just not searching in the right place. (Yes, I've seen the GHC docs, and it doesn't help, maybe I'm missing some background info.) 3. Please do not tell me I should solve the problem differently. Here is the problem I'm trying to solve, and nothing else: "Write a program that reads a line from the user, looping the query until the line contains a valid integer." It shouldn't be too hard i think. The best answer would be a two-liner code example that'll make me feel even more stupid than I already do. Thanks in advance.

5 8