December 2007 - Haskell-Cafe

Software Tools in Haskell
by Gwern Branwen 06 Jan '08

06 Jan '08

On 2007.12.10 13:52:41 -0600, Tommy McGuire <mcguire(a)crsr.net> scribbled 1.7K characters: > In the "if anyone is interested,..." department.... > > For reasons that remain unclear, early this fall I started translating > Brian W. Kernighan and P.J. Plaugher's classic _Software Tools in Pascal_ > into Haskell. I have completed most of it, up to the second part of > chapter 8 which presents a proto-m4 preprocessor. I have the code online > including notes, comments, descriptions, and a few alternate approaches. > > Attractions include: > > * A fair gamut of the usual Unix suspects: proto-cat, proto-wc, proto-tr, > proto-compress, proto-ar, proto-grep, etc. > > * A usable editor, if you consider a de-featured ed-alike to be usable. > > * A simple monadic regular expression engine. > > * Zippers, Parsec, the State monad, the StateT monad transformer, and other > attempts to sully Computing Science's brightest jewels. > > * Lots and lots of really bad Haskell, including a fair bit that is a > direct translation of 30-year old Pascal (see xindex in translit, Ch. 2, if > you need to skip lunch). Programming really has advanced, you know. > > Anyway, the URL is: > http://www.crsr.net/Programming_Languages/SoftwareTools > > Questions and comments would be appreciated, especially suggestions for how > to make the code cleaner and more understandable. Flames and mockery are > welcome, too, but only if they're funny---remember, I've been staring at > Haskell, Pascal (plus my job-related Perl, CORBA, and C++) for a while; > there's no telling what my mental state is like. > > [I had intended to wait until I had the whole thing done to make this > announcement, but I recently moved and have not made much forward progress > since, other than putting what I had done online.] > > -- > Tommy M. McGuire Some of those really look like they could be simpler, like 'copy' - couldn't that simply be 'main = interact (id)'? Have you seen <http://haskell.org/haskellwiki/Simple_Unix_tools>? For example, 'charcount' could be a lot simpler - 'charcount = showln . length' would work, wouldn't it, for the core logic, and the whole thing might look like: > main = do (print . showln . length) =<< getContents Similarly wordcount could be a lot shorter, like 'wc_l = showln . length . lines' (showln is a convenience function: showln a = show a ++ "\n") I... I want to provide a one-liner for 'detab', but it looks impressively monstrous and I'm not sure I understand it. One final comment: as regards run-length encoding, there's a really neat way to do it. I wrote a little article on how to do it a while ago, so I guess I'll just paste it in here. :) --- Recently I was playing with and working on a clone of the old Gradius arcade games which was written in Haskell, Monadius <http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Monadius-0.9>. Most of my changes were not particularly interesting (cleaning up, Cabalizing, fixing warnings, switching all Integers to Ints and so on), but in its Demo.hs, I found an interesting solution to an interesting problem which seems to be a good example of how Haskell's abstractions can really shine. So, suppose we have these data items, which are levels which are specified by a pair of numbers and then a long list of numbers, often very repetitious. Perhaps a particular level might be represented this way: > level1 = ((Int,Int),[Int]) > level1 = ((2,1),[0,0,0,0,0,0,0,0,0,0,0,0,8,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,73,73,73,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,69,69,69,69,69,69,65,17,17,17,17,17,17,17,17,17,17,17,17,17,25,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,1,1,1,1,1,1,1,1,1,1,9,9,9,1,1,1,1,1,1,1,1,1,1,1,1,1,65,65,65,65,65,65,1,1,1,1,1,1,1,1,33,33,1,1,1,1,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,49,49,49,49,33,33,33,1,1,1,1,1,1,1,9,9,9,1,1,1,1,1,1,1,1,1,33,33,33,33,1,1,1,1,1,1,1,1,1,9,9,1,1,1,1,1,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,1,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,81,81,81,81,81,81,81,81,81,81,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,1,1,1,1,1,1,1,17,17,17,17,17,17,17,17,17,17,17,1,1,1,1,1,1,1,1,1,1,1,1,17,17,17,1,1,1,1,1,1,1,1,1,1,1,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,65,97,33,33,33,33,37,5,69,69,65,65,65,65,65,65,67,67,67,67,67,67,67,67,67,75,75,75,75,75,75,75,75,75,75,75,75,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,3,3,3,3,3,3,3,3,3,3,3,3,3,11,11,3,3,3,3,3,3,3,3,3,3,11,3,3,3,3,3,3,3,3,3,3,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,3,3,3,3,3,3,3,3,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,3,3,3,3,3,3,3,67,67,67,67,67,67,3,3,3,67,67,3,3,3,3,3,67,67,67,67,67,67,67,67,67,67,3,3,3,3,3,3,67,67,67,67,67,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,11,11,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,35,35,35,35,35,3,3,3,35,35,35,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,35,35,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,19,19,19,19,19,19,19,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,43,43,43,43,43,43,43,43,43,43,43,43,43,43,43,11,11,11,11,11,43,43,43,43,43,43,43,43,35,35,35,35,35,35,35,35,3,3,3,35,35,35,35,35,35,35,35,35,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,35,35,35,35,35,35,35,35,35,35,35,35,35,3,3,3,35,35,35,35,35,35,35,35,35,35,35,3,3,3,3,3,35,35,35,35,35,35,35,35,35,3,3,3,3,35,35,35,35,35,35,3,3,3,3,35,35,35,35,35,3,3,3,3,3,3,3,3,3,3,3,3,3,19,19,19,19,19,19,19,19,19,19,19,19,19,19,3,3,3,3,19,19,19,19,3,3,3,3,3,3,19,19,19,19,3,3,3,3,3,3,3,19,19,19,19,19,3,3,3,3,3,3,3,3,19,19,19,19,19,19,19,19,83,83,83,83,83,67,67,67,3,3,19,19,19,19,19,19,19,19,19,19,19,19,83,83,83,83,83,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,83,83,83,83,83,83,83,83,83,19,19,3,3,3,3,3,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,75,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,43,35,35,35,35,3,3,3,3,3,3,3,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,3,3,19,19,19,19,19,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,19,19,19,19,19,19,3,3,3,3,3,3,3,3,67,67,67,67,67,67,83,83,83,83,83,83,83,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,19,19,19,19,19,19,19,19,19,51,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,35,35,35,35,35,35,35,35,35,35,35,35,35,35,3,3,3,3,3,3,3,35,35,43,43,43,43,43,43,43,43,43,43,43,11,11,11,11,11,11,3,3,3,3,3,3,3,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,67,3,3,3,3,3,3,3,35,35,35,35,35,35,35,35,35,35,35,35,35,43,43,43,43,43,11,11,11,11,11,11,11,3,3,67,67,67,67,67,83,19,19,3,3,67,67,67,67,67,67,67,67,67,67,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]) This is clearly a bad way of representing things. We could just scrap this representation as Ints completely and perhaps define it as > -- Assume that these datatypes are already defined and everything > level1 :: ((Geometry,Geometry),[Enemies]) > level1 = ((Tall,Narrow), > > [FlyEnemy,FlyEnemy,FlyEnemy,FlyEnemy,FlyEnemy,FlyEnemy,Shooter,PowerUp,Boss..]) > -- and so on But this representation, while certainly more symbolic, is still very repetitious. We need some way of expressing this more concisely, of, in short, *compressing* it. In this vein of thought, our first observation should be that we do not need to resort to Gzipping it or adding dependencies on fancy compression libraries or anything; there is a very obvious way to compress it already - the entire thing is practically just a series of repeated numbers. We should be able to replace the length enumeration of [0,0,0,0,0,0,0,0,0,0,0,0] with something simpler, say the number of repetition and what is to be repeated so that our entry would look like (12,0). This representation is definitely shorter and more importantly, easier to modify and not a constant. It is possible that there may be a performance benefit here, as we've gotten rid of a large constant that would have to be defined in the program itself and instead replaced it with a shorter function which evaluates to the same thing. So, what is the type of our decompressing function? Well, we need to turn a (Int,Int) into a [Int]; even better, we want to turn a whole list of (Int,Int)s into a single list of [Int]. Thus, our end goal is going to be a function of this type: > rleDecode :: [(Int,Int)] -> [Int] Let us tackle the single tuple example first. The second entry defines what we need, and the first entry defines how many we need. We could write a recursive function that takes the parameter, decreases the first entry by one, and cons on one example of the second entry. It could look like this: > rleRecursiveDecode :: (Int,Int) -> [Int] > rleRecursiveDecode (0,_) = [] > rleRecursiveDecode (n,b) = b : (rleRecursiveDecode (n-1,b)) But this really is not the best way to go. It is not necessarily easy to follow, and if there is one thing I have learned about Haskell programming, it is that the most obvious approach (in this case, primitive recursion) may not be the best way to go. This is code that could have as well been written in Scheme or something. It is complicated because we are trying to ensure that we generate an item for the list only at the exact moment we need to add it into the list; we are programming as if our language is strict, in other words. So, what is the lazy way of doing things? Infinite lists, of course. We create an infinite list containing only the second entry, and we merely take as many as the first entry says we need. Simple enough! > -- Infinite list of our item of interest. > reduplicate a = a:a > rleLazyDecode :: (Int,Int) -> [Int] > rleLazyDecode (n,b) = take n (reduplicate b) Now, reduplicate is a simple enough function to define, but it already has a definition in the standard libraries - 'cycle'. (I assume you know what 'take' is, but that is also fairly easy to define once you seen the need for it.) So: > rleLazyDecode (n,b) = take n (cycle b) Might as well remove the parentheses: > rleLazyDecode (n,b) = take n $ cycle b A satisfying, short, functional, and lazy one-liner. From here the definition of rleDecode is almost trivial: we extend it to a list of tuples by throwing in a map, and we turn the resulting list of lists into a single list by way of 'concat': > rleDecode ns = concat $ map rleLazyDecode ns We can tweak this further, as 'concat . map' is a common enough idiom that there is a shortcut: > rleDecode ns = concatMap rleLazyDecode ns Aw heck - make it points-free: > rleDecode = concatMap rleLazyDecode And substitute in the rleLazyDecode definition: > rleDecode = concatMap (\(n,b) -> take n $ cycle b) We could also write a version that omits the explicit lambda and naming of parameters by use of the helpful but somewhat esoteric 'uncurry' function; Uncurry takes apart the tuple. Tts type is: > uncurry :: (a -> b -> c) -> (a, b) -> c We can actually go even further into the realms of incomprehensibility. It turns out that lists are counter-intuitively a monad! This means we can use bind and all the rest of the operations defined by the Monad typeclass to operate on lists and other things. So we can write the bizarre (but short and effective) version of rleDecode that follows: > rleDecode = (uncurry replicate =<<) And we are done! We can now represent the first list like this: > d1 = ((2,1),d) > where d = rleDecode [(5, 3), (10, 67), (6, 3), (5, 67), (29, 3), (2, 11), (29, 3), (5, 35), (3, 3), (3, 35), (24, 3), (2, 35), (19, 3), (7, 19), (21, 51), (63, 35), (15, 43), (5, 11), (8, 43), (8, 35), (3, 3), (9, 35), (20, 3), (52, 67), (32, 3), (13, 35), (3, 3), (11, 35), (5, 3), (9, 35), (4, 3), (6, 35), (4, 3), (5, 35), (13, 3), (14, 19), (4, 3), (4, 19), (6, 3), (4, 19), (7, 3), (5, 19), (8, 3), (8, 19), (5, 83), (3, 67), (2, 3), (12, 19), (5, 83), (17, 19), (9, 83), (2, 19), (5, 3), (20, 67), (1, 75), (38, 11), (1, 43), (4, 35), (7, 3), (57, 67), (2, 3), (5, 19), (17, 3), (6, 19), (8, 3), (6, 67), (7, 83), (59, 3), (9, 19), (1, 51), (17, 35), (20, 3), (14, 35), (7, 3), (2, 35), (11, 43), (6, 11), (7, 3), (26, 67), (7, 3), (13, 35), (5, 43), (7, 11), (2, 3), (5, 67), (1, 83), (2, 19), (2, 3), (10, 67), (21, 3), (147, 0)] Much nicer, don't you think? And the best part is, we should be able to reuse this run-length decoding even if we replace the arbitrary numbers by more descriptive type constructors! (Many thanks to the good denizens of #haskell, and Don Stewart's blog entry on run-length encoding/decoding using Arrows <http://cgi.cse.unsw.edu.au/~dons/blog/2007/07>.) -- gwern

