- Haskell-Cafe - Haskell.org

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

Haskell and GnuPG?
by Magnus Therning 10 Jul '07

10 Jul '07

Continuing my "life up-side-down"¹ I'm looking for a Haskell wrapper around GPGME. Is there such a beast? /M ¹) That's the life where I turn to Haskell before turning to Python. -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus(a)therning.org Jabber: magnus.therning(a)gmail.com http://therning.org/magnus

2 1

Data.ByteString.dropWhile
by Thomas Conway 10 Jul '07

10 Jul '07

Hi All, I notice that Data.ByteString has span and spanEnd. Is there a known particular reason why dropWhile and takeWhile don't have corresponding *End functions? If not, what is the protocol for adding them? 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.

4 7

where's yi available?
by Vadim 10 Jul '07

10 Jul '07

I'm trying to get 'hide' but failed to install 'yi'. I followed instructions at page http://haskell.org/hawiki/hIDE_2fDesign but can't succeed in executing darcs get http://scannedinavian.org/repos/yi/ the mentioned http isn't responding. Can you please advise where can I get yi? TIA. Vadim.

2 1

Too many packages on hackage? :-)
by dons＠cse.unsw.edu.au 10 Jul '07

10 Jul '07

Hackage hackers, Looks like there's too many packages on hackage.haskell.org now for a single page listing: http://hackage.haskell.org/packages/archive/pkg-list.html Perhaps we can have a page with just the categories, with subpages hanging off? -- Don

11 14

Evaluation of IO actions in record assignment
by Adde 09 Jul '07

09 Jul '07

Hi. I'm toying around with GTK2Hs and one of the things I'm doing is stuffing a bunch of widgets in a record. The problem is that the function that fetches a widget from the Glade file returns IO Widget while my structure contains Widget's. The best I've come up with is simply evaluating the actions by putting the result in temporaries and then building the record. Is there an easier way to accomplish this? signatureEntry <- xmlGetWidget xml castToEntry "signatureEntry" passwordEntry <- xmlGetWidget xml castToEntry "passwordEntry" repeatEntry <- xmlGetWidget xml castToEntry "repeatEntry" return UserPanel {userPanelSignatureEntry = signatureEntry, userPanelPasswordEntry = passwordEntry, userPanelRepeatEntry = repeatEntry} Thanks, Adde

3 3

Testing parsing failures with Parsec
by Sean Smith 09 Jul '07

09 Jul '07

All - I tried emailing this to Daan, but I can't find an up-to-date email address, so I hope this is an acceptable alternative :). I'm looking for someone who knows the guts of Parsec a bit, or has done some automated testing of a Parsec parser. I'm interested in using Parsec for a number of projects, so I'm giving it a try. So far, it has really served me well. However, I've run into an issue with testing for proper parsing failures. As an example, I've been parsing a simplified version of scheme's s-expressions. When parsing "(1 2n3)", I expect a parse error "unexpected \"n\"". Therefore, I've made a test case which attempts to inspect the resulting ParseError to make sure it's correct. However, I'm confused by this list of Messages: [SysUnExpect "\"n\"",SysUnExpect "\"n\"",Expect "space",Expect "\")\""] Why is SysUnExpect "\"n\"" in the list twice? I can't figure that out from looking over the source for Parsec. It seems like the following rules should hold, but I can't be sure: 1) There should only be one occurrence of SysUnExpect *or* UnExpect in the list 2) UnExpect is only used for an unexpected reserved word or operator, and SysUnExpect is used for parse errors 3) There can be any number of Expect in the list, which indicate what was expected to occur in the stream If the above rules are correct, I was thinking it might make more sense to use a type with more structure than a list to hold those data. Also, the fact that neither Message nor ParseError derives Eq makes it difficult to test values of those types. Why not derive Eq? Finally, do you have any suggestions as to how I might better test for correct parse errors from Parsec? Thanks very much for your help! - Sean Smith P.S. I'm more than willing to dig into the Parsec source and provide patches for any changes I might make, if someone will accept them!

