- Beginners - Haskell.org

Unexpected Space Leak (despite using external-sort)
by Peter Green 04 Jan '10

04 Jan '10

I am using the external-sort package to sort my output in the program below. I made this choice because my output dataset [[Int]] can be large (e.g. >3M items, each [Int]). What my program does: (1) Reads in a file containing 'compressed lists' which look like so: 8+12,11,7+13,10 1+2+3,1+9,3+6,4 . . One compressed list per line. These compressed lists are parsed to become [[[Int]]] [[[8,12],[11],[7,13],[10]], [[1,2,3],[1,9],[3,6],[4]], . . ] Generally files of compressed lists have lengths of ~10,000 lines. (2) Compressed lists are exploded to [[int]] via concatMap Cartesian Product over [[[Int]]], so we end up with [[Int]] [[8, 11, 7, 10], [8, 11, 13, 10], [12, 11, 7, 10], [12, 11, 13, 10], [1, 1, 3, 4], . . [3, 9, 6, 4]] These 'exploded lists are' *much* longer than the input lists. It's common for them to have >100K [Int] members, or even >1M [Int] members. (3) This [[Int]] data must be sorted in to lexicographic order and output as CSV data: i.e. output should be: 1,1,3,4 3,9,6,4 8,11,7,10 . . 12,11,13,10 There is no way to avoid the necessity of sorting the final product. I can *not* take advantage of any structure in the input data to avoid this sort stage. e.g. sorting the (smaller) input compressed lists *will not* obviate the need to lex sort the (larger) final output. The program listing below works correctly, but *is not* space- efficient. In fact it is *less* space-efficient than the equivalent program using Prelude sort! e.g. with one data set which explodes to ~3.7M I am seeing 639MB of total memory use. I am sure externalSort is not at fault because: (a) I'm the Newbie. (b) ExternalSort.bin is 'only' 228MB in size. (Expected to be not small because sorting a [[Int]] with 3.7M [Int] members.) I'm sure it must be something I'm doing wrong elsewhere which is causing the entire output data list to be read into memory. What I really want to happen is: (1) Data lazily read in from stdin and lazily parsed (2) Data lazily sucked out to disk and strictly sorted by externalSort (but no big deal since this happening on disk) (3) Data lazily sucked back out of externalSort, lazily formatted for output, and lazily written to stdout. So memory usage should hopefully never go over (say 10MB). But in fact I'm using 638MB. So somewhere in the code below I must be doing something very wrong. I hope someone can tell me what I am doing wrong here. TIA! import Algorithms.ExternalSort import Data.List.Split (splitOn) import System.IO -- Cartesian Product over a List of Lists -- Http://www.cs.nott.ac.uk/~gmh/sudoku.lhs -- cp [[1,2],[3],[4,5,6]] --> [[1,3,4],[1,3,5],[1,3,6],[2,3,4],[2,3,5], [2,3,6]] cp :: [[a]] -> [[a]] cp [] = [[]] cp (xs:xss) = [y:ys | y <- xs, ys <- cp xss] -- fromCSV ["8+12,11,7+13,10", "1+2+3,1+9,3+6,4"] --> -- [[[8,12],[11],[7,13],[10]],[[1,2,3],[1,9],[3,6],[4]]] fromCSV :: [String] -> [[[Int]]] fromCSV = map parseOneLine where parseOneLine = map parseGroup . splitOn "," where parseGroup = map read . splitOn "+" -- explode [[[1,2],[3],[4,5,6]], [[1, 2], [14,15], [16]]] --> [[1,3,4], [1,3,5], -- [1,3,6],[2,3,4],[2,3,5],[2,3,6],[1,14,16],[1,15,16],[2,14,16], [2,15,16]] explode :: [[[a]]] -> [[a]] explode = concatMap cp -- toSingles "8+12,11,7+13,10\n1+2+3,1+9,3+6,4" --> -- [[8,11,7,10],[8,11,13,10],[12,11,7,10],[12,11,13,10],[1,1,3,4], [1,1,6,4], -- [1,9,3,4],[1,9,6,4],[2,1,3,4],[2,1,6,4],[2,9,3,4],[2,9,6,4], [3,1,3,4], -- [3,1,6,4],[3,9,3,4],[3,9,6,4]] toSingles :: String -> [[Int]] toSingles = explode . fromCSV . lines -- toCSV [8,11,7,10,12] --> "8,11,7,10,12" toCSV :: (Show a) => [a] -> String toCSV = tail . init . show main = do getContents >>= externalSort . toSingles >>= mapM_ (putStrLn . toCSV)

3 4

in which monad am I?
by Francesco Guerrieri 03 Jan '10

03 Jan '10

Hello, this is my first post to the list. I am learning Haskell and I think I understand monads (well, that doesn't mean that I actually understand them :-) ) Nevertheless, I would like to check something with you. My question is: how do you know in which monad you are computing at a given time? What I mean is that, when dealing with more than a monad at the same time (Maybe, List, IO come to my mind) if I understand correctly you have to lift values back and forth from a monad to the other. How do you "keep" track of the monad you are in a given time? I think that the type system will help to resolve to the relevant function (eg, thinking to liftM signature, liftM :: (Monad m) => (a1 -> r) -> m a1 -> m r But doesn't ever happen that poor liftM be confused? and do poor haskell programmers never feel the need to explicitly state to which monad they "wish to lift" ? I hope it's not a too silly question. If so, please point me to the relevant resouces (Are monad transformers relevant to my issue?) Thanks in advance, Francesco

4 8

writing many1Till combinator for Parsec
by Vlad Skvortsov 02 Jan '10

02 Jan '10

Hi, I'm writing a parser where I find myself in need to use manyTill combinator with an additional constraint that there should be at least one meaningful element before the trailer (say, a word ended with a period: 'abc.'). Here is what I have: many1Till :: Parser a -> Parser end -> Parser [a] many1Till p end = do p1 <- p ps <- manyTill p end return (p1:ps) The problem here is that I want to catch and report a case when 'p1' could be actually parsed by 'end' ('..' is not a word ended by a period). Generally 'p' and 'end' can parse the same subset of strings. Another version a had was: many1Till :: Parser a -> Parser end -> Parser [a] many1Till p end = do try (end >> (unexpected "sequence terminator")) <|> (do { p1 <- p; ps <- manyTill p end; return (p1:ps) }) Here there are two disadvantages: 1) I don't like hardcoding "sequence terminator" here; 2) the error output should say that only 'p' parser is expected, while it says (technically correct) that either 'p' or 'end' is expected: Prelude Main Text.ParserCombinators.Parsec> parseTest (many1Till letter (char '.')) "1" parse error at (line 1, column 1): unexpected "1" expecting "." or letter (What I want here is to say "expecting letter") Any suggestions? Thanks! -- Vlad Skvortsov, vss(a)73rus.com, http://vss.73rus.com

2 4

Problem installing graphalyze with Cabal
by John Velman 01 Jan '10

01 Jan '10

I have Haskell Platform downloaded and installed today. When I tried to install graphalyze with cabal install, it had problems with pandoc. To make a long story fairly short, I downloaded pandoc-1.3 from hackage, and tried building it "by hand". It says it had missing dependencies of utf8-string >= 0.3, and zip-archive >=0.1.1. Tried installing them with cabal, and this worked OK. Still, pandoc setup says: jrv:pandoc-1.3 jr$ runhaskell Setup configure Configuring pandoc-1.3... Setup: At least the following dependencies are missing: utf8-string >=0.3, zip-archive >=0.1.1 jrv:pandoc-1.3 jr$ cabal install zip-archive-0.1.1.1 I _finally_ checked ghc-pkg list, and I have, among other things: /Users/jr/.ghc/i386-darwin-6.10.4/package.conf: {HOC-1.0}, {HOC-Foundation-1.0}, binary-0.5.0.1, binary-0.5.0.2, bktrees-0.2.2, darcs-2.3.0, digest-0.0.0.8, graphviz-2999.6.0.0, hashed-storage-0.3.7, haskeline-0.6.1.6, mmap-0.4.1, pandoc-1.3, polyparse-1.4, terminfo-0.3.0.2, utf8-string-0.3.5, utf8-string-0.3.6, zip-archive-0.1.1.1, zip-archive-0.1.1.4, zlib-0.5.2.0 As you see, I've ended up with two copies each (because of my messing around before I checked ghc-pkg, I guess). Well, all of them are >= the dependency requirements, If I understand correctly. What gives? How do I get rid of the extra copies? (By the way, the HOC entries are left over from an earlier time, and I'd like to get rid of those also). Thanks, John Velman

2 2

Interpreting profiling results
by Patrick LeBoutillier 01 Jan '10

01 Jan '10

Hi, Firstly, Happy New Year! Secondly, I've written (and improved using other solutions I've found on the net) a simple sudoku solver which I'm trying to profile. Here is the code: import Array import List (transpose, nub, (\\)) import Data.List data Sudoku = Sudoku { unit :: Int, cells :: Array (Int, Int) Int, holes :: [(Int, Int)] } cell :: Sudoku -> (Int, Int) -> Int cell s i = (cells s) ! i instance Read Sudoku where readsPrec _ s = [(Sudoku unit cells holes, "")] where unit = length . words . head . lines $ s cells = listArray ((1, 1), (unit, unit)) (map read . words $ s) holes = [ c | c <- indices cells, (cells ! c) == 0] instance Show Sudoku where show s = unlines [unwords [show $ cell s (x,y) | x <- [1 .. unit s]] | y <- [1 .. unit s]] genNums :: Sudoku -> (Int, Int) -> [Int] genNums s c@(i,j) = ([1 .. u] \\) . nub $ used where used = (row s u i j) ++ (col s u i j) ++ (square s sq u i j) u = unit s sq = truncate . sqrt . fromIntegral $ u row s u i j = [cell s (i, y) | y <- [1 .. u]] col s u i j = [cell s (x, j) | x <- [1 .. u]] square s sq u i j = [cell s (x, y) | y <- [1 .. u], x <- [1 .. u], f x i, f y j] where f a b = div (a-1) sq == div (b-1) sq solve :: Sudoku -> [Sudoku] solve s = case holes s of [] -> [s] (h:hs) -> do n <- genNums s h let s' = Sudoku (unit s) ((cells s) // [(h, n)]) hs solve s' main = print . head . solve . read =<< getContents When I compile as such: $ ghc -O2 --make Sudoku.hs -prof -auto-all -caf-all -fforce-recomp and run it on the following puzzle: 0 2 3 4 3 4 1 0 2 1 4 0 0 3 2 1 I get the following profiling report: Fri Jan 1 10:34 2010 Time and Allocation Profiling Report (Final) Sudoku +RTS -p -RTS total time = 0.00 secs (0 ticks @ 20 ms) total alloc = 165,728 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc CAF GHC.Handle 0.0 10.7 CAF Text.Read.Lex 0.0 2.1 CAF GHC.Read 0.0 1.2 square Main 0.0 2.8 solve Main 0.0 1.3 show_aVx Main 0.0 3.7 readsPrec_aYF Main 0.0 60.6 main Main 0.0 9.6 genNums Main 0.0 5.0 cell Main 0.0 1.2 individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 1 0 0.0 0.3 0.0 100.0 main Main 186 1 0.0 9.6 0.0 85.6 show_aVx Main 196 2 0.0 3.7 0.0 3.7 cell Main 197 16 0.0 0.0 0.0 0.0 solve Main 188 5 0.0 1.3 0.0 11.8 genNums Main 189 8 0.0 5.0 0.0 10.4 square Main 194 88 0.0 2.8 0.0 3.2 cell Main 195 16 0.0 0.4 0.0 0.4 col Main 192 4 0.0 0.7 0.0 1.1 cell Main 193 16 0.0 0.4 0.0 0.4 row Main 190 4 0.0 0.7 0.0 1.1 cell Main 191 16 0.0 0.4 0.0 0.4 readsPrec_aYF Main 187 3 0.0 60.6 0.0 60.6 CAF GHC.Read 151 1 0.0 1.2 0.0 1.2 CAF Text.Read.Lex 144 8 0.0 2.1 0.0 2.1 CAF GHC.Handle 128 4 0.0 10.7 0.0 10.7 CAF GHC.Conc 127 1 0.0 0.0 0.0 0.0 Does the column 'entries' represent the number of times the function was called? If so, I don't understand how the 'square' function could be called 88 times when it's caller is only called 8 times. Same thing with 'genNums' (called 8 times, and solve called 5 times) What am I missing here? Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

1 0

Global variable question
by Joe Van Dyk 31 Dec '09

31 Dec '09

What's the appropriate way to write this in Haskell? # Ruby code, ignore the thread-unsafety for now. class Ticker @@tick = 0 def self.update! @@tick += 1 end def self.current return @@tick end end Ticker.update! # 1 Ticker.update! # 2 Ticker.current # 2 -- Joe Van Dyk http://fixieconsulting.com

4 5

Is there a (^) function for exponents other than integral?
by Ken Overton 31 Dec '09

31 Dec '09

Sorry if this is from a faq list somewhere, I've been looking through the more common locations/libs and have been unable to find a way to raise numbers to a fractional exponent. Can someone help me to find such a function in haskell? Thanks, -- kov

3 2

Data.Map, types and debug
by legajid 31 Dec '09

31 Dec '09

Hi, studying IO with files, i got this tutorial program. By the way, i discover the Data.Map module. Several questions then come to my mind : q1: why, in mapM_, make (sort (keys grades)) ? keys is already sorted, isn't it? q2: why, in mapM_, have grades twice (in draw then keys). I wonder if writing only draw grades, one could then extract the s and g parts in the draw function (via keys and elems). From this, i have problems with the type of grades; which is it? The insert function, using insertWith should give Map k a, but foldr seems to change this (couldn't match expected type [Map k a] against inferred type Map [String] a1 on the mapM_ line . q3: To solve the types problem, I tried to debug : i can get the types for s, marks and avg but for g, it says not in scope. How can i get this information ? q4: I also tried to type the parameter in draw (draw (x::Map k a) = ...) but i got an error : Illegal signature in pattern use -XScopedTypeVariables to permit it Since this parameter is visibly not set by default in ghci, is it a good idea to set it ? Thanks and happy new year. Didier import Data.Char <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#t:Char> import Data.Maybe <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#t:Maybe> import Data.List import Data.Map hiding (map <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:map>) import Text.Printf main = do src <- readFile <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:readF…> "grades" let pairs = map <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:map> (split.words <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:words>) (lines <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:lines> src) let grades = foldr <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:foldr> insert empty pairs mapM_ <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:mapM_> (draw grades) (sort (keys grades)) where insert (s, g) = insertWith (++ <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:.>) s [g] split [name,mark] = (name, read <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:read> mark) draw g s = printf "%s\t%s\tAverage: %f\n" s (show <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:show> marks) avg where marks = findWithDefault (error <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:error> "No such student") s g avg = sum <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:sum> marks / fromIntegral <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:fromI…> (length <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:length> marks) :: Double <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#t:Double>

2 1

Re: [Haskell-beginners] Interrupting a thread
by Floptical Logic 31 Dec '09

31 Dec '09

On Thu, Dec 31, 2009 at 1:21 AM, Dean Herington <heringtonlacey(a)mindspring.com> wrote: > At 6:08 PM -0600 12/30/09, Floptical Logic wrote: >> >> On Sun, Dec 27, 2009 at 1:47 PM, Stephen Blackheath [to >> Haskell-Beginners] <mutilating.cauliflowers.stephen(a)blacksapphire.com> >> wrote: >>> >>> MVars are the lowest-level operation for this kind of thing in Haskell, >>> and they're very fast. Anything can be done with MVars but in some cases >>> you need extra worker threads (cheap in Haskell), and you may even need >>> to kill threads (which is a safe operation in Haskell). CHP is higher >>> level and designed for this sort of complexity, so you might want to >>> look at that. I'll give you the answer I know, which is a low-level >>> MVar answer. >>> >>> I have *not* tried compiling this code. >>> >>> >>> import Control.Concurrent >>> import Control.Concurrent.MVar >>> import Data.Int >>> import System.Time >>> >>> type Microseconds = Int64 >>> >>> getSystemTime :: IO Microseconds >>> getSystemTime = do >>> (TOD sec pico) <- getClockTime >>> return $! >>> (fromIntegral sec::Int64) * 1000000 + >>> (fromIntegral pico::Int64) `div` 1000000 >>> >>> type Stack a = [a] -- or whatever type you want >>> >>> isEmpty :: Stack a -> Bool >>> isEmpty [] = True >>> isEmpty _ = False >>> >>> pop :: Stack a -> (a, Stack a) >>> >>> data ScheduleInput = ModifyStack (Stack -> Stack) | WaitFor Microseconds >>> | Timeout >>> >>> never = maxBound :: Microseconds >>> >>> schedule :: MVar ScheduleInput -> MVar a -> Stack a -> IO () >>> schedule inpVar wnVar stack = schedule_ never stack >>> where >>> schedule_ :: Microseconds -> Stack -> IO () >>> schedule_ timeout stack = do >>> now <- getSystemTime >>> let tillTimeout = 0 `max` (timeout - now) >>> if tillTimeout == 0 && not (isEmpty stack) then do >>> let (val, stack') = pop stack >>> putMVar wnVar (PopValue val) >>> schedule never stack' >>> else do >>> inp <- takeMVarWithTimeout (fromIntegral tillTimeout) inpVar >>> case inp of >>> ModifyStack f -> schedule_ timeout (f stack) >>> WaitFor t -> do >>> now <- getSystemTime >>> schedule (t+now) stack >>> Timeout -> schedule timeout stack >>> >>> readMVarWithTimeout :: Int -> MVar ScheduleInput -> IO ScheduleInput >>> readMVar timeoutUS inpVar = do >>> tid <- forkIO $ do >>> threadDelay timeoutUS >>> putMVar inpVar Timeout >>> inp <- takeMVar inpVar >>> killThread tid >>> return inp >>> >>> waitNotify :: MVar ScheduleInput -> MVar Int -> IO () >>> waitNotify schInp wnInp = do >>> val <- takeMVar wnInp >>> ...notify... >>> let t = .... >>> putMVar schInp $ WaitFor t -- block input for the specified period >>> >>> main = do >>> schVar <- newEmptyMVar >>> wnVar <- newEmptyMVar >>> forkIO $ schedule schVar wnVar [] >>> forkIO $ waitNotify wnVar schVar >>> ... >>> -- Modify stack according to user input inside your main IO loop >>> putMVar schVar $ ModifyStack $ \stack -> ... >>> >>> >>> I'm sure this is not exactly what you want, but at least it illustrates >>> how you can achieve anything you like by using MVars + extra worker >>> threads + killing threads (useful for implementing timeouts). >>> >>> >>> Steve >>> >>> Floptical Logic wrote: >>>> >>>> Hi, >>>> >>>> I am new to concurrency in Haskell and I am having trouble >>>> implementing the notion of interrupting a thread. >>>> >>>> In a new thread, call it waitNotify, I am trying to do the following: >>>> pop a number from a stack, wait some number of seconds based on the >>>> number popped from the stack, perform some notification, and repeat >>>> until there are no more numbers in the stack at which point we wait >>>> for a new number. >>>> >>>> These numbers will be supplied interactively by the user from main. >>>> When the user supplies a new number, I want to interrupt whatever >>>> waiting is happening in waitNotify, insert the number in the proper >> >> >> position in the current stack, and resume waitNotify using the updated >>>> >>>> stack. Note, here "stack" is just a generalization; it will likely >>>> just be a list. >>>> >>>> What is the most idiomatic way to capture this sort of behavior in >>>> Haskell? My two challenges are the notion of interrupting a thread, >>>> and sharing and updating this stack between threads (main and >>>> waitNotify). >>>> >>>> Thank you >>>> _______________________________________________ >>>> Beginners mailing list >>>> Beginners(a)haskell.org >>>> http://www.haskell.org/mailman/listinfo/beginners >>>> >>> _______________________________________________ >>> Beginners mailing list >>> Beginners(a)haskell.org >>> http://www.haskell.org/mailman/listinfo/beginners >>> >> >> Thanks Stephen. That worked and things are starting to make more >> sense. The crux of it all was the readMVarWithTimeout function which >> does exactly what I want. >> >> Now I want to extend this a bit further to use StateT. I've modified >> the schedule function quite a bit, and now it has type schedule :: >> StateT MyState IO. I keep the MVar actVar in MyState as well the list >> (stack) of wait times. However, the type of forkIO is forkIO :: IO () >> -> IO ThreadId. How do I fork a new thread for schedule even though >> it is wrapped in the State monad? >> >> Thanks again. > > You'll want something like this: > > myFork :: StateT MyState IO () -> MyState -> StateT MyState IO ThreadId > myFork action initialState = liftIO (forkIO (evalStateT action > initialState)) > > Dean > That's not quite what I'm looking for. I don't want to create a new thread in which to run the monad but rather to be able to create threads from inside the monad (as a result of running the monad).

2 1

Interrupting a thread
by Floptical Logic 31 Dec '09

31 Dec '09

Hi, I am new to concurrency in Haskell and I am having trouble implementing the notion of interrupting a thread. In a new thread, call it waitNotify, I am trying to do the following: pop a number from a stack, wait some number of seconds based on the number popped from the stack, perform some notification, and repeat until there are no more numbers in the stack at which point we wait for a new number. These numbers will be supplied interactively by the user from main. When the user supplies a new number, I want to interrupt whatever waiting is happening in waitNotify, insert the number in the proper position in the current stack, and resume waitNotify using the updated stack. Note, here "stack" is just a generalization; it will likely just be a list. What is the most idiomatic way to capture this sort of behavior in Haskell? My two challenges are the notion of interrupting a thread, and sharing and updating this stack between threads (main and waitNotify). Thank you

4 4