- Haskell-Cafe - Haskell.org

will the real quicksort please stand up? (or: sorting a > million element list)
by Thomas Hartman 20 Nov '07

20 Nov '07

It has been noted in a few places that the 2 line quicksort demo in the Introduction section of the haskell wiki http://www.haskell.org/haskellwiki/Introduction isn't a "real" quicksort, and wouldn't scale well with longer lists. Interested, and wanting to put my recently learned test data generating skills to the test, I put this to the test with a little suite for various versions of quickcheck I found lying around. My patience extends to <3 minutes for waiting for a result, which for my tests was about the amount needed for a million integer long list. This was definitely faster for the "treesort" below than the naive quicksort from the wiki. (Prelude sort, which I think is mergesort, just blew the stack.) I wonder if there are "tricks" or lore that could be applied to get better results or insight. t. {-import Control.Monad (when) import Control.Monad.ST import Data.Array.ST import Data.Array.IArray import Data.Array.MArray import System.IO.Unsafe import Control.Monad -} import Test.QuickCheck hiding (test) import System.Random import Data.List {- $ time ghci -e 'test treesort 6' quicksort.hs # a "real" quicksort, according to roconnor 1000000 real 2m18.702s user 1m3.296s sys 0m0.453s $ time ghci -e 'test qs1 6' quicksort.hs # "naive" (from the wiki intro to haskell, not a "real" quicksort 1000000 real 4m18.174s user 1m57.615s sys 0m0.665s $ time ghci -e 'test sort 6' quicksort.hs # mergesort from the prelude *** Exception: stack overflow real 0m13.634s user 0m3.805s sys 0m0.446s hartthoma@linuxpt:~/ProjectRepos/learning/quicksort> -} -- For interactive development, I wound up working in hugs +S +I, -- because ghci in emacs tended to lock up -- hugs just segfaults, but at least the computer doesn't lock. -- by the way, is there a way to get ghci to behave similarly to hugs? (restricted memory mode?) -- t1 and t2 are about the same speed for n = 4, got bored of waiting for n great. -- naive, "not really" quicksort according to recent reddit discussion. test sortf n = genlist n >>= return . ( length . sortf ) -- naive qs1 [] = [] qs1 (x:xs) = qs1 (filter (< x) xs) ++ [x] ++ qs1 (filter (>= x) xs) -- roconnor claims that "real" quicksort in haskell is really treesort. -- from http://programming.reddit.com/info/2h0j2/comments --I'm talking about a deforested version of tree sort. In tree sort you build a binary search tree by adding the head of the list to the root of the tree, and then building binary search trees for those items less than the root, and those items greater than the root. qs2 l = treeSort l treeSort l = foldTree (\x lft rht -> lft++[x]++rht) [] (mkTree l) -- After building the search tree, it is turned into a list by folding \x lft rht -> lft++[x]++rht. foldTree f g Leaf = g foldTree f g (Node x l r) = f x (foldTree f g l) (foldTree f g r) mkTree [] = Leaf mkTree (x:xs) = Node x (mkTree (filter (<= x) xs)) (mkTree (filter (x <) xs)) -- If you deforest this algorithm (removing the intermediate tree structure) you are left with -- treeSort' [] = [] -- treeSort' (x:xs) = treeSort' (filter (<= x) xs) ++ [x] ++ treeSort' (filter (x <) xs) -- for testing genlist n = rgen ( vector $ 10^n ) :: IO [Int] rgenIntList = rgen (arbitrary :: Gen [Int]) :: IO [Int] rgen gen = do sg <- newStdGen return $ generate 10000 sg gen data Tree a = Leaf | Node a (Tree a) (Tree a) --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

7 8

user error when using Text.Regex.PCRE
by Olivier Boudry 20 Nov '07

20 Nov '07

