November 2007 - Haskell-Cafe

map/reduce example
by Bulat Ziganshin 06 Jan '08

06 Jan '08

Hello Haskell-Cafe, i've written small program which demonstrates how map/reduce may be implemented in Haskell. it counts amount of words in file, splitting it into 64kb blocks processed by two threads. their results are combined by another two threads. how it may be made better? in particular, is it strict in values send over channels? {-# LANGUAGE BangPatterns #-} import Control.Concurrent import Control.Concurrent.Chan import Control.Monad import Data.IORef import Data.ByteString.Char8 as B hiding (length) import System.Environment import System.IO main = do (file:_) <- getArgs h <- openBinaryFile file ReadMode map <- newChan reduce <- newChan result <- newChan replicateM_ 2 (forkIO$ mapThread map reduce) replicateM_ 2 (forkIO$ reduceThread reduce result) jobs <- new 0 untilM (hIsEOF h) $ do str <- B.hGet h 65536 writeChan map str jobs += 1 jobs' <- val jobs writeChan reduce (0,-jobs') res <- readChan result print res mapThread map reduce = forever $ do str <- readChan map let !sum = length (B.words str) writeChan reduce (sum,1) reduceThread reduce result = forever $ do (sum1,n1) <- readChan reduce (sum2,n2) <- readChan reduce let (!sum,!n) = (sum1+sum2,n1+n2) case n of 0 -> writeChan result sum _ -> writeChan reduce (sum,n) untilM cond action = do deny <- cond unless deny $ do action untilM cond action forever action = action >> forever action infixl 0 =:, += new = newIORef val = readIORef a=:b = writeIORef a b a+=b = modifyIORef a (\a->a+b) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

3 2

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

Problems with split-objs
by Magnus Therning 14 Dec '07

14 Dec '07

I've followed the instructions at [1] to create a .deb of vty[2]. It seems the helper scripts for Debian passes `--enable-split-obj' when running `./Setup.lhs configure'. This results in numerous multiple definitions of stuff. I have a few questions regarding this... I think I understand what --split-objs does, but why doesn't it work for vty? I've debianised other haskell libs using the same method without problems. The only difference I can see is that vty uses FFI. Is that what causes the problems? How do I fix this? I'd rather not go in and manually change any automatically generated files, and the file that passes `--enable-split-objs' is automatically generated :( /M [1]: http://haskell.org/haskellwiki/Creating_Debian_packages_from_Cabal_package [2]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/vty-3.0.0 -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus．therning＠gmail．com http://therning.org/magnus What if I don't want to obey the laws? Do they throw me in jail with the other bad monads? -- Daveman

2 2

Waiting for thread to finish
by Maurício 11 Dec '07

11 Dec '07

Hi, After I have spawned a thread with 'forkIO', how can I check if that thread work has finished already? Or wait for it? Thanks, Maurício

21 39

What is the role of $!?
by PR Stanley 10 Dec '07

10 Dec '07

Hi What is the role of $! ? As far as I can gather it's something to do with strict application. Could someone explain what it is meant by the term strict application please? Thanks, Paul

20 26

ARM back end?
by Greg Fitzgerald 09 Dec '07

09 Dec '07

Anybody know of an ARM back end for any of the Haskell compilers? Thanks, Greg

8 7

Over-allocation
by Gracjan Polak 08 Dec '07

08 Dec '07

Hi, My program is eating too much memory: copyfile source.txt dest.txt +RTS -sstderr Reading file... Reducing structure... Writting file... Done in 20.277s 1,499,778,352 bytes allocated in the heap 2,299,036,932 bytes copied during GC (scavenged) 1,522,112,856 bytes copied during GC (not scavenged) 17,846,272 bytes maximum residency (198 sample(s)) 2860 collections in generation 0 ( 10.37s) 198 collections in generation 1 ( 8.35s) 50 Mb total memory in use INIT time 0.00s ( 0.00s elapsed) MUT time 1.26s ( 1.54s elapsed) GC time 18.72s ( 18.74s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 19.98s ( 20.28s elapsed) %GC time 93.7% (92.4% elapsed) Alloc rate 1,186,898,778 bytes per MUT second Productivity 6.3% of total user, 6.2% of total elapsed The source.txt is 800kb, and I expect files of size 100 times more, say 80MB, so using -H800M will not help here much. The profile -p says: Wed Nov 21 14:23 2007 Time and Allocation Profiling Report (Final) copyfile +RTS -p -RTS source.txt dest.txt total time = 4.48 secs (224 ticks @ 20 ms) total alloc = 1,500,359,340 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc xparse PdfModel 78.1 95.0 followed by a lot of 0.0 numbers. Then the faulty xparse: xparse uniq borders body bin = do parseOperatorEq "xref" p <- P.many (parseXRefSection uniq) parseOperatorEq "trailer" e <- parseDict let entries = IntMap.fromList (map (\(a,b,c) -> (a,c)) (concat p)) return (Body e entries) where the P is Text.ParserCombinators.ReadP made to work with [Word8]. How do I know WHAT is making so much allocation in this function? My files are xml-like in structure. The task currently is to read, parse, write the file. I can provide more details for interested souls. How do I make my program make less allocations? -- Gracjan

5 12

New slogan for haskell.org
by Don Stewart 05 Dec '07

05 Dec '07

It was raised at CUFP today that while Python has: Python is a dynamic object-oriented programming language that can be used for many kinds of software development. It offers strong support for integration with other languages and tools, comes with extensive standard libraries, and can be learned in a few days. Many Python programmers report substantial productivity gains and feel the language encourages the development of higher quality, more maintainable code. With the links from the start about using Python for various purposes, along with reassuring text about licenses and so on. Note its all about how it can help you. The Haskell website has the rather strange motivational text: Haskell is a general purpose, purely functional programming language featuring static typing, higher order functions, polymorphism, type classes, and monadic effects. Haskell compilers are freely available for almost any computer. Which doesn't say why these help you. Any suggestions on a 2 or 3 sentence spiel about what's available? Here's some quick points: General purpose: applications from OS kernels to compilers to web dev to ... Strong integration with other languages: FFI, and FFI binding tools Many developer tools: debugger, profiler, code coverage, QuickCheck Extensive libraries: central library repository, central repo hosting Productivity, robustness, maintainability: purity, type system, etc Parallelism! -- Don

54 160

Parsing unstructured data
by Olivier Boudry 05 Dec '07

05 Dec '07

Hi all, This e-mail may be a bit off topic. My question is more about methods and algorithms than Haskell. I'm looking for links to methods or tools for parsing unstructured data. I'm currently working on data cleaning of a Customer Addresses database. Addresses are stored as 3 lines of text without any structure and people made used lots of imagination to create the data (20 years of data using no rules at all). Postal code, street, city, state, region, country and other details as suite, building, dock, doors, PO box, etc... are all stored in free form in those 3 lines. I already wrote a haskell program to do the job. It correctly parses about 2/3 addresses and parses much of the rest but with unrecognized parts left. The current program works by trying to recognize words used to tag parts like STE, SUITE, BLDG, street words (STR, AVE, CIRCLE, etc...) and countries from a list (including typos). It uses regular expressions to recognize variation of those words, lookup tables for countries, street words, regular expression rules for postal codes, etc... The most difficult task is splitting the address parts. There is no clearly defined separator for the fields. It can be dot, space, comma, dash, slash, or anything you can imagine using as a separator and this separator can of course also be found inside an address part. In the current application when part of an address is recognized it will not be parsed again by the other rules. A system trying all rules and tagging them with probabilities would probably give better results. Any link to tools or methods that could help me in that task would be greatly appreciated. I already searched for fuzzy, probabilistic or statistical parsing but without much success. Thanks, Olivier. PS: just in case someone's interested I attached the code and partial data to this e-mail.

4 6

Haskell interface file (.hi) format?
by Rob Hoelz 04 Dec '07

04 Dec '07

Hello fellow Haskellers, Does anyone know if/where I can find a specification for the .hi files generated by GHC? I ask because I want to write an omni-completion plugin for Vim to make Haskell hacking a bit nicer. Thanks, Rob Hoelz

10 12