December 2009 - Haskell-Cafe

ghc 6.12.1 and regex
by Paulo Tanimoto 29 Dec '09

29 Dec '09

Oh, I forgot to "reply-to-all". ---------- Forwarded message ---------- From: Paulo Tanimoto <tanimoto(a)arizona.edu> Date: Tue, Dec 29, 2009 at 9:39 AM Subject: Re: [Haskell-cafe] ghc 6.12.1 and regex To: David Fox <ddssff(a)gmail.com> Hi David, On Tue, Dec 29, 2009 at 9:28 AM, David Fox <ddssff(a)gmail.com> wrote: > Is anyone else seeing this problem: > >> :m +Text.Regex.Posix >> "\250" =~ "\250" :: Bool > True >> "\250" =~ "[\250]" :: Bool > False I also get that on GHC 6.10.4. On the other hand: $ cabal update $ cabal install regex-tdfa $ ghci > :m +Text.Regex.TDFA > "\250" =~ "\250" :: Bool True > "\250" =~ "[\250]" :: Bool True But the author says it's not fully Posix yet: http://hackage.haskell.org/package/regex-tdfa Paulo

1 0

semantics of type synonym
by pbrowne 29 Dec '09

29 Dec '09

Hi, I am studying the underlying semantics behind Haskell and to what degree those semantics are actually implemented. I need to clarify what a *type synonym* actual means in relation to Haskell's logic (or formal semantics). I used the following type synonym: type Name = String getName(n) = n I checked the types with two tests: -- test 1 :t "ww" "ww" :: [Char] -- test 2 :t getName("ww") getName("ww") :: Name Obviously I get two different types. In the case of the function Haskells type system seems to pick up enough information to determine that “ww” is a Name. But I am not sure what is happening with the literal "ww" in the first test. Pat

6 9

Performance of functional priority queues
by Richard O'Keefe 29 Dec '09

29 Dec '09

There's a current thread in the Erlang mailing list about priority queues. I'm aware of, for example, the Brodal/Okasaki paper and the David King paper. I'm also aware of James Cook's priority queue package in Hackage, have my own copy of Okasaki's book, and have just spent an hour searching the web. One of the correspondents in that thread claims that it is provably impossible to have an efficient priority queue implementation without mutability. I think he's cuckoo. But I'd like to have some numbers to back me up. Can anyone point me to some actual benchmark results comparing priority queue performance *with* mutation and priority queue performance *without* mutation, in the same functional or mostly-functional language?

16 24

Native CLient
by Joan Miller 29 Dec '09

29 Dec '09

Native CLient (NaCl) [1] is a technology very cool which lets to run native code in web applications, and it's being integrated in some languages as Python [2]. Go [3] already has rudimentary support for Native Client (and it's logical since that both technologies are from Google) I hope that Haskell also gets support for NaCl and doesn't loose this train else a language as Go could get every time more users that until now they had gone to Haskell or Erlang mainly for its concurrency. [1] http://code.google.com/p/nativeclient/ [2] http://lackingrhoticity.blogspot.com/2009/06/python-standard-library-in-nat… [3] http://golang.org/pkg/exp/nacl/

2 3

Invertible functions list
by Jonathan Fischoff 29 Dec '09

29 Dec '09