Hi all, I'm getting a strange user error when working with Data.ByteString.Char8 and Text.Regex.PCRE. Error I get is: CustomerMaster: user error (Text.Regex.PCRE.ByteString died: (ReturnCode 0,"Ptr parameter was nullPtr in Text.Regex.PCRE.Wrap.wrapMatch cstr")) The part of the code causing problems is at the end of this e-mail. The complete code is attached. I'm working at cleansing customer addresses for a ERP system data migration. The failing function is supposed to split some bytestrings using a list of regular expressions (split on words like suite, building, attention, etc...) stored in the "tags" binding. I use a foldl' to try each regular expression on each address (addr is a list of address part, can be seen as a list of bytestring values). The funny and weird thing is that when I have only one regular expression in tags, it works. When I have more than one regular expression in tags it fails (user error) the first time one of the regular expression matches. A match replaces the current address part with 3 new parts, before, match, after. The next regular expression in the tags list will test the new before and after parts. I presume it's the testing of those newly created parts that causes the problem. Any idea about what could go wrong here? Thanks, Olivier. === code === -- | Split unparsed address parts on keywords (suite, building, doors, etc...) splitOnTags :: AddressState splitOnTags = do addr <- get put $ foldl' f addr tags where f a t = concatMap (split t) a split (T {partType = p, regex = r}) a@(AP X v) | BS.null y = [a] | otherwise = [AP X x, AE p, AP X z] -- new address parts where (x, y, z) = match r v split _ a = [a] -- | Regex and part type representing tags used for splitting addresses tags :: [Tag] tags = [T AT (makeRegexOpts compCaseless execBlank "\\b(?:ATTN|ATTENTION|C/O)\\b[[:punct:]]?") (BS.pack "ATTN: ") ,T PB (makeRegexOpts compCaseless execBlank "\\b(?:(?:P\\.?\\s?O\\.?\\s*)BOX|C\\.P\\.|POSTFACH)\ \[[:punct:]]?\\s+(?:NO.\\s+)?") (BS.pack "PO BOX: ") ,T BLDG (makeRegexOpts compCaseless execBlank "\\b(?:BLDG|BUILDING|HANGAR)[[:punct:]]?") (BS.pack "BLDG: ") ,T DOCK (makeRegexOpts compCaseless execBlank "\\bDOCK[[:punct:]]?") (BS.pack "DOCK: ") ,T STE (makeRegexOpts compCaseless execBlank "\\b(?:SUITE|STE|APT|ROOM)[[:punct:]]?\ \\\s+(?:NO[[:punct:]]?)?") (BS.pack "STE: ") ,T UNIT (makeRegexOpts compCaseless execBlank "\\bUNIT[[:punct:]]?") (BS.pack "UNIT: ") ,T FLOOR (makeRegexOpts compCaseless execBlank "FLOOR") (BS.pack "FLOOR: ") ,T DOORS (makeRegexOpts compCaseless execBlank "\\bDOORS?[[:punct:]]?") (BS.pack "DOORS: ")]

3 3

ANNOUNCE: Important bug fix for regex-pcre ByteStrings.
by ChrisK 20 Nov '07

20 Nov '07

Greetings, There are new version 0.82 and 0.93 of regex-posix. If you use regex-posix with Data.ByteString then you should upgrade to obtain a fix for a crash error. There are new version of regex-pcre available on hackage and the two darcs repositories: http://darcs.haskell.org/packages/regex-pcre/ for "stable" version 0.82 and http://darcs.haskell.org/packages/regex-unstable/regex-pcre/ for "unstable" version 0.93 The new version regex-pcre-0.82 replaces the broken version 0.81 The new version regex-pcre-0.93 replaces the broken version 0.92 I apologize for the error. I took the address of the ByteString to give to the pcre library by using unsafeUseAsCStringLen. I had not appreciated that this can return a null pointer for an empty ByteString. My code caught this null pointer and reported it, however, and so a good error message sent in by a user allowed me to quickly find and hopefully fix it. For version 0.92 the error also applied to Lazy ByteStrings. In case anyone is curious, the fixed code checks the pointer returned by unsafeUseAsCStringLen and replaces a null pointer to a non-null pointer to a private private bytestring "myEmpty" with the length set to 0 by "trim": > {-# INLINE asCStringLen #-} > asCStringLen :: ByteString -> (CStringLen -> IO a) -> IO a > asCStringLen s op = B.unsafeUseAsCStringLen s checked > where checked cs@(ptr,_) | ptr == nullPtr = B.unsafeUseAsCStringLen myEmpty (op . trim) > | otherwise = op cs > myEmpty = B.pack [0] > trim (ptr,_) = (ptr,0) This fix is motivated by desiring to ensure asCStringLen never passes a null pointer to "op" and that no memory copy operations are used. The safe "useAsCString(Len)" do not appear capable of returning a null pointer. Only "unsafeUseAsCString(Len)" on an empty bytestring might return a null pointer. -- Chris

1 0

Re: [Haskell] Recruiting functional programmers
by Mattias Bengtsson 20 Nov '07

20 Nov '07

> Interested in recruiting Haskell programmers from Chalmers/Gothenburg > university? As an experiment, I am planning a recruitment event here in > December-see www.jobs-in-fp.org for how to take part. > Just checked my calendar and all according to Murphy's law this had to be the weekend when i'm in Stuttgart on vacation. Will there be more events if this one turns out successful? /Mattias --

1 0

Translations and Haskell
by Felipe Lessa 20 Nov '07

20 Nov '07

Hello, I'd like to start a project using Gtk2Hs and one thing is concerning me: what's the current approach on writing portable and translatable GUI programs in Haskell? I couldn't find anything on some quick searchs on haskell.org, hackage and google. If there aren't any libraries available, are there any suggestions on how to create one? Would it be too much job for someone without experience with gettext to write bindings and create and extractor like xgettext (or modify it)? Maybe TH can help? I don't know, I'm just throwing out some random ideas =). Cheers, -- Felipe.

4 3

RFC: demanding lazy instances of Data.Binary
by Nicolas Frisby 20 Nov '07

20 Nov '07