1 0

Haskell's prefix exprs
by Christian Maeder 09 Jul '07

09 Jul '07

Hi, I would like haskell to accept the following (currently illegal) expressions as syntactically valid prefix applications: f = id \ _ -> [] g = id let x = [] in x h = id case [] of [] -> [] i = id do [] j = id if True then [] else [] The rational is that expressions starting with a keyword should extend as far as possible (to the right and over several lines within their layout). In this case the above right hand sides (rhs) are unique juxtapositions of two expressions. (This extension should of course apply to more than two expressions, i. e. "f a do []") Furthermore the above rhs are all valid if written as infix expressions: f = id $ \ _ -> [] g = id $ let x = [] in x h = id $ case [] of [] -> [] i = id $ do [] j = id $ if True then [] else [] (In fact, maybe for haskell-prime "$" could be changed to a keyword.) Does this pose any problems that I haven't considered? I think only more (and shorter) illegal haskell programs will become legal. Cheers Christian Maybe someone else can work out the details for Haskell's grammar (I've posted this message to glasgow-haskell-users before, but it applies to every Haskell implementation and should be discussed here.)

3 2

Elementary question about Type Constraints
by lassoken 09 Jul '07

09 Jul '07

Hi, I'm trying to translate Example 2.3.3 (simple symbolic differentation) from Structure and Interpretation of Computer Programs into Haskell. Here is code that works (as far as see): --- data Term b = Var String | Const b | Sum (Term b) (Term b) | Prod (Term b) (Term b) newSum (Const a) (Const b) = Const (a+b) newSum (Const 0) t@_ = t newSum t@_ (Const 0) = t newSum a b = Sum a b newProd (Const a) (Const b) = Const (a*b) newProd (Const 1) t@_ = t newProd t@_ (Const 1) = t newProd (Const 0) t@_ = Const 0 newProd t@_ (Const 0) = Const 0 newProd a b = Prod a b deriv (Var x) (Const c) = Const 0 deriv (Var x) (Var y) | x == y = Const 1 | otherwise = Const 0 deriv x@(Var _) (Sum u v) = newSum (deriv x u) (deriv x v) deriv x@(Var _) (Prod u v) = newSum (newProd u (deriv x v)) (newProd (deriv x u) v) --instance Show (Term b) where show = showTerm showTerm (Var x) = x showTerm (Const c) = show c showTerm (Sum a b) = "(" ++ showTerm a ++ "+" ++ showTerm b ++ ")" showTerm (Prod a b) = "(" ++ showTerm a ++ showTerm b ++ ")" --- Where should I put type constraint (Show b) to be able to define Term b as an instance of Show class? Actually, I would like to say that Term b is an instance of Show iff b is and not to put constraint on b.

4 3

More binary IO, compression, bytestrings and FFI fun
by dons＠cse.unsw.edu.au 09 Jul '07

09 Jul '07

Processing larger amounts of data, compression, serialisation and calling C. An elaboration of the previous example: * Build a largish structure in Haskell * Compress it in memory * Serialise it to disk * Deserialise it * Decompress * Pass it to C * Display the result Pretty common pattern for low level stuff. We use zlib + lazy bytestrings for streaming decompression, and Data.Binary for the serialisation. We will use * Foreign.* to generate the data * Wrap it as a lazy bytestring * Data.Binary to serialise it * Code.Compression.Gzip to compress/uncompress * Pass it to C and make a simple FFI call on the result * Display the result Running: $ ghc -O2 A.hs --make $ time ./A Built table Compressed 25600000 bytes Compressed size 2231545 bytes (91.28%) Decompressed 25600000 bytes Calling into C ... -8.742278e-8 -0.6865875 -0.7207948 -0.1401903 0.63918984 0.7437966 0.27236375 -0.5763547 -0.75708854 -0.39026973 ./A 2.98s user 0.11s system 94% cpu 3.275 total The code: {-# OPTIONS -fglasgow-exts #-} -- -- Some imports -- import Foreign import Foreign.C.Types import Data.Int import qualified Data.ByteString.Lazy as L import qualified Data.ByteString.Base as S import qualified Data.ByteString as S import Data.Binary import Codec.Compression.GZip import System.IO import Text.Printf import Control.Monad ------------------------------------------------------------------------ -- Foreign Ptrs -- -- A simple wrapper type -- data Table = Table { floats :: ForeignPtr CFloat , ints :: ForeignPtr Int } -- Statically fixed sizes floatSize = 4800000 intSize = 1600000 totalBytes = sizeOf (undefined :: CFloat) * floatSize + sizeOf (undefined :: Int) * intSize -- -- Build a table populated with some defaults -- Float table filled with 'pi' , ints numbered consecutively -- newTable :: IO Table newTable = do fp <- S.mallocByteString (floatSize * sizeOf (undefined :: CFloat)) ip <- S.mallocByteString (intSize * sizeOf (undefined :: Int )) withForeignPtr fp $ \p -> forM_ [0..floatSize-1] $ \n -> pokeElemOff p n pi withForeignPtr ip $ \p -> forM_ [0..intSize-1] $ \n -> pokeElemOff p n n return (Table fp ip) ------------------------------------------------------------------------ -- Lazy ByteStrings -- -- Convert ForeignPtr a to and from a lazy ByteString -- toByteString :: Storable a => ForeignPtr a -> Int -> L.ByteString toByteString (fp :: ForeignPtr a) n = L.fromChunks . (:[]) $ S.fromForeignPtr (castForeignPtr fp) (n * sizeOf (undefined :: a)) -- -- Flatten a lazy bytestring back to a ForeignPtr. -- fromByteString :: Storable a => L.ByteString -> ForeignPtr a fromByteString lbs = castForeignPtr fp where (fp,_,n) = S.toForeignPtr . S.concat $ L.toChunks lbs ------------------------------------------------------------------------ -- GZip and Data.Binary -- -- Serialise a Table, compressing with gzip it as we go: -- instance Binary Table where put (Table f i) = do put . compress . toByteString f $ floatSize put . compress . toByteString i $ intSize get = do fs <- liftM decompress get is <- liftM decompress get -- check we read the correct amount: if L.length fs + L.length is == fromIntegral totalBytes then return $ Table (fromByteString fs) (fromByteString is) else error "Partial read" ------------------------------------------------------------------------ -- FFI -- -- Example call to process the data using C functions. -- rounded :: Int -> ForeignPtr CFloat -> IO [CFloat] rounded l fp = withForeignPtr fp $ \p -> go p where go p = forM [0..l-1] $ \n -> do v <- peekElemOff p n return $ c_tanhf (c_sinf (v + fromIntegral n)) -- A random C function to use: foreign import ccall unsafe "math.h sinf" c_sinf :: CFloat -> CFloat foreign import ccall unsafe "math.h tanhf" c_tanhf :: CFloat -> CFloat ------------------------------------------------------------------------ -- -- Now glue it all together -- main = do table <- newTable putStrLn "Built table" -- write the data to disk, compressed with gzip as we go. encodeFile "/tmp/table.gz" table printf "Compressed %d bytes\n" totalBytes -- how good was the compression? h <- openFile "/tmp/table.gz" ReadMode n <- hFileSize h hClose h printf "Compressed size %d bytes (%0.2f%%)\n" n (100 - (fromIntegral n/fromIntegral totalBytes*100) :: Double) -- load it back in, decompressing on the fly table' <- decodeFile "/tmp/table.gz" printf "Decompressed %d bytes\n" totalBytes -- now process the floats with C printf "Calling into C ...\n" ps <- rounded 10 (floats table') forM_ ps print

2 3