February 2009 - Haskell-Cafe

memory issues
by Rogan Creswick 28 Feb '09

28 Feb '09

First off, my apologies for breaking etiquette, if/when I do -- I've only just joined Haskell-cafe, and I'm quite new to Haskell. I have recently been trying to process a large data set (the 2.8tb wikipedia data dump), and also replace my scripting needs with haskell (needs that have previously been filled with bash, perl, and bits of Java). Last week I needed to do some quick scanning of the (7zipped) wikipedia dump to get a feel for the size of articles, and from that determine the best way to process the whole enchilada... cutting to the chase, I ended up with a file consisting of byte offsets and lines matched by a grep pattern (a 250mb file). Specifically, 11m lines of: 1405: <page> 14062: <page> 15979: <page> 18665: <page> 920680797: <page> ...... 2807444041476: <page> 2807444043623: <page> I needed to know how large the lagest <page> elements were, so I'd know if they would fit in memory, and some idea of how many would cause swapping, etc. So, I wrote a simple app in haskell (below) to find the sizes of each <page> and sort them. Unfortunately, it consumes an absurd amount of memory (3+gb) and dies with an out-of-memory error. Given the input size, and what it is doing, this seems ridiculously high -- can anyone help me understand what is going on, and how I can prevent this sort of rampant memory use? I can provide a link to the input file if anyone wants it, but it doesn't seem particularly useful, given the simplicity and size. Since I needed to get results fairly quickly, I've re-implemented this in java, so that reference implementation is also available should anyone want it (the approach that is most similar to the haskell requires a 1.4gb heap, but by streaming the string->long parsing, that requirement drops to ~600mb, which seems pretty reasonable, since the *output* is 215mb.) Thanks! Rogan \begin{code} -- Compiled with: -- $ ghc --make offsetSorter.hs -- -- (ghc v. 6.8.2) -- -- Run with: -- $ time ./offsetSorter data/byteOffsets.txt > haskOffsets.txt -- offsetSorter: out of memory (requested 1048576 bytes) -- -- real 4m12.130s -- user 3m4.812s -- sys 0m5.660s --(OOM happened after consuming just over 3000mb of Virt, 2.6gb Res, according to top.) -- import System (getArgs) import Data.Maybe import Monad import Text.Printf (printf) import Data.Function (on) import Data.List (sort) import Data.ByteString (ByteString) import qualified Data.ByteString.Char8 as C8 import qualified Data.ByteString as B -- get the lines -- parse each line to get the offset. -- scan the list of offsets -- | The full file size: maxSize :: Integer maxSize = 2807444044080 -- | Block is a contiguous chunk of data. -- The first entry is the offset, the second is the length. data Block = Block { offset::Integer , size::Integer } deriving (Eq) -- | Ordering of Blocks is based entirely on the block size. instance Ord Block where compare = compare `on` size instance Show Block where show (Block o s) = (show o) ++ " " ++ (show s) -- turn the file into a list of offsets: getOffsets :: ByteString -> [Integer] getOffsets = catMaybes . map parseOffset . C8.lines -- | Pull out the offsets frome a line of the file. parseOffset :: ByteString -> Maybe Integer parseOffset s = do (i, _) <- C8.readInteger (C8.filter (/=':') s) Just i -- | Get the offsets between entries in a list getSizes :: [Integer] -> [Integer] getSizes (x:y:[]) = [y - x] getSizes (x:y:ys) = (y - x):(getSizes (y:ys)) -- | creates and returns a list of Blocks, given a file's content. blocks :: ByteString -> [Block] blocks s = zipWith (Block) offsets sizes where offsets = getOffsets s sizes = getSizes (offsets ++ [maxSize]) main :: IO () main = do args <- getArgs content <- B.readFile (args!!0) printf "%s" $ unlines $ map (show) (sort $! blocks content) \end{code}

5 13

subscription problems for projects.haskell.org mailing list
by Wolfgang Jeltsch 28 Feb '09

28 Feb '09

Hello, I created a mailing list for Grapefruit on the Haskell Community Server (<grapefruit(a)projects.haskell.org>). If I try to subscribe to it, I receive a confirmation e-mail but my answers to this e-mail seem to get ignored. Does anyone have an idea what’s wrong here? Best wishes, Wolfgang