I've noticed a few posts on the cafe, including my own experience, where the spine-strictness of the Binary instance for lists caused some confusion. I'd like to suggest an approach to preventing this confusion in the future, or at least making it easier to resolve. Having decided that it is indeed appropriate for some standard instances to be strict by default [1], I think it would be beneficial to standardize an approach for expressing that a lazy instance is expected. I propose the following newtype be added to Data.Binary. A demonstration immediately follows. > newtype Lazily a = Lazily { unLazily :: a } > -- example instance > instance Binary a => Binary (Lazily [a]) where > -- lazy get and put Now > [1..] = (unLazily . decode . encode . Lazily) [1..] instead of > _|_ = (decode . encode) [1..] This email is a request for comments on this concept. I think it is a minimal way of expressing the intent that the serialisation be lazy [2]. Please share any concerns or suggestions. I'll submit a patch once the discussion is complete... or if it becomes inactive ;) Thanks for your time, Nick 1 - One solution is to make all standard Binary instances lazy wherever possible, but I presume that in most cases it's not needed and the compactness gained through default strictness (such as the [] instance) is quite significant. 2 - A more involved option is to recognize that serialisation always maps to a sequence, and so create another standard data type and class. > data Chunks a = Empty | Chunk !a (Chunks a) -- a la lazy bytestrings > instance Binary a => Binary (Chunks a) where > -- lazy put and get > class Chunky a chunk | a -> chunk where > toChunks :: a -> Chunks chunk > fromChunks :: Chunks chunk -> a All of this machinery, however, may prematurely emphasize problem-specific concerns. Thus it obfuscates the point: we just want sufficient laziness. Whatever ends up happening, the Chunks data type may be a route so common for Lazily instances that it makes sense to provide it in a library (? http://hackage.haskell.org/cgi-bin/hackage-scripts/package/strict-0.2)

3 9

HTTP actions & proxy server
by Jim Burton 20 Nov '07

20 Nov '07

How would I go about converting the little get program at http://darcs.haskell.org/http/test/get.hs to use a proxy server? I tried adding a call to setProxy like this but it doesn't work: get :: URI -> IO String get uri = do browse $ setProxy (Proxy "myproxy:80" Nothing) eresp <- simpleHTTP (request uri) resp <- handleE (err . show) eresp case rspCode resp of (2,0,0) -> return (rspBody resp) _ -> err (httpError resp) where showRspCode (a,b,c) = map intToDigit [a,b,c] httpError resp = showRspCode (rspCode resp) ++ " " ++ rspReason resp Thanks. -- View this message in context: http://www.nabble.com/HTTP-actions---proxy-server-tf4815272.html#a13775608 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 4

binary operator modifiers
by Tim Newsham 20 Nov '07

20 Nov '07

I would love to have the ability to define binary operator modifiers. For example: f \overline{op} g = liftM2 op f g f \overleftarrow{op} n = liftM2 op f (return n) n \overrightarrow{op} g = liftM2 op (return n) f \widehat{f} x = liftM f x so that for example you could define functions like: (*3) \overline{+} (/2) and 3 \overrightarrow{+} \widehat{read} getContents Obviously you could write this out the long way: liftM2 (3+) $ liftM read getContents or go through the trouble of defining a bunch of binops f <+> g = liftM2 (+) f g n +> g = return n <+> g f <+ n = f <+> return n read' = liftM read (*3) <+> (/2) 3 +> read' getContents but doing this for more than one or two operators gets tedious quickly... Is there any way in Haskell to modify binops in this way and still be able to use them infix? If not, has anyone considered supporting strange syntaxes like this? Tim Newsham http://www.thenewsh.com/~newsham/

4 5

Re: [Haskell-cafe] Properties of monads
by Radosław Grzanka 19 Nov '07

19 Nov '07

2007/11/19, Ryan Ingram <ryani.spam(a)gmail.com>: > I am pretty sure that the constructor MaybeT is exactly what you are looking > for. > > newtype MaybeT m a = MaybeT (m (Maybe a)) > > therefore > > MaybeT :: m (Maybe a) -> MaybeT m a > I swear I tried it. I swear.. Why didn't it worked than and it works now?? ;) Thank you very much for a tip. :) Thanks, Radek (who can go sleep now with clear mind). -- Codeside: http://codeside.org/ Przedszkole Miejskie nr 86 w Lodzi: http://www.pm86.pl/

1 0

Properties of monads
by Radosław Grzanka 19 Nov '07

19 Nov '07

Hello, I am writing some toys programs to learn and try to apply Monads properties (without success, I must say). Although I spent half a day on this code: http://hpaste.org/3957 I couldn't simplify (shorten) getStrip function. After reading "Doing it with class" ( http://www.haskell.org/all_about_monads/html/class.html ) I had an impression that I could "collapse" cases using some Monads properties. But maybe I misunderstood something. Can anyone look at it and give me a pointers?? (I don't mind if the code becomes unreadable a bit.) Thank you, Radek.

2 4