March 2008 - Haskell-Cafe

Starting Haskell with a web application
by Jonathan Gardner 18 May '08

18 May '08

I am sure I am missing something obvious, but since the cafe is the place to ask stupid questions... I am getting more and more excited about Haskell as I learn more and more about it. Professionally, and as a hobby, I love working on web applications. Where do I get started in writing a web app with Haskell? I am looking more for a framework like Pylons and less like Apache, if that helps. I am sure someone has already done the homework on this, so a link will be fine. -- Jonathan Gardner jgardner(a)jonathangardner.net

11 15

Cryptographic hash uniquness (was [Haskell-cafe] Simple network client)
by Peter Verswyvelen 11 May '08

11 May '08

>winds up having a write cache, which is mutable in practice. The >interesting thing is that the block's location is the cryptographic >hash of its contents, which leads to all sorts of neat properties (as >well as requiring immutability). That's interesting. When I developed a version control system for a customer, I also used a cryptographic hash as the database key of file+content in question, but I was afraid I might have clashes (two files with different content generating the same hash)... My intuition told me that the odds of two cryptographic hashes (on meaningful content) colliding was much less than the earth being destroyed by an asteroid... But this is just intuition... What does computer science tell us about this? Thank you, Peter

6 6

Old editions of The Monad.Reader lost
by Henk-Jan van Tuyl 10 May '08

10 May '08

L.S., Now that all hawiki pages have been removed, we have lost some valuable information. For example The Monad.Reader; on http://www.haskell.org/haskellwiki/The_Monad.Reader it says: Older editions can be found on the old Haskell wiki – they haven't been included here for licensing reasons. The page it links to, a hawiki page, has dissappeared. I propose to bring at least the The Monad.Reader pages back. Backups of these pages can be found at the Wayback Machine, but there is no guarantee that will always be there. -- Met vriendelijke groet, Henk-Jan van Tuyl -- http://functor.bamikanarie.com http://Van.Tuyl.eu/ --

3 6

(flawed?) benchmark : sort
by Krzysztof Skrzętnicki 23 Apr '08

23 Apr '08