11 19

An interesting monad: "Prompt"
by Ryan Ingram 04 Jan '08

04 Jan '08

(This message is a literate haskell file. Code for the "Prompt" monad is preceded by ">"; code for my examples is preceded by "]" and isn't complete, but intended for illustration.) I've been trying to implement a few rules-driven board/card games in Haskell and I always run into the ugly problem of "how do I get user input"? The usual technique is to embed the game in the IO Monad: ] type Game = IO ] -- or ] type Game = StateT GameState IO The problem with this approach is that now arbitrary IO computations are expressible as part of a game action, which makes it much harder to implement things like replay, undo, and especially testing! The goal was to be able to write code like this: ] takeTurn :: Player -> Game () ] takeTurn player = do ] piece <- action (ChoosePiece player) ] attack <- action (ChooseAttack player piece) ] bonusTurn <- executeAttack piece attack ] when bonusTurn $ takeTurn player but be able to script the code for testing, allow undo, automatically be able to save replays, etc. While thinking about this problem earlier this week, I came up with the following solution: > {-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances #-} > -- undecidable instances is only needed for the MonadTrans instance below > > module Prompt where > import Control.Monad.Trans > import Control.Monad.Identity > class Monad m => MonadPrompt p m | m -> p where > prompt :: p a -> m a "prompt" is an action that takes a prompt type and gives you a result. A simple example: ] prompt [1,3,5] :: MonadPrompt [] m => m Int This prompt would ask for someone to pick a value from the list and return it. This would be somewhat useful on its own; you could implement a "choose" function that picked randomly from a list of options and gave non-deterministic (or even exhaustive) testing, but on its own this wouldn't be much better than the list monad. What really made this click for me was that the prompt type could be built on a GADT: ] newtype GamePrompt a = GP (GameState, GameChoice a) ] data GameChoice a where ] -- pick a piece to act with ] ChoosePiece :: Player -> GameChoice GamePiece ] -- pick how they should attack ] ChooseAttack :: Player -> GamePiece -> GameChoice AttackType ] -- etc. Now you can use this type information as part of a "handler" function: ] gameIO :: GamePrompt a -> IO a ] gameIO (GP (state, ChoosePiece player)) = getPiece state player ] gameIO (GP (state, ChooseAttack player piece)) = attackMenu player piece ] -- ... The neat thing here is that the GADT specializes the type of "IO a" on the right hand side. So, "getPiece state player" has the type "IO GamePiece", not the general "IO a". So the GADT is serving as a witness of the type of response wanted by the game. Another neat things is that, you don't need to embed this in the IO monad at all; you could instead run a pure computation to do AI, or even use it for unit testing! > -- unit testing example > data ScriptElem p where SE :: p a -> a -> ScriptElem p > type Script p = [ScriptElem p] > > infix 1 --> > (-->) = SE ] gameScript :: ScriptElem GameChoice -> GameChoice a -> Maybe a ] gameScript (SE (ChoosePiece _) piece) (ChoosePiece _) = Just piece ] gameScript (SE (ChooseAttack _ _) attack) (ChooseAttack _ _) = Just attack ] gameScript _ _ = Nothing ] ] testGame :: Script GameChoice ] testGame = ] [ ChoosePiece P1 --> Knight ] , ChooseAttack P1 Knight --> Charge ] , ChoosePiece P2 --> FootSoldier ] , ... ] ] So, how to implement all of this? > data Prompt (p :: * -> *) :: (* -> *) where > PromptDone :: result -> Prompt p result > -- a is the type needed to continue the computation > Prompt :: p a -> (a -> Prompt p result) -> Prompt p result This doesn't require GADT's; it's just using existential types, but I like the aesthetics better this way. Intuitively, a (Prompt p result) either gives you an immediate result (PromptDone), or gives you a prompt which you need to reply to in order to continue the computation. This type is a MonadPrompt: > instance Functor (Prompt p) where > fmap f (PromptDone r) = PromptDone (f r) > fmap f (Prompt p cont) = Prompt p (fmap f . cont) > > instance Monad (Prompt p) where > return = PromptDone > PromptDone r >>= f = f r > Prompt p cont >>= f = Prompt p ((>>= f) . cont) > > instance MonadPrompt p (Prompt p) where > prompt p = Prompt p return > > -- Just for fun, make it work with StateT as well > -- (needs -fallow-undecidable-instances) > instance (Monad (t m), MonadTrans t, MonadPrompt p m) => MonadPrompt p (t m) where > prompt = lift . prompt The last bit to tie it together is an observation function which allows you to run the game: > runPromptM :: Monad m => (forall a. p a -> m a) -> Prompt p r -> m r > runPromptM _ (PromptDone r) = return r > runPromptM f (Prompt pa c) = f pa >>= runPromptM f . c > > runPrompt :: (forall a. p a -> a) -> Prompt p r -> r > runPrompt f p = runIdentity $ runPromptM (Identity . f) p > > runScript :: (forall a. ScriptElem p -> p a -> Maybe a) > -> Script p -> Prompt p r -> Maybe r > runScript _ [] (PromptDone r) = Just r > runScript s (x:xs) (Prompt pa c) = case s x pa of > Nothing -> Nothing > Just a -> runScript s xs (c a) > runScript _ _ _ = Nothing > -- script & computation out of sync My original goal is now achievable: ] type Game = StateT GameState (Prompt GamePrompt) ] ] action :: GameChoice a -> Game a ] action p = do ] state <- get ] prompt $ GP (state, p) ] runGameScript :: Script GameChoice -> GameState -> Game a -> Maybe (GameState, a) ] runGameScript script initialState game ] = runScript scriptFn script' (runStateT game initialState) ] where ] script' = map sEmbed script ] scriptFn s (GP (s,p)) = gameScript (sExtract s) p ] sEmbed (SE p a) = SE (GP (undefined, p)) a ] sExtract (SE (GP (_,p)) a) = SE p a Any comments are welcome! Thanks for reading this far. -- ryan

8 22

Importing Data.Char speeds up ghc around 70%
by Joost Behrends 03 Jan '08

03 Jan '08

Hi, while still working on optimizing (naively programmed) primefactors i watched a very strange behavior of ghc. The last version below takes 2.34 minutes on my system for computing 2^61+1 = 3*768614,336404,564651. Importing Data.Char without anywhere using it reduces this time to 1.34 minute - a remarkable speed up. System is WindowsXP on 2.2GHZ Intel, 512MB Ram. I give the complete code here - hopefully all tabs are (4) blanks. Can this be reproduced ? I compile just with --make -O2. module Main where import IO import System.Exit import Data.Char main = do hSetBuffering stdin LineBuffering putStrLn "Number to decompose ?" s <- getLine if s == [] then exitWith ExitSuccess else do putStrLn (show$primefactors$read s) main data DivIter = DivIter {dividend :: Integer, divisor :: Integer, bound :: Integer, result :: [Integer]} intsqrt m = floor (sqrt $ fromInteger m) primefactors :: Integer -> [Integer] primefactors n | n<2 = [] | even n = o2 ++ (primefactors o1) | otherwise = if z/=1 then result res ++[z] else result res where res = divisions (DivIter {dividend = o1, divisor = 3, bound = intsqrt(o1), result = o2}) z = dividend res -- is 1 sometimes (o1,o2) = twosect (n,[]) twosect :: (Integer,[Integer]) -> (Integer,[Integer]) twosect m |odd (fst m) = m |even (fst m) = twosect (div (fst m) 2, snd m ++ [2]) found :: DivIter -> DivIter found x = x {dividend = xidiv, bound = intsqrt(xidiv), result = result x ++ [divisor x]} where xidiv = (dividend x) `div` (divisor x) d2 :: DivIter -> DivIter d2 x |dividend x `mod` divisor x > 0 = x { divisor = divisor x + 2} |otherwise = found x d4 :: DivIter -> DivIter d4 x |dividend x `mod` divisor x > 0 = x { divisor = divisor x + 4} |otherwise = found x d6 :: DivIter -> DivIter d6 x |dividend x `mod` divisor x > 0 = x { divisor = divisor x + 6} |otherwise = found x divisions :: DivIter -> DivIter divisions y |or[divisor y == 3, divisor y == 5] = divisions (d2 y) |divisor y <= bound y = divisions (d6$d2$d6$d4$d2$d4$d2$d4 y) |otherwise = y

7 20

Basic question concerning data constructors
by Joost Behrends 03 Jan '08

03 Jan '08

Hello, perhaps i will make a wishlist of topics not dealt in the tutorials. Here is something i miss in each of them: notes at the semantics of data constructors. We read data Pair a b = Pair a b in YetAnotherHaskellTutorial. And that is all ! If we omit "data" here, this would be a silly pleonasm. And no single word about this strange behavior of "data" in every tutorial i read. A similar point: The tutorials teach, that "=" has a similar meaning than "=" in mathematics. But there is a big difference: it is not reflexive. The the right side is the definition of the left. Thus "x=y" has still some kind of temporality, which mathematics doesn't have. Wadler himself describes bunches of lazily computed equations as "dataflows" somewhere. Ok, so much on theory. Here a concrete question: For adapting hws (one of the reasons for me to be here, not many languages have a native web server) to Windows i must work on time. In System.Time i found data ClockTime = TOD Integer Integer 2 questions arise here: Does this define "TOD" (which i do not find elsewhere) together with ClockTime also ? And: Why is this not: data ClockTime Integer Integer = TOD Integer Integer ? Is it just an abbreviation for the first? Or is there a connection to ClockTime as an "abstract data type" (a notion, which would have a subtle different meaning than in OOP - since "instance" is such different thing here). Thanks for your attention, Joost

16 31

regex package for yhc?
by Thomas Hartman 03 Jan '08

03 Jan '08

Is there some way to use any of the various regex packages on hackage via yhc? Has anyone installed one them successfully? I'd like regex-tdfa, but would settle for regex-posix, or really, anything that brings the convenience of regex to yhc. In general, is there a straightforward way to install "extralibs" type packages for universal "import" availability in yhc? Is there a cabal equivalent for yhc? Documentation pointer would be appreciated; I searched but couldn't find anything. Maybe not using the right keywords... t. --- 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.

5 6

[16/16] SBM: Discussion and Conclusion
by Peter Firefly Brodersen Lund 03 Jan '08

03 Jan '08

General ------- Bytestrings are faster than haskell strings. This is good and expected. But their memory use, ouch! There seems to be a grave memory bug in 6.9. Lazy bytestrings are slower than strict bytestrings -- this was completely unexpected for me. The strictness analyzer works *very* well. It rarely made a difference to mark arguments as strict (and when it did, it was very easy to use). I/O --- The I/O patterns seen in the various programs are: 1) strict bytestrings = read increasingly large chunks (they double every time). I don't know if the already-read data have to be copied around or if the memory allocator can handle extending existing blocks (if they are at the "front" of the heap, say) like realloc() can. Even if the blocks do get copied around, that's not where the performance limiter is (speed-wise). It does seem to be a bit unwise in terms of memory pressure. Does the gc kick in every time the heap has to expand? Does it do a full collection then? If no other allocations have happened since the last collection than the allocation that caused the heap to expand, then perhaps skip the collection? (or some criteria similar to that) 2) lazy bytestrings = read blocks of 32K-8 bytes, as expected. The C benchmarks show that there's no penalty for reading 32K-8 vs. 32K. 3) native strings = read blocks 8K. The C benchmarks show that it barely matters if the block size is 4K, 32K, or 32K-8 bytes. In any case, the small differences due to block size are completely in the noise. Reading very large blocks, though, as the strict bytestrings do, actually has a cost (38-70% slower, depending on the CPU and kernel and RAM and busspeeds, etc -- see email 10 in the series). It is still peanets compared for almost all the benchmarks. Backend ------- The backend turns out to be rather bad. It is generally very easy to improve the generated code by hand without doing anything in terms of sophisticated analysis. One can rewrite inner loops using heroic code (load four characters at a time together into a 32-bit register or even use MMX to handle eight characters in parallel) but it isn't really necessary to do that to gain a good improvement and start being competitive with C. The backend is probably what is costly on some of the lazy bytestring and native string code because there are too many tests to see if the buffer has been exhausted (I think). Some simple hoisting and common subexpression elimination would go far here. For the simpler strict bytestring benchmarks, heroic backend optimizations are not necessary because they give less of an improvement over merely competent register use than sensible I/O and buffer management (cache effects start to be important once the compiler generates sensible code). I would have liked to examine backend performance further by playing with the generated C-- code but unfortunately, the C-- that ghc emits won't compile. Dissecting the generated machine code for the more complicated benchmarks was so hard that I skipped it -- I can't even recognize the labels! It's one thing if the backend generates lots of extra labels but another if the expected labels simply are not there! (this is why tools/cut.pl complains that it can't find the main loop for some of the programs -- if the */*.discut file is unexpectedly short, then that's the reason.) Quality of measurements ----------------------- The speed measurements are of extremely high quality, much more than it turns out is needed at this moment. I probably spent a bit too much effort there. The memory measurements are unusual. I don't recall having seen anything like them elsewhere because one seldom has to work with uncooperative programs when benchmarking (the preloading trick works with any program, as long as it is dynamically linked on Linux and uses the standard loader). They are probably the biggest single contribution from this work, together with the visualization provided by the bar charts. Thoroughness ------------ It really is necessary to benchmark more than one ghc/library combination, otherwise the bad memory bugs wouldn't stand out so clearly or I would have believed, as Don Stewart did, that he had fixed the memory allocation bug. It also matters what microarchitectures one use, as pointed out by email 10 in this series. And you gotta have many benchmarks, otherwise you might not really be measuring what you think you measure. I could probably have gotten away with fewer benchmarks in this case but that would have left a nagging feeling at the back of my head that there was a benchmark I /could/ have included that would have showed up a spectacular performance bug. Using so big input files (150MB) made the programs run slow enough that the timer granularity (1ms) was small compared to their runtime. It also made the memory performance problems really stand out (and be unignorable). I think that was a good idea. Having automatic feedback on the timing measurement quality helped a lot during the development of the testing harness because it made it easier and faster for me to eliminate the causes of imprecision. That's why I wrote the eatmem tool and that's why the test harness does a dd of the input file and the compiled program before running the tests. It should probably also dd the C library (and the few other libraries linked in: math, GNU multiprecision, and TLS stuff) but the quality estimators show that any improvement would be very small. Using top together with huge input files convinced me that -sstderr was untrustworthy so I developed the pause-at-end preloading hack. Paranoia paid off big time there. Visual presentation ------------------- The bar charts (with UTF-8) turned out to be so much more readably than raw numbers. This is a trick I learned from the Cairo team, which created a performance suite very early on. The bar is drawn with '%' if the measurement is bad. That turned out to be a much clearer visual indicator than my previous '*' and '!' flag characters. Really, there's no good reason not to use UTF-8 these days. I also discovered that the program names used for the benchmarks really matter. I had started out with names like 'cntspaces12' and 'cntbytes34' and kept getting confused about what program measured what. If the names are good, you don't need to put a description of each benchmark on the report. The order the benchmarks are presented in also matters. It is important that they are grouped and it is also important that the order is as stable as possible, even when not all runs contain exactly the same benchmarks. Separation of the time and memory bar charts + the separation of byte and space counting benchmarks also turned out to be useful. I had neither at first. And finally, merging of reports. I had no idea it would be so useful before I wrote the scripts for it. This is what makes the memory bugs in 6.9 really stand out and this is what shows the improvements of bytestring 0.9.0.2 (in particular with ghc 6.8.2). It also shows how wildly the performance of four different microarchitectures can differ. Scripting --------- Scripting everything is key to the success of an effort like this. I am VERY happy that scripted not just the running of the benchmarks but also the report handling and even the installation of the ghc/bytestring combinations. (I also scripted the sending of these 17 emails -- let's see if the script works :) ) The predictions elicited by my teaser email ------------------------------------------- As expected, predicting the performance of haskell programs is really hard, even modulo performance bugs. And, no, strings are not "silly". Action Items ------------ Suggested short-term actions: o Can the allocator expand blocks? If not, see if it can be implemented. o Find out why lazy bytestrings "by hand" are that slow - is it due to lack of hoisting in the backend? o Improve backend, mainly by not hiding information from register allocator. Alternatively, by using an assembly-to-assembly transformator that improves the register allocation. o Fix -sstderr. o perhaps even let the RTS print out /proc/self/maps or /proc/self/status or "peak RSS" returned by getrusage() in the ru_maxrss field? o Find memory leaks in ghc 6.9 code. o ghc should allow round-tripping of the C-- code it generates. o would be awfully nice if the backend didn't sometimes throw the recognizable labels away. o can the core/stg code be made easier to read? -Peter

3 3

Newbie question: can laziness lead to space compression?
by Brian Hurt 02 Jan '08

02 Jan '08

My apologies if this has been beat to death before, I'm still new to Haskell. But I was wondering if it is possible that lazy evaluation could lead to space compression, especially under heavily persistant usage patterns? Here's the argument I'm making. Say we have a tree-based Set with, say, 1024 values in it. For ease of math we'll assume that it's perfectly balanced. Say each node in the tree takes 5 words of memory. So in an eager language (for example, Ocaml), adding a new node to this tree requires the allocation of 10 new nodes, or 50 words of memory. In Haskell, what would happen (as I understand it) is that just a new lazy thunk would be allocated- say, 10 words of memory. Conceptually, we could think of the returned value as the original tree plus a small delta. The lazy implementation is using 40 fewer words of memory than the eager implementation. Note that the benefit isn't *big*- we're talking about 40 words of memory when the main data structure is taking up 5K plus words of memory- so it's less than 1% different. But there is a (small) upside in memory usage at least occassionally, right? Brian

3 2

[RFC] benchmarks of bytestrings, teaser
by Peter Lund 02 Jan '08

02 Jan '08

What do you think the relative speeds are of the six small haskell programs at the end of this email? All they do is read from stdin and count the number of spaces they see. There are two that use strict bytestrings, two that use lazy bytestrings, and two that use the standard Haskell strings. Three use a recursive function with an accumulator parameter and three use a foldl with a lambda function. Say the fastest one takes the time 1. How much time will the others take? And how about memory? How much memory do you think they require? Let's say we feed a 150MB(*) file into each of them, how many megabytes do you think they end up using (as seen from the OS, not in terms of how big the live heap is)? I'm going to post full benchmarks + analysis on Wednesday. -Peter *) hardddisk megabytes. The file is 150000034 bytes ≈ 143 mebibytes. PS: For extra credit, what do you think is the peak memory use for this program when given an input file of 150MB? {-# LANGUAGE BangPatterns #-} import qualified Data.ByteString.Lazy.Char8 as B import GHC.Int (Int64) -- note that D.BS.Lazy.Char8.length is ByteString -> Int64 -- D.BS.C8.length is ByteString -> Int cnt :: B.ByteString -> Int64 cnt bs = B.length (B.filter (== ' ') bs) main = do s <- B.getContents print (cnt s) ============================== hs/space-bs-c8-acc-1.hs: {-# LANGUAGE BangPatterns #-} import qualified Data.ByteString.Char8 as B cnt :: Int -> B.ByteString -> Int cnt !acc bs = if B.null bs then acc else cnt (if B.head bs == ' ' then acc+1 else acc) (B.tail bs) main = do s <- B.getContents print (cnt 0 s) ============================== hs/space-bslc8-acc-1.hs: {-# LANGUAGE BangPatterns #-} import qualified Data.ByteString.Lazy.Char8 as B cnt :: Int -> B.ByteString -> Int cnt !acc bs = if B.null bs then acc else cnt (if B.head bs == ' ' then acc+1 else acc) (B.tail bs) main = do s <- B.getContents print (cnt 0 s) ============================== hs/space-xxxxx-acc-1.hs: {-# LANGUAGE BangPatterns #-} cnt :: Int -> String -> Int cnt !acc bs = if null bs then acc else cnt (if head bs == ' ' then acc+1 else acc) (tail bs) main = do s <- getContents print (cnt 0 s) ============================== hs/space-bs-c8-foldlx-1.hs: {-# LANGUAGE BangPatterns #-} import qualified Data.ByteString.Char8 as B cnt :: B.ByteString -> Int cnt bs = B.foldl' (\sum c -> if c == ' ' then sum+1 else sum) 0 bs main = do s <- B.getContents print (cnt s) ============================== hs/space-bslc8-foldlx-1.hs: {-# LANGUAGE BangPatterns #-} import qualified Data.ByteString.Lazy.Char8 as B cnt :: B.ByteString -> Int cnt bs = B.foldl' (\sum c -> if c == ' ' then sum+1 else sum) 0 bs main = do s <- B.getContents print (cnt s) ============================== hs/space-xxxxx-foldl.hs: {-# LANGUAGE BangPatterns #-} cnt :: String -> Int cnt bs = foldl (\sum c -> if c == ' ' then sum+1 else sum) 0 bs main = do s <- getContents print (cnt s) ==============================

15 33

Knowledge
by jlw501 02 Jan '08

02 Jan '08

I'm new to functional programming and Haskell and I love its expressive ability! I've been trying to formalize the following function for time. Given people and a piece of information, can all people know the same thing? Anyway, this is just a bit of fun... but can anyone help me reduce it or talk about strictness and junk as I'd like to make a blog on it? contains :: Eq a => [a]->a->Bool contains [] e = False contains (x:xs) e = if x==e then True else contains xs e perfectcomm :: Bool perfectcomm = undefined knowself :: Bool knowself = undefined allKnow :: Eq a => [a]->String->Bool allKnow _ "" = True allKnow [] k = False allKnow (x:[]) k = knowself allKnow (x:xs) k = comm x xs k && allKnow xs k where comm p [] k = False comm p ps k = if contains ps p then knowself else perfectcomm -- View this message in context: http://www.nabble.com/Knowledge-tp14423007p14423007.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 6

Missing join and split
by Mitar 01 Jan '08

01 Jan '08

Hi! I am really missing the (general) split function built in standard Haskell. I do not understand why there is something so specific as words and lines but not a simple split? The same goes for join. Yes, I can of course define them but ... in an interactive mode it would be quite handy to have them there. Or am I wrong and are those hidden somewhere? So what are common ways to get around this? What are elegant definitions? Inline definitions? Mitar

13 19