Hi, I would to create a list of tuples (or something similar) of invertible functions [((a -> b), (b -> a)), ((b -> c), (c -> b)), .... Such that I could call forward invertibleFuctionList domainValue = ? -- composite all the functions backward invertibleFuctionList rangeValue = forward (reverse invertibleFuctionList) rangeValue -- or something similar I would also like to concat them. This sounds like a job for GADT that someone might have already tackled. Any ideas? -Jonathan

5 8

Haskell Platform - distiguish packages in Hackage
by Radoslav Dorcik 29 Dec '09

29 Dec '09

Hello, is it possible to distiguish which package is included at Haskell Platform directly from Hackage web interface or `cabal info` ? So anybody can recognize if the dependecy of his package is going from platform or not without platform installed. Thanks, Rado

1 0

Request to review my attempt at understanding Monads
by CK Kashyap 29 Dec '09

29 Dec '09

Hi, I've been reading the papers titled "Comprehending Monads" and "Monadic Parser Combinator" to understand Monads and I think I am beginning to understand it. In my attempt to validate my understanding, I've written my version of List data structure with Monadic behaviour - I'd appreciate answers to the following queries - 1. Comments about the functions I've written 2. I've used the do notation at the bottom which is a result of my List being a Monad - are there any other benefits that comes in because of List being a Monad? What would MonadPlus provide me? 3. The comprehension syntax for Lists in Haskell - can that be used in anyway for other Monads? Regards, Kashyap import Monad ( MonadPlus(..) ) data List a = Cons a (List a) | Empty deriving Show --myMap :: (t -> a) -> List t -> List a myMap :: (t -> a) -> List t -> List a myMap f Empty = Empty myMap f (Cons a rest) = Cons (f a) (myMap f rest) --myAppend :: List a -> List a -> List a myAppend :: List a -> List a -> List a myAppend Empty l = l myAppend l Empty = l myAppend (Cons a rest) l = Cons a (myAppend rest l) --myConcat :: List (List a) -> List a myConcat :: List (List a) -> List a myConcat Empty= Empty myConcat (Cons Empty rest)= myConcat rest myConcat (Cons list rest)= myAppend list (myConcat rest) instance Monad List where return a = Cons a Empty Empty >>= f = Empty l >>= f = myConcat (myMap f l) instance MonadPlus List where p `mplus` q = myAppend p q mzero= Empty list2myList :: [a] -> List a list2myList [] = Empty list2myList (x:xs) = Cons x (list2myList xs) l1 = list2myList [1..10] l2 = do x <- l1 y <- Cons (2*x) Empty return y

7 9

Design question
by haskell＠kudling.de 29 Dec '09

29 Dec '09

Hi, i am not quite sure how to do this in the most elegant way: I have some data structures: data A = A Double data B = B Double data C = C Double ... and i want to allow only a subset in another data structure, so i did something like this: data SubSet = SubSetA A | SubSetC C and use it in Foo: data Foo = Foo [SubSet] No i want to perform a polymorphic operation on the contents of A,B,C, e.g. doSomething :: Foo -> [Double] doSomething (Foo s) = map doSomethingElse s Now i have two questions: 1) Is the way i define and use "SubSet", the only/valid way to define subsets? 2) What's the best way to make "doSomethingElse" polymorphic? There's the tedious way: doSomethingElse (SubSetA x) = doSomethingElse x doSomethingElse (SubSetB x) = doSomethingElse x or i could make SubSet and A,B,C instances of a type class with the function "doSomethingElse". But i have several different subsets so the type class aproach feels like overkill for these helper structures. Whatever my approach is, it does not feel right. Can you help me step back and get the picture? Thanks, Lenny

6 7

Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)
by Dave Bayer 29 Dec '09

29 Dec '09