Hi I was playing with various versions of sorting algorithms. I know it's very easy to create flawed benchmark and I don't claim those are good ones. However, it really seems strange to me, that sort - library function - is actually the worse measured function. I can hardly belive it, and I'd rather say I have made a mistake preparing it. The overall winner seems to be qsort_iv - which is nothing less but old sort replaced by mergesort now. Any clues? Regards Christopher Skrzętnicki --- cut here --- [Tener@laptener haskell]$ ghc -O2 --make qsort.hs && ./qsort +RTS -sstderr -RTS > /dev/null [1 of 1] Compiling Main ( qsort.hs, qsort.o ) Linking qsort ... ./qsort +RTS -sstderr (1.0,"iv") (1.1896770400256864,"v") (1.3091609772011856,"treeSort") (1.592515715933153,"vii") (1.5953543402198838,"vi") (1.5961286512637272,"iii") (1.8175480563244177,"i") (1.8771604568641642,"ii") (2.453160634439497,"mergeSort") (2.6627090768870216,"sort") 26,094,674,624 bytes allocated in the heap 12,716,656,224 bytes copied during GC (scavenged) 2,021,104,592 bytes copied during GC (not scavenged) 107,225,088 bytes maximum residency (140 sample(s)) 49773 collections in generation 0 ( 21.76s) 140 collections in generation 1 ( 23.61s) 305 Mb total memory in use INIT time 0.00s ( 0.00s elapsed) MUT time 20.39s ( 20.74s elapsed) GC time 45.37s ( 46.22s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 65.76s ( 66.96s elapsed) %GC time 69.0% (69.0% elapsed) Alloc rate 1,279,723,644 bytes per MUT second Productivity 31.0% of total user, 30.5% of total elapsed --- cut here --- {-# OPTIONS_GHC -O2 #-} module Main where import System.CPUTime import System.IO import System.Environment import System.Random import Data.List( partition, sort ) data Tree a = Node (Tree a) a (Tree a) | Leaf qsort_i [] = [] qsort_i (x:xs) = qsort_i (filter (< x) xs) ++ [x] ++ qsort_i (filter (>= x) xs) qsort_ii [] = [] qsort_ii (x:xs) = let (ls,gt) = partition (< x) xs in qsort_ii ls ++ [x] ++ qsort_ii gt qsort_iii xs = qsort_iii' [] xs qsort_iii' acc [] = acc qsort_iii' acc (x:xs) = let (ls,gt) = partition (< x) xs in let acc' = (x:(qsort_iii' acc gt)) in qsort_iii' acc' ls qsort_v [] = [] qsort_v (x:xs) = let (xlt, xgt ) = foldl (\ (lt,gt) el -> case compare x el of GT -> (el:lt, gt) _ -> (lt, el:gt) ) ([],[]) xs in qsort_v xlt ++ [x] ++ qsort_v xgt -- zmodyfikowany i qsort_vi [] = [] qsort_vi (x:xs) = qsort_vi (filter (\y-> compare x y == GT) xs) ++ [x] ++ qsort_vi (filter (\y-> compare x y /= GT) xs) -- zmodyfikowany iii qsort_vii xs = qsort_vii' [] xs qsort_vii' acc [] = acc qsort_vii' acc (x:xs) = let (ls,gt) = partition (\y-> compare x y == GT) xs in let acc' = (x:(qsort_vii' acc gt)) in qsort_vii' acc' ls -- qsort is stable and does not concatenate. qsort_iv xs = qsort_iv' (compare) xs [] qsort_iv' _ [] r = r qsort_iv' _ [x] r = x:r qsort_iv' cmp (x:xs) r = qpart cmp x xs [] [] r -- qpart partitions and sorts the sublists qpart cmp x [] rlt rge r = -- rlt and rge are in reverse order and must be sorted with an -- anti-stable sorting rqsort_iv' cmp rlt (x:rqsort_iv' cmp rge r) qpart cmp x (y:ys) rlt rge r = case cmp x y of GT -> qpart cmp x ys (y:rlt) rge r _ -> qpart cmp x ys rlt (y:rge) r -- rqsort is as qsort but anti-stable, i.e. reverses equal elements rqsort_iv' _ [] r = r rqsort_iv' _ [x] r = x:r rqsort_iv' cmp (x:xs) r = rqpart cmp x xs [] [] r rqpart cmp x [] rle rgt r = qsort_iv' cmp rle (x:qsort_iv' cmp rgt r) rqpart cmp x (y:ys) rle rgt r = case cmp y x of GT -> rqpart cmp x ys rle (y:rgt) r _ -> rqpart cmp x ys (y:rle) rgt r -- code by Orcus -- Zadanie 9 - merge sort mergeSort :: Ord a => [a] -> [a] mergeSort [] = [] mergeSort [x] = [x] mergeSort xs = let(l, r) = splitAt (length xs `quot` 2) xs in mergeSortP (mergeSort l) (mergeSort r) -- funkcja pomocnicza scalajÄ…ca dwie listy uporzÄ…dkowane w jednÄ… mergeSortP :: Ord a => [a] -> [a] -> [a] mergeSortP xs [] = xs mergeSortP [] ys = ys mergeSortP (x:xs) (y:ys) | x <= y = x:(mergeSortP xs (y:ys)) | otherwise = y:(mergeSortP (x:xs) ys) -- Zadanie 10 - tree sort treeSort :: Ord a => [a] -> [a] -- pointless po raz drugi treeSort = (treeSortInorder . treeSortToTree) treeSortToTree :: Ord a => [a] -> Tree a treeSortToTree [] = Leaf treeSortToTree (x:xs) = let (xlt, xgt) = foldl (\ (lt,gt) el -> case compare x el of GT -> (el:lt, gt) _ -> (lt, el:gt) ) ([],[]) xs in Node (treeSortToTree xlt) x (treeSortToTree xgt) treeSortInorder :: Ord a => Tree a -> [a] treeSortInorder Leaf = [] treeSortInorder (Node l x r) = (treeSortInorder l) ++ [x] ++ (treeSortInorder r) -- end code by Orcus -- big_number = 1000000 :: Int main = do gen <- getStdGen let xs' = randomRs (1::Int, big_number) gen xs <- return (take big_number xs') t1 <- getCPUTime print (qsort_i xs) -- i t2 <- getCPUTime print (qsort_ii xs) -- ii t3 <- getCPUTime print (qsort_iii xs) -- iii t4 <- getCPUTime print (qsort_iv xs) -- iv t5 <- getCPUTime print (qsort_v xs) -- v t6 <- getCPUTime print (qsort_vi xs) -- vi t7 <- getCPUTime print (qsort_vii xs) -- vii t8 <- getCPUTime print (sort xs) -- sort t9 <- getCPUTime print (mergeSort xs) -- mergeSort t10 <- getCPUTime print (treeSort xs) -- treeSort t11 <- getCPUTime let getTimes xs = zipWith (-) (tail xs) xs let timers = [t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11] let times = getTimes timers let table = zip times ["i","ii","iii","iv", "v", "vi", "vii", "sort","mergeSort","treeSort"] let sorted = sort table let scaled = map (\(x,n) -> (((fromIntegral x / (fromIntegral $ fst (head sorted)))::Double),n)) sorted let toShow = concatMap (\x-> show x ++ "\n") scaled hPutStr stderr toShow main_small = do gen <- getStdGen let xs' = randomRs (1::Int, 100000) gen xs <- return (take big_number xs') t1 <- getCPUTime print (qsort_iv xs) -- iv t2 <- getCPUTime print (sort xs) -- sort t3 <- getCPUTime print (mergeSort xs) -- mergeSort t4 <- getCPUTime print (treeSort xs) -- treeSort t5 <- getCPUTime let getTimes xs = zipWith (-) (tail xs) xs let timers = [t1,t2,t3,t4,t5] let times = getTimes timers let table = zip times ["iv", "sort","mergeSort","treeSort"] let sorted = sort table let scaled = map (\(x,n) -> (((fromIntegral x / (fromIntegral $ fst (head sorted)))::Double),n)) sorted let toShow = concatMap (\x-> show x ++ "\n") scaled hPutStr stderr toShow hPrint stderr times --- cut here ---