2 3

Hardware for FRP programming - what should it support?
by Noam Lewis 28 Feb '09

28 Feb '09

Greetings, I've heard about the Reduceron (graph reduction machine in FPGA), and also FRP (functional reactive programming). What sort of features/capabilities/architecture would you expect from a processor that will be designed a-priori for FRP programming? I guess it will need graph-reduction capabilities for the Functional in FRP, but what other tools do we need or can we take advantage of for the Reactive Programming? I haven't thought about this much yet, just a question that came to mind. Any thoughts? - Noam

2 1

Google Summer of Code 2009 - mentors wanted!
by Eric Kow 28 Feb '09

28 Feb '09

Hi everybody, Just a reminder that darcs will be applying to be a mentoring organisation for the Google Summer of Code project 2009. Anybody interested in mentoring a project? Darcs hackers? Haskellers in general? According to the GSoC FAQ, mentoring should take about 5 hours a week <http://code.google.com/opensource/gsoc/2009/faqs.html>. It would be a wonderful way to contribute to the darcs and Haskell communities and a fun learning experience to boot. Haskellers in general, if you've been thinking about contributing to darcs, give mentoring a try! Or if you're already working on a more general project like Grapefruit or Haskeline, you could think about mentoring as a way to turn darcs into one of your customers :-) Eric PS. Students and project ideas wanted too. Also, see you at the Hackathon! 17-19 April, Utrecht Previous discussions -------------------- * http://lists.osuosl.org/pipermail/darcs-users/2009-February/017766.html * http://lists.osuosl.org/pipermail/darcs-users/2009-February/017865.html -- Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow> PGP Key ID: 08AC04F9

1 0

Re: [Haskell-cafe] HackageDB suggestion [WAS: Re: Hidden module?]
by Cristiano Paris 28 Feb '09

28 Feb '09

On Fri, Feb 27, 2009 at 9:53 PM, Achim Schneider <barsoap(a)web.de> wrote: > ... > In general, just try the maintainer and/or author adresses given on > hsc2hs's hackage page. Ok, thanks. I suggest to add a comment section to every package's area in the HackageDB so as to let users report errors, info and the likes regarding the package. > I'd advice you to switch over to c2hs, which is actively developed, > while hsc2hs's last update date smells like abandonware. I had to use it as it's required by jhc. Thanks for the suggestion though. Cristiano

1 0

ANNOUNCE: pqueue-mtl, stateful-mtl
by Louis Wasserman 28 Feb '09

28 Feb '09

Hello all, I just released two new packages on Hackage, stateful-mtl and pqueue-mtl. Stateful-mtl provides an ST monad transformer, several useful operations on generic monad transformers, and a monad transformer intended to cleanly externally wrap operations on a mutable array (including resizing operations). It provides wrappers to generic MArray instances, an "array" based on an IntMap, and a specialized transformer that completely wraps what is essentially a pared-down STArray into a monadic interface that doesn't mention ST at all. pqueue-mtl provides implementations of several structures supporting a generic 'single-in, single-out' paradigm (encapsulated in a typeclass named Queuelike), including stacks, queues, and several implementations of priority queues, including primarily a PQueue structure (in Data.Queue.PQueue) based on a pairing heap. In addition, the package provides monad transformers encapsulating single-threaded access to a Queuelike structure, and provides a fully encapsulated array-backed heap implementation (using the array transformers from stateful-mtl). The primary motivation for all this was to improve elegance of graph algorithms. The following is an implementation of a shortest-path algorithm based on the fgl library that returns an IntMap mapping each node to its parent in a shortest-path tree: type DijkstraM gr a b = IntMapT (Node, b) (PQueueT (Edge :-> b) (State (gr a b))) expand :: (Num b, Ord b, MonadQueue (Edge :-> b) m) => b -> Context a b -> m () expand d cxt = let x = node' cxt -- node being expanded in queueInsertAll [(y, x) :-> (d + w) | (y, w) <- lsuc' cxt] dijkstraM :: (Graph gr, Num b, Ord b) => DijkstraM gr a b () dijkstraM = execMaybeT $ forever $ do -- this line repeats a monadic operation until a pattern match fails False <- gets isEmpty Just ((v, w) :-> d) <- queueExtract statefully (match v) >>=? \ c -> writeAt v (w, d) >> expand d c -- performs an action if the match does not return Nothing dijkstra :: (Graph gr, Num b, Ord b) => gr a b -> Node -> IntMap (Node, b) dijkstra g v = evalState (runQueueTOn (execIntMapT_ dijkstraM) [(v, v) :-> 0]) g As an imperative programmer for many years, this is pretty much the most intuitive implementation of Dijkstra's algorithm that I've seen. Let me know what you think. Louis Wasserman wasserman.louis(a)gmail.com

11 40

Re: Incremental array updates
by Keith Sheppard 28 Feb '09

28 Feb '09

I'm still learning haskell, so I may be missing something pretty obvious, but isn't this the kind of thing that the diff array types were created for. http://en.wikibooks.org/wiki/Haskell/Hierarchical_libraries/Arrays#DiffArra… -Keith >On Thu, Feb 26, 2009 at 06:45:27PM +0000, Ross Paterson wrote: >> Yes, bucketing problems like this are a common case that the standard >> functions cannot handle. Perhaps the libraries need a canned solution. > >Stratch that -- as Bulat points out, accumArray is such a canned solution.

2 1

Translating an imperative algorithm - negascout
by Colin Paul Adams 27 Feb '09

27 Feb '09

Hello Haskellers, I want to implement the negascout algorithm for the game I'm writing. Wikipedia gives the algorithm in imperative terms: http://en.wikipedia.org/wiki/Negascout I've tried to translate this into Haskell. I'm not sure if I'm going about it the right way, and if I am, if I've done it correctly. Any comments on my effort here, are welcome: module Move (negascout ) where {-# contract negascout Ok -> {depth | depth >= 0} -> Ok -> Ok -> Ok #-} negascout :: Node -> Int -> Int -> Int -> Int negascout node depth alpha beta = case depth == 0 || is_terminal node of True -> evaluate node False -> let child:rest = children node b = beta -- initial window is (-beta, -alpha) in negascout' child (depth-1) (- b) (- alpha) beta rest -- Implementation {-# contract negascout' Ok -> {depth | depth >= 0} -> Ok -> Ok -> Ok -> Ok -> Ok #-} negascout' :: Node -> Int -> Int -> Int -> Int -> [Node] -> Int negascout' node depth beta' alpha beta rest = let a = negate $ negascout child depth beta' alpha in case a > (- alpha) of True -> let alpha' = a in case alpha' >= beta of True -> alpha' -- beta cut-off False -> case alpha' >= (- beta') of -- null window failed high? True -> let alpha'' = negate $ negascout child depth (- beta) (- alpha') -- full re-search in case alpha'' >= beta of True -> alpha'' -- beta cut-off False -> case rest of [] -> alpha'' child':rest' -> let b' = alpha'' + 1 in negascout' child' depth (- b') alpha'' beta rest' False -> case rest of [] -> alpha' child':rest' -> let b' = alpha' + 1 in negascout' child' depth (- b') alpha' beta rest' False -> case rest of [] -> alpha child':rest' -> let b' = alpha + 1 in negascout' child' depth (- b') alpha beta rest' -- Colin Adams Preston Lancashire

5 5

Samples for http package
by Gü?nther Schmidt 27 Feb '09

27 Feb '09

Hi everyone, are there any examples on how to use the current version of the http package? Günther

4 3

How can you effectively manually determine the type?
by Anonymous Anonymous 27 Feb '09

27 Feb '09

Hello, I'm new at haskell and I have the following question: let's say I type the following: function = foldr until Now my first question is what is the type of this function? Well let's see what the type of until and foldr is: until :: (a -> Bool) -> (a -> a) -> a -> a foldr :: (a -> b -> b) -> b -> [a] -> b So I would be thinking: we fill until in the position of (a -> b -> b) so, a correspond with (a -> Bool) and b correspond with (a -> a) and b correspond with a. Hmm a small problem, I think we can divide that as follows: b1 corresponds with (a -> a) and b2 corresponds with a. So I get: foldr until :: b1 -> [a] -> b2 foldr until :: (a -> a) -> [a -> Bool] -> a Is this a correct way of thinking or am I wrong? And another question is: can someone give me an example how this can be executed? All my code that I tried to execute resulted in errors with "foldr until". Thanks!

3 2