Here is another prime sieve. It is about half the length of the fastest contributed code (ONeillPrimes) and nearly as fast until it blows up on garbage collection: > % cat ONeillPrimes.hs | grep -v "^--" | wc > 185 1105 6306 > % cat BayerPrimes.hs | grep -v "^--" | wc > 85 566 2418 > > [Integer] -O 1*10^6 2*10^6 3*10^6 4*10^6 5*10^6 > --------------------------------------------------------- > ONeillPrimes | 3.555 | 7.798 | 12.622 | 18.927 | 23.529 > BayerPrimes | 3.999 | 8.895 | 18.003 | 22.977 | 38.053 I wrote this as an experiment in coding data structures in Haskell's lazy evaluation model, rather than as explicit data. The majority of the work done by this code is done by "merge"; the multiples of each prime percolate up through a tournament consisting of a balanced tree of suspended "merge" function calls. In order to create an infinite lazy balanced tree of lists, the datatype > data List a = A a (List a) | B [a] is used as scaffolding. One thinks of the root of the infinite tree as starting at the leftmost child, and crawling up the left spine as necessary. What I'm calling a "venturi" > venturi :: Ord a => [[a]] -> [a] merges an infinite list of infinite lists into one list, under the assumption that each list, and the heads of the lists, are in increasing order. This could be a generally useful function. If one can think of a better way to write "venturi", swapping in your code would in particular yield a faster prime sieve. I found that a tertiary merge tree was faster than a binary merge tree, because this leads to fewer suspensions. One can speed this code up a bit by interleaving strict and lazy calls, but I prefer to leave the code short and readable. It is bizarre that > trim p = let f m x = mod x m /= 0 in filter (f p) lurks in the prime sieve code, but it is only used with primes of size up to the square root of the largest output prime. I tried more thoughtful alternatives, and they all slowed down the sieve. Sometimes dumb is beautiful. Thanks to apfelmus for various helpful remarks that lead me to think of this approach. Here is the code: > module BayerPrimes (venturi,primes) where > > -- Code for venturi :: Ord a => [[a]] -> [a] > > merge :: Ord a => [a] -> [a] -> [a] -> [a] > merge xs@(x:xt) ys@(y:yt) zs@(z:zt) > | x <= y = if x <= z > then x : (merge xt ys zs) > else z : (merge xs ys zt) > | otherwise = if y <= z > then y : (merge xs yt zs) > else z : (merge xs ys zt) > merge _ _ _ = undefined > > data List a = A a (List a) | B [a] > > mergeA :: Ord a => List a -> List a -> List a -> List a > mergeA (A x xt) ys zs = A x (mergeA xt ys zs) > mergeA (B xs) ys zs = mergeB xs ys zs > > mergeB :: Ord a => [a] -> List a -> List a -> List a > mergeB xs@(x:xt) ys@(A y yt) zs = case compare x y of > LT -> A x (mergeB xt ys zs) > EQ -> A x (mergeB xt yt zs) > GT -> A y (mergeB xs yt zs) > mergeB xs (B ys) zs = mergeC xs ys zs > mergeB _ _ _ = undefined > > mergeC :: Ord a => [a] -> [a] -> List a -> List a > mergeC xs@(x:xt) ys@(y:yt) zs@(A z zt) > | x < y = if x < z > then A x (mergeC xt ys zs) > else A z (mergeC xs ys zt) > | otherwise = if y < z > then A y (mergeC xs yt zs) > else A z (mergeC xs ys zt) > mergeC xs ys (B zs) = B $ merge xs ys zs > mergeC _ _ _ = undefined > > root :: Ord a => List a -> [List a] -> [a] > root (A x xt) yss = x : (root xt yss) > root (B xs) (ys:zs:yst) = root (mergeB xs ys zs) yst > root _ _ = undefined > > wrap :: [a] -> List a > wrap [] = B [] > wrap (x:xt) = A x $ B xt > > triple :: Ord a => [List a] -> [List a] > triple (x:y:z:xs) = mergeA x y z : (triple xs) > triple _ = undefined > > group :: Ord a => [List a] -> [List a] > group (x:y:xt) = x : y : (group $ triple xt) > group _ = undefined > > venturi :: Ord a => [[a]] -> [a] > venturi (x:xt) = root (wrap x) $ group $ map wrap xt > venturi _ = undefined > > -- Code for primes :: Integral a => [a] > > diff :: Ord a => [a] -> [a] -> [a] > diff xs@(x:xt) ys@(y:yt) = case compare x y of > LT -> x : (diff xt ys) > EQ -> (diff xt yt) > GT -> (diff xs yt) > diff _ _ = undefined > > trim :: Integral a => a -> [a] -> [a] > trim p = let f m x = mod x m /= 0 in filter (f p) > > seed :: Integral a => [a] > seed = [2,3,5,7,11,13,17] > > wheel :: Integral a => [a] > wheel = drop 1 [ m*j + k | j <- [0..], k <- ws ] > where m = foldr1 (*) seed > ws = foldr trim [1..m] seed > > multiples :: Integral a => [a] -> [[a]] > multiples ws = map fst $ tail $ iterate g ([], ws) > where g (_,ps@(p:pt)) = ([ m*p | m <- ps ], trim p pt) > g _ = undefined > > primes :: Integral a => [a] > primes = seed ++ (diff wheel $ venturi $ multiples wheel)

6 8

FGL/Haskell and Hierarchical Clustering/dendograms
by Nikolas Borrel-Jensen 29 Dec '09

29 Dec '09

Hi! I have some trouble implementing single-linkage clustering algorithm by using a minimum-spanning tree, so I would appreciate if some of you could give me some advise. I am implementing a single-linkage clustering algorithm, and my approach is to use minimum spanning trees for that task. I am using the library FGL ( http://web.engr.oregonstate.edu/~erwig/fgl/haskell/) and I have managed to compute a minimum spanning tree from an arbitrary fully connected graph with 5 nodes. I get [ [(4,0) ] , [ (3,1) , (4,0) ] , [ (1,1) , (3,1) , (4,0) ] , [ (2,3) , (4,0) ] , [ (5,12) , (2,3) , (4,0) ] ], which is the root path tree of the minimum spanning tree created by the function msTreeAt. >From that I would create a dendrogram. [ (1,1) , (3,1) , (4,0) ] is telling that node 1,3 and 4 has the same cost, namely cost 1. Therefore these are merged at level 1. At level 1 we now have 3 clusters: (1,3,4), 2 and 5. Now the second lowest should be merged, that is 2 and 4. BUT because 4 is already merged in the cluster (1,3,4), we should merge (1,3,4) and 2 at level 3 (because the cost is 3). Now at level 3 we have 2 clusters, (1,2,3,4) and 5. Now we merge the last one at level 12: (1,2,3,4,5), and we are finished. I have very hard to see, how this could be done efficiently without pointers (as in C). I have thought of just saving the nodes from the start of the root path, and traversing it, but a lot of searching should be done all the time. Can you please give me some advise on that? Kind regards Nikolas Borrel-Jensen Computer Science University Of Copenhagen

3 4