33 117

Anyone mind proofing a short monad transformers explanation?
by Jack Kelly 22 Apr '08

22 Apr '08

I sent this to a friend who asked me about monad transformers and he reckons it should be saved somewhere. If anyone feels up to giving it a quick fact-check, that'd be great. I'm not sure what to do with it, though. It doesn't seem to be made of the right stuff for a tutorial but I'm not sure what to do with it. --- SNIP --- Basically it's like making a double, triple, quadruple, ... monad by wrapping around existing monads that provide wanted functionality. You have an innermost monad (usually Identity or IO but you can use any monad). You then wrap monad transformers around this monad to make bigger, better monads. Concrete example: Suppose I was writing a server. Each client thread must be of type IO () (that's because forkIO :: IO () -> IO ThreadID)). Suppose also that this server has some configuration that (in an imperative program) would be global that the clients all need to query. > data Config = Config Foo Bar Baz One way of doing this is to use currying and making all the client threads of type Config -> IO (). Not too nice because any functions they call have to be passed the Config parameter manually. The Reader monad solves this problem but we've already got one monad. We need to wrap IO in a ReaderT. The type constructor for ReaderT is ReaderT r m a, with r the shared environment to read from, m the inner monad and a the return type. Our client_func becomes: > client_func :: ReaderT Config IO () We can then use the ask, asks and local functions as if Reader was the only Monad: (these examples are inside do blocks) > p <- asks port (Assuming some function port :: Config -> Int or similar.) To do stuff in IO (or in the general case any inner monad) the liftIO function is used to make an IO function work in this wrapped space: (given h :: Handle, the client's handle) > liftIO $ hPutStrLn h "You lose" > liftIO $ hFlush h IO is once again special. For other inner monads, the lift function does the same thing. Note also that IO has no transformer and must therefore always be the innermost monad. This is all well and good, but the client_func now has type ReaderT Config IO () and forkIO needs a function of type IO (). The escape function for Reader is runReader :: Reader r a -> r -> a and similarly for ReaderT the escape function is runReaderT :: ReaderT r m a -> r -> m a: (Given some c :: Config that's been assembled from config files or the like) > forkIO (runReaderT client_func c) Will do the trick. Monad transformers are like onions. They make you cry but you learn to appreciate them. Like onions, they're also made of layers. Each layer is the functionality of a new monad, you lift monadic functions to get into the inner monads and you have transformerised functions to unwrap each layer. They're also like a present in that regard: in this example we unwrapped the outer wrapping paper to get to the present: an object of type IO (), which lets us make haskell do something.

3 2

Separate a string into a list of strings
by Sara Kenedy 18 Apr '08

18 Apr '08

Hi all, I want to write a function to separate a string into a list of strings separated by commas. Example: separate :: String -> [String] separate "Haskell, Haskell, and Haskell" = ["Haskell", "Haskell", "and Haskell"] If anyone has some ideas, please share with me. Thanks. S.

14 35

Parsec Expected Type
by Paul Keir 07 Apr '08

07 Apr '08

Hi, Does anyone know why this reduced Parsec production stops compilation, and how I can fix it? tester = reserved "parameter" <|> do { reserved "dimension"; symbol ":" } Thanks, Paul

6 9

HDBC, character encoding
by Adrian Neumann 05 Apr '08

05 Apr '08

Hi, I wrote a CGI program to access a Postgres database using HDBC. The database stores books and I want to display those from a certain author. Everything works fine, unless I search for someone with an umlaut in his name. Böll, for example. I have a function like this > bookByAuthor :: Connection -> AutorName -> IO [[String]] > bookByAuthor c aName = do > writeFile "./err.log" ((show aName)++" "++(show $ toSql aName)) > rows <- quickQuery c "SELECT * FROM buecher WHERE lower (autor_name) LIKE ? ORDER BY autor_name, buch_name" [toSql $ map toLower $ '%':aName++"%"] > return $ map (map fromSql) rows It returns me a SqlError. However, doing the same in ghci works perfectly. I can't understand why. err.log contains > "b\195\182ll" SqlString "b\195\182ll" which is ok I think. Since > quickQuery c "SELECT * FROM buecher WHERE lower(autor_name) LIKE ? ORDER BY autor_name, buch_name" [toSql "%b\195\182%"] works in ghci. I have tried "b\246ll", but that doesn't even work in ghci, although the database-encoding is utf-8. This all is really annoying... Adrian

6 8

Type constraints for class instances
by Krzysztof Skrzętnicki 03 Apr '08

03 Apr '08

Hello everyone, I'm working on a small module for comparing things incomparable with Ord. More precisely I want to be able to compare equal infinite lists like [1..]. Obviously (1) compare [1..] [1..] = _|_ It is perfectly reasonable for Ord to behave this way. Hovever, it doesn't have to be just this way. Consider this class class YOrd a where ycmp :: a -> a -> (a,a) In a way, it tells a limited version of ordering, since there is no way to get `==` out of this. Still it can be useful when Ord fails. Consider this code: (2) sort [ [1..], [2..], [3..] ] It is ok, because compare can decide between any elements in finite time. However, this one (3) sort [ [1..], [1..] ] will fail because of (1). Compare is simply unable to tell that two infinite list are equivalent. I solved this by producing partial results while comparing lists. If we compare lists (1:xs) (1:ys) we may not be able to tell xs < ys, but we do can tell that 1 will be the first element of both of smaller and greater one. You can see this idea in the code below. --- cut here --- {-# OPTIONS_GHC -O2 #-} module Data.YOrd where -- Well defined where Eq means equality, not only equivalence class YOrd a where ycmp :: a -> a -> (a,a) instance (YOrd a) => YOrd [a] where ycmp [] [] = ([],[]) ycmp xs [] = ([],xs) ycmp [] xs = ([],xs) ycmp xs'@(x:xs) ys'@(y:ys) = let (sm,gt) = x `ycmp` y in let (smS,gtS) = xs `ycmp` ys in (sm:smS, gt:gtS) ycmpWrap x y = case x `compare` y of LT -> (x,y) GT -> (y,x) EQ -> (x,y) -- biased - but we have to make our minds! -- ugly, see the problem below instance YOrd Int where ycmp = ycmpWrap instance YOrd Char where ycmp = ycmpWrap instance YOrd Integer where ycmp = ycmpWrap -- ysort : sort of mergesort ysort :: (YOrd a) => [a] -> [a] ysort = head . mergeAll . wrap wrap :: [a] -> [[a]] wrap xs = map (:[]) xs mergeAll :: (YOrd a) => [[a]] -> [[a]] mergeAll [] = [] mergeAll [x] = [x] mergeAll (a:b:rest) = mergeAll ((merge a b) : (mergeAll rest)) merge :: (YOrd a) => [a] -> [a] -> [a] merge [] [] = [] merge xs [] = xs merge [] xs = xs merge (x:xs) (y:ys) = let (sm,gt) = x `ycmp` y in sm : (merge [gt] $ merge xs ys) --- cut here --- I'd like to write the following code: instance (Ord a) => YOrd a where ycmp x y = case x `compare` y of LT -> (x,y) GT -> (y,x) EQ -> (x,y) But i get an error "Undecidable instances" for any type [a]. Does anyone know the way to solve this? Best regards Christopher Skrzętnicki

5 9

Template Haskell -- when are things evaluated?
by Emil Axelsson 02 Apr '08

02 Apr '08

Hello all! Up until yesterday I thought I understood the basics of Template Haskell, but now I'm a little confused. Consider the following code module A where a1 = [| (2::Int) + 2 |] a2 = let x = (2::Int) + 2 in [| x |] a3 = [| y |] where y = (2::Int) + 2 z = (2::Int) + 2 a4 = [| z |] module B where import A a1S = $a1 a2S = $a2 a3S = $a3 a4S = $a4 I'd have thought that in all four cases the addition was evaluated at compile-time, but compiling with -ddump-splices reveals that this is only the case for a2 and a3. Is there a general reliable rule for when things are evaluated? Thanks, / Emil

3 5