July 2007 - Haskell-Cafe

ANN: Network.HTTP.Simple 0.1 in hackage
by brad clawsie 11 Jul '07

11 Jul '07

i have mentioned my small Network.HTTP.Simple wrapper library here before i have made api changes and i have released it to hackage these changes are described here http://www.b7j0c.org/content/haskell-http.html this page oddly gets many non-bot hits a day, so i presume there is sufficient interest to merit major changes here on the list i have made every attempt to correctly attribute work i borrowed from the Network.HTTP authors, to whom i am grateful

1 0

Re: [Haskell-cafe] function unique
by Gregory Propf 10 Jul '07

10 Jul '07

There was a typo in my last email. The input list is [1,4,5,3,3,4] not [1,4,5,3]. - Greg ----- Original Message ---- From: Alexteslin <alexteslin(a)yahoo.co.uk> To: haskell-cafe(a)haskell.org Sent: Tuesday, July 10, 2007 1:40:56 PM Subject: [Haskell-cafe] function unique Hi, i am a beginner to Haskell and i have a beginner's question to ask. An exercise asks to define function unique :: [Int] -> [Int], which outputs a list with only elements that are unique to the input list (that appears no more than once). I defined a function with list comprehension which works but trying to implement with pattern matching and primitive recursion with lists and doesn't work. unique :: [Int] -> [Int] unique xs = [x | x <- xs, elemNum2 x xs == 1] elemNum2 :: Int -> [Int] -> Int elemNum2 el xs = length [x| x <- xs, x == el] //This doesn't work, I know because the list shrinks and produces wrong result but can not get a right //thinking unique2 :: [Int] -> [Int] unique2 [] = [] unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 xs Any help to a right direction would be very appreciated, thanks. -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11528933 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ____________________________________________________________________________________ It's here! Your new message! Get new email alerts with the free Yahoo! Toolbar. http://tools.search.yahoo.com/toolbar/features/mail/

1 0

Allocating enormous amounts of memory and wondering why
by Jefferson Heard 10 Jul '07

10 Jul '07

I'm using the Data.AltBinary package to read in a list of 4.8 million floats and 1.6 million ints. Doing so caused the memory footprint to blow up to more than 2gb, which on my laptop simply causes the program to crash. I can do it on my workstation, but I'd really rather not, because I want my program to be fairly portable. The file that I wrote out in packing the data structure was only 28MB, so I assume I'm just using the wrong data structure, or I'm using full laziness somewhere I shouldn't be. I've tried compiling with profiling enabled, but I wasn't able to, because the Streams package doesn't seem to have an option for compiling with profiling. I'm also a newbie to Cabal, so I'm probably just missing something. The fundamental question, though is "Is there something wrong with how I wrote the following function?" binaryLoadDocumentCoordinates :: String -> IO (Ptr CFloat, [Int]) binaryLoadDocumentCoordinates path = do pointsH <- openBinaryFile (path ++ "/Clusters.bin") ReadMode coordinates <- get pointsH :: IO [Float] galaxies <- get pointsH :: IO [Int] coordinatesArr <- mallocArray (length coordinates) pokeArray coordinatesArr (map (fromRational . toRational) coordinates) return (coordinatesArr, galaxies) I suppose in a pinch I could write a C function that serializes the data, but I'd really rather not. What I'm trying to do is load a bunch of coordinates into a vertex array for OpenGL. I did this for a small 30,000 item vertex array, but I need to be able to handle several million vertices in the end. If I serialize an unboxed array instead of a list or if I do repeated "put_" and "get" calls, will that help with the memory problem?

4 6

GHC threads and SMP
by Paul L 10 Jul '07

10 Jul '07

I have two parallel algorithms that use the lightweight GHC thread and forkIO. I compile them using the -threaded (or -smp) option, and run both with +RTS -N2 -RTS command line option. QSort is able to make use of the dual cores on my laptop -- "top" shows that two threads show up and both CPUs are utilized, and "time" it will give something like this: real 0m0.502s user 0m0.872s sys 0m0.004s But Prime can only make use of one core, as shown by "top". "time" gives real 0m9.112s user 0m9.093s sys 0m0.028s Because forkOS is not used anywhere, the decision of running them on 1 or 2 OS threads seem rather arbitary. Why? Regards, Paul L > import Control.Concurrent > import System.Random > import Data.Array.MArray > import Data.Array.IO > import System.IO.Unsafe > import Control.Exception 1. Quick Sort > testQSort' n verbose = do > let b = (0, n - 1) > arr <- newArray b 0 :: IO (IOUArray Int Int) > initM' (mkStdGen 0) b arr > waitForChildren > qsortM' b arr > waitForChildren > if verbose then getElems arr >>= putStrLn . show else return () Initialize an array with random numbers. > initM' g (i, j) arr | j - i < 10000 = fillArr g i j > where > fillArr g i j = if i > j then return () else do > let (v, g') = next g > writeArray arr i v >> fillArr g' (i + 1) j > initM' g (i, j) arr = do > let k = (i + j) `div` 2 > (g1, g2) = split g > forkChild $ initM' g1 (i, k) arr > forkChild $ initM' g2 (k + 1, j) arr > return () > qsortM' (i, j) arr = qsort' (i, j) > where > qsort' (i, j) = > if j <= i then return () else do > k <- split i j > if j - i > 10000 then (forkChild $ qsort' (i, k - 1)) >> return () > else qsort' (i, k - 1) > qsort' (k + 1, j) > split left right = do > v <- readArray arr right > let split' i j = if j == right then swap i right v >> return i else do > b <- readArray arr j > if b <= v > then (swap i j b) >> split' (i + 1) (j + 1) > else split' i (j + 1) > split' left left > swap i j b = do > a <- readArray arr i > writeArray arr i b > writeArray arr j a 2. Prime > testPrime' n verbose = do > arr <- newArray (0, n) True :: IO (IOUArray Int Bool) > primeM' arr n > waitForChildren > if verbose > then getElems arr >>= putStrLn . show . map fst . filter snd . zip [0..] > else return () > primeM' arr n = do > let p = truncate $ sqrt (fromIntegral n) + 1 > remove i = if i > p then return () else do > spawnRemover (i + 1) > remove' (i + i) > where > remove' j = if j > n then return () else do > writeArray arr j False > remove' (j + i) > spawnRemover j = if j > n then return () else do > t <- readArray arr j > if t then forkChild (remove j) else spawnRemover (j + 1) > remove 2 Manage thread termination > children :: MVar [MVar ()] > children = unsafePerformIO (newMVar []) > waitForChildren :: IO () > waitForChildren = do > cs <- takeMVar children > case cs of > [] -> putMVar children cs > m:ms -> do > putMVar children ms > takeMVar m > waitForChildren > > forkChild :: IO () -> IO () > forkChild io = do > mvar <- newEmptyMVar > childs <- takeMVar children > putMVar children (mvar:childs) > forkIO (io `finally` putMVar mvar ()) > return ()

3 4

Re: [Haskell-cafe] The Garbage Collector Ate My Homework
by Thomas Conway 10 Jul '07

10 Jul '07

Hmm, looks like the garbage collector got hungry again: 1093,741,664,672 bytes allocated in the heap 1006,759,632,160 bytes copied during GC (scavenged) 72,181,353,728 bytes copied during GC (not scavenged) 400,940,412 bytes maximum residency (8853 sample(s)) 76353 collections in generation 0 (3724.54s) 8853 collections in generation 1 (19689.00s) 1065 Mb total memory in use INIT time 0.00s ( 0.00s elapsed) MUT time 2619.54s (3103.46s elapsed) GC time 23413.54s (23569.24s elapsed) RP time 0.00s ( 0.00s elapsed) PROF time 2167.91s (2204.09s elapsed) EXIT time 0.00s ( 0.08s elapsed) Total time 28201.00s (28876.80s elapsed) %GC time 83.0% (81.6% elapsed) Alloc rate 417,531,666 bytes per MUT second Productivity 9.3% of total user, 9.1% of total elapsed And that was with -H700M. What a shame the heap profiler (-hb) aborts on my program. :-( Still, -hc and -hd seem to work, the only hassle is the hours of running time required to get things to go bad. cheers, T. -- Dr Thomas Conway drtomc(a)gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

1 0

Sequence Classes
by Jonathan Cast 10 Jul '07

10 Jul '07

I was just meditating on array fusion using streams, and list fusion using streams, and it struck me: the definition of the list functions over arrays is the same as that of the list functions over lists. From the ByteString paper, we get: map f = transformerBi (mapS f) foldr f z = consumerDn (foldrS f z) foldl f z = consumerUp (foldlS f z) replicate n = producerBi (replicateS n) etc. So why not say class Sequence t alpha where consumerUp, consumerDn, consumerBi :: (Stream alpha -> beta) -> t alpha -> beta producerUp, producerDn, producerBi :: Stream alpha -> t alpha transformerUp, transformerDn, transformerBi :: Sequence t beta => (Stream alpha -> Stream beta) -> t alpha -> t beta map :: Sequence t alpha => (alpha -> beta) -> t alpha -> t beta map f = transformerBi (mapS f) etc.? Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs

2 1

Re: [Haskell-cafe] Very freaky
by Dan Piponi 10 Jul '07

10 Jul '07

On 7/10/07, Dan Piponi <dpiponi(a)gmail.com> wrote: > On 7/10/07, Andrew Coppin <andrewcoppin(a)btinternet.com> wrote: > > But what does, say, "Maybe x -> x" say? Silly me. You reversed the arrows and I copied you. (Could it be something to do with the other conversation we were having?) I meant to say: So x -> Maybe x says that X implies "True or X". That's a valid proposition and so there is a function x -> Maybe x. -- Dan

1 0

Re: [Haskell-cafe] In-place modification
by Andrew Coppin 10 Jul '07

10 Jul '07

Bulat Ziganshin wrote: > Hello Andrew, > > Monday, July 9, 2007, 12:36:25 AM, you wrote: > >> OK. So that's just the GHC binary itself, right? >> > > it's INSTALLER > Ah. That explains the size then... Is it safe to install two versions of GHC at once? :-.

3 6

ANNOUNCE: HCL v1.0 -High-level library for building command line interfaces
by Justin Bailey 10 Jul '07

10 Jul '07

I'm please to announce HCL 1.0 - a library for building command line interfaces. The library exports a mix of low and high-level functions for building programs which gather simple values, ask yes/no questions, or present hierarchical menus. The library is not intended to do complex, full-screen UIs ala ncurses - it is intended for line-oriented interfaces. Included with the library is a hangman game, so if nothing else you can enjoy that. Where do I get it? ============= Download from Hackage at: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HCL-1.0 How do I use it it? ============= It's Cabal-ized so, after downloading and unpacking: runghc Setup.hs configure runghc Setup.hs build runghc Setup.hs install Note I had some inconsistent results building with HEAD cabal, but the version distributed with GHC works great (1.1.6.2). To play hangman, execute 'hangman'. Once installed, you can look at it in GHCi by loading the "HCL" module. Tell me more! ========== This library lets you do a lot of cool things. For example, here's a simple guess a number game: guess_num_fun = do target <- reqIO $ getStdRandom (randomR (1::Integer,100)) let guessed val = case compare target val of GT -> do { reqIO $ putStrLn "Too low!"; return False } LT -> do { reqIO $ putStrLn "Too high!"; return False } EQ -> do { reqIO $ putStrLn "You win!"; return True } reqUntil guessed (prompt "Enter a number between 1 and 100: " reqInteger) "reqUntil" takes a predicate and asks for a response until the predicate is true. In the case above, the user is asked to enter an integer. Once they guess the number, the program ends. The library makes it easy to gather structured values. For example, imagine this data structure: data Taxpayer = Taxpayer { name :: String, age :: Int, ssn :: String } deriving (Read, Show) One way to use HCL to get Taxpayer values from the user is to take advantage of its Read instance: reqTaxpayer :: Request Taxpayer reqTaxpayer = prompt "Please enter tax payer information: " (reqRead reqResp) But that is ugly because the user has to type a "Read"-able string: > getTaxpayer reqTaxpayer Please enter tax payer information: Taxpayer {name="John", age = 30, ssn = "" } However, we can build a form of sorts and make life much easier for the user: reqTaxpayerEasy :: Request Taxpayer reqTaxpayerEasy = do name <- prompt "Please enter the tax payer's name: " reqResp age <- prompt "Please enter their age: " reqInt ssn <- prompt "What is their SSN/ASN: " reqResp return (Taxpayer name age ssn) Which looks like this: > getTaxpayer reqTaxpayerEasy Please enter the tax payer's name: Bob Please enter their age: 50 Please enter their SSN/ASN: 111-11-1111 The library also makes simple hierarchical menus easy to build. The below defines the menu structure for a hypothetical PIM: reqMenu $ reqSubMenu topMenu "Manage contacts" manageContactsMenu $ reqSubMenu topMenu "Manage calendar" (reqMenuItem "Add an event" ... $ ... reqMenuExit "Return to previous menu" reqMenuEnd) $ -- End the menu definition reqMenuEnd -- Defines a partial menu manageContactsMenu = reqMenuItem "Add a contact" ... $ ... reqMenuExit "Return to previous menu" reqMenuEnd These and more examples are distributed with the library in the examples directory. Anything else? =========== Feedback, praise and criticism are welcome. Feedback regarding 'idiomatic' usage is especially desired. This is a first for me so any responses are appreciated. The library was developed on Windows using GHC - please let me know of any odd *nix and Hugs bugs. This library was inspired in part by the Ruby HighLine library (http://highline.rubyforge.org/) Many thanks Mark Jones for his input on HCL's design and implementation.

4 5

Need for speed: the Burrows-Wheeler Transform
by Andrew Coppin 10 Jul '07

10 Jul '07

OK, so I *started* writing a request for help, but... well I answered my own question! See the bottom... I was reading Wikipedia, and I found this: http://en.wikipedia.org/wiki/Burrows-Wheeler_transform I decided to sit down and see what that looks like in Haskell. I came up with this: module BWT where import Data.List rotate1 :: [x] -> [x] rotate1 [] = [] rotate1 xs = last xs : init xs rotate :: [x] -> [[x]] rotate xs = take (length xs) (iterate rotate1 xs) bwt :: (Ord x) => [x] -> [x] bwt = map last . sort . rotate step :: (Ord x) => [x] -> [[x]] -> [[x]] step xs = zipWith (:) xs . sort inv_bwt :: (Ord x) => x -> [x] -> [x] inv_bwt mark xs = head . filter (\xs -> head xs == mark) . head . drop ((length xs) - 1) . iterate (step xs) . map (\x -> [x]) $ xs My my, isn't that SO much shorter? I love Haskell! :-D Unfortunately, the resident C++ expert fails to grasp the concept of "example code", and insists on comparing the efficiency of this program to the C one on the website. Fact is, he's translated the presented C into C++, and it can apparently transform a 145 KB file in 8 seconds using only 3 MB of RAM. The code above, however, took about 11 seconds to transform 4 KB of text, and that required about 60 MB of RAM. (I tried larger, but the OS killed the process for comsuming too much RAM.) Well anyway, the code was written for simplicity, not efficiency. I've tried to explain this, but apparently that is beyond his comprehension. So anyway, it looks like we have a race on. >:-D The first thing I did was the optimisation mentioned on Wikipedia: you don't *need* to build a list of lists. You can just throw pointers around. So I arrived at this: module BWT2 (bwt) where import Data.List rotate :: Int -> [x] -> Int -> [x] rotate l xs n = (drop (l-n) xs) ++ (take (l-n) xs) bwt xs = let l = length xs ys = rotate l xs in map (last . rotate l xs) $ sortBy (\n m -> compare (ys n) (ys m)) [0..(l-1)] This is indeed *much* faster. With this, I can transform 52 KB of text in 9 minutes + 60 MB RAM. The previous version seemed to have quadratic memory usage, whereas this one seems to be linear. 52 KB would have taken many months with the first version! Still, 9 minutes (for a file 3 times smaller) is nowhere near 8 seconds. So we must try harder... For my next trick, ByteStrings! (Never used them before BTW... this is my first try!) module BWT3 (bwt) where import Data.List import qualified Data.ByteString as Raw rotate :: Int -> Raw.ByteString -> Int -> Raw.ByteString rotate l xs n = (Raw.drop (l-n) xs) `Raw.append` (Raw.take (l-n) xs) bwt xs = let l = Raw.length xs ys = rotate l xs in Raw.pack $ map (Raw.last . rotate l xs) $ sortBy (\n m -> compare (ys n) (ys m)) [0..(l-1)] Now I can transform 52 KB in 54 seconds + 30 MB RAM. Still nowhere near C++, but a big improvement none the less. Woah... What the hell? I just switched to Data.ByteString.Lazy and WHAM! Vast speed increases... Jeepers, I can transform 52 KB so fast I can't even get to Task Manager fast enough to *check* the RAM usage! Blimey... OK, just tried the 145 KB test file that Mr C++ used. That took 2 seconds + 43 MB RAM. Ouch.

12 21