January 2010 - Beginners

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