July 2006 - Haskell-Cafe

Packages and modules
by Brian Hulley 10 Jul '06

10 Jul '06

Hi - At the moment there is a problem in that two packages P and Q could contain the same hierarchical module eg Data.Foo, and the only way for user code to ensure the "right" Data.Foo is used is to ensure that packages P and Q are searched in the right order. However suppose P and Q also contain another module with the same name, eg Data.Bar. And suppose a user module wants to use Data.Foo from P but Data.Bar from Q!!! I'm wondering: would it not be easier to just make it that the package name is prepended to the hierarchical module name, so the modules would instead be called by the names P.Data.Foo and Q.Data.Bar? As I see it, this would have at least these advantages: 1) A package author would only have to ensure that the name of the package (eg Edison, FPS, Base) is globally unique, and would then be free to name the modules in the package without having to worry about conflicts with other packages 2) Users of packages could specify exactly which modules they want to use, which would also make it easier to switch between different implementations of the same data type provided by different people etc 3) When you read the program text, you could immediately see which packages the modules came from, so you would know which packages you need to download if you don't currently have that module on your system. (At the moment, if I come across "import Data.Foldable" I've got no idea where to get it from.) It seems to me that the only reason this wasn't done in the first place was that originally there was just a flat module namespace, whereas with hierarchical modules it seems obvious to put the package name at the beginning (eg in Java the modules are called java.xyz, com.company.xyz etc to ensure there are no namespace conflicts) (On the Haskell' wiki there is http://hackage.haskell.org/trac/haskell-prime/wiki/SolveThePackageAbstracti… but this doesn't appear to consider the above solution.) Regards, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com

16 37

Trace parser
by Andy Georges 10 Jul '06

10 Jul '06

Hello, I'm looking for a bit of help (ok, a lot) the speed up my program which I use to build a calltree out of an annotated program execution trace. To give you an idea about the sluggishness at the moment, for a trace containing 70MB, it has been running for about 10 hours straight (AMD Athlon XP (Barton) 2600+). The trace contains lines made up of a number of fields: C 4 1000 1000000 C 4 1001 1000200 R 4 1001 1003045 R 4 1000 1003060 C indicates a function entrypoint (call), R indicates a function exitpoint (return). The second field indicates which thread is executing the function, the third field denotes the function id, the last field contains a performance counter value. As you can see, numbering each line with a pre-order and a post-order number yields a list that can be transformed easily into a tree, which can then be manipulated. The first goal is to build the tree. This is done in the following code: data ParserState = ParserState { methodStack :: !ThreadMap , methodQueue :: !ThreadMap , pre :: !Integer , post :: !Integer , methodMap :: !MethodMap , currentThread :: !Integer } deriving (Show) initialParserState :: ParserState initialParserState = ParserState e e 0 0 e 0 where e = M.empty :: Map Integer a readInteger :: B.ByteString -> Integer readInteger = fromIntegral . fst . fromJust . B.readInt parseTraceMonadic :: [B.ByteString] -> ParserState parseTraceMonadic ss = state { methodQueue = M.map reverse (methodQueue state) } where state = execState (mapM_ (\x -> modify (updateState x) >> get >>= (`seq` return ())) ss) initialParserState updateState :: B.ByteString -> ParserState -> ParserState updateState s state = case (B.unpack $ head fields) of "M" -> updateStateMethod fields state "E" -> updateStateException fields state "C" -> updateStateEntry fields state "R" -> updateStateExit fields state where fields = B.splitWith (== ' ') s updateStateMethod :: [B.ByteString] -> ParserState -> ParserState updateStateMethod (_:methodId:methodName:_) state = state { methodMap = M.insert (readInteger methodId) methodName (methodMap state) } updateStateException :: [B.ByteString] -> ParserState -> ParserState updateStateException _ state = state updateStateEntry :: [B.ByteString] -> ParserState -> ParserState updateStateEntry (_:ss) state = {-Debug.Trace.trace ("before: " ++ (show state) ++ "\nafter: " ++ (show newstate)) $-} newstate where newstate = state { methodStack = updateMap thread (methodStack state) (\x y -> Just (x:y)) (pre state, 0, method) , pre = ((+1) $! (pre state)) } method = mkMethod (Prelude.map B.unpack ss) thread = Method.thread method updateStateExit :: [B.ByteString] -> ParserState -> ParserState updateStateExit (_:ss) state = {-Debug.Trace.trace ("before: " ++ (show state)) $-} case updateMethod m (Prelude.map B.unpack ss) of Just um -> state { methodStack = M.update (\x -> Just (tail x)) thread (methodStack state) , methodQueue = updateMap thread (methodQueue state) (\x y -> Just (x:y)) (pre_, post state, um) , post = ((+1) $! (post state)) } Nothing -> error $ "Top of the stack is mismatching! Expected " ++ (show m) ++ " yet got " ++ (show ss) ++ "\n" ++ (show state) where method = mkMethod (Prelude.map B.unpack ss) thread = Method.thread method (pre_, _, m) = case M.lookup thread (methodStack state) of Just stack -> head stack Nothing -> error $ "Method stack has not been found for thread " ++ (show thread) ++ " -> fields: " ++ (show ss) updateMap key map f value = case M.member key map of True -> M.update (f value) key map False -> M.insert key [value] map As you can see, the state is updated for each entry, a stack being maintained with methods we've seen up to now, and a list with methods that have received both pre and post order numbers, and of which both the entry and exit point have been parsed. I am using a ByteString, because using a plain String is causing the program to grab far too much heap. The mkMethod yields a Method like this: data Method = Method { mid :: Integer , thread :: Integer , instruction_entry :: Integer , instruction_exit :: Integer } deriving (Eq, Show) eM = Method 0 0 0 0 mkMethod :: [String] -> Method mkMethod s = let [_thread, _id, _entry] = take 3 $ map (read :: String -> Integer) s in [_thread, _id, _entry] `seq` Method { mid = _id , thread = _thread , instruction_entry = _entry , instruction_exit = 0 } updateMethod :: Method -> [String] -> Maybe Method updateMethod (Method mid thread instruction_entry instruction_exit ) s | thread == _thread && mid == _id = _exit `seq` Just Method { mid = mid , thread = thread , instruction_entry = instruction_entry , instruction_exit = _exit } | otherwise = Nothing where [_thread, _id, _exit] = take 3 $ map (read :: String -> Integer) s Any suggestions for improving this code? Thanks, Andy

2 2

help with creating a DAG?
by David Roundy 09 Jul '06

09 Jul '06

Hi all, I'm wanting to create a data structure to hold a directed acyclic graph (which will have patches represented by edges), and haven't yet been able to figure out a nice representation. I'd like one that can be reasoned with recursively, or as closely to recursively as possible. The problem is one of dependency relations between darcs patches, and "normally" reduces to a simple tree, with conflict resolution patches bringing branches of the tree back together. Trees I know how to handle intuitively and elegantly, but DAGs are a whole different question. I looked for papers, and there was one on "an initial-algebra approach to DAGs" that looked promising, but I'm afraid I wasn't able to fully understand it, and it is able to describe more complicated DAGs than I'd like to support. Anyhow, any suggestions from persons with experience with this sort of thing would be great. These are getting to be data structures that are more complicated than anything I'm comfortable with. :( -- David Roundy

4 4

Strictness in do block
by John Goerzen 08 Jul '06

08 Jul '06

Hi, One thing that seems to keep biting me is strictness in do blocks. What I want to know is the generic way to force an entire String (or other list, perhaps from hGetContents) to be evaluated (read into RAM, I guess) so the underlying file can be closed.... and do it right now. One quick hack that works is hPutStrLn on it, right where I want it to be evaluated. But ugly and not always appropriate. Passing it to some other IO-based functions also works, but again, that doesn't "feel" right. I can always stumble upon things that work, but I'm never sure if I've got 'em right. So, what is the idiomatic way to do this? Most of the documents I see out there on this topic are for usage outside the I/O monad, and I'm not seeing how they apply here. Thanks, -- John

6 6

WxHaskell Question: How to get mouse or context menu events for wxGrid
by Jason Dagit 07 Jul '06

07 Jul '06

Hello, Not sure where to ask this question but maybe here is a good place. I'm trying to use wxHaskell and I need a table with a right-click context menu. So far it seems that I can get some events on a wxGrid but not the context menu event or the mouse right click event. To get grid events I've followed the example in the wxHaskell source which grabs grid events. Using this technique I can get mouse right-clicks if they happen in a cell. I was hoping to get the events when the click happens in the wxGrid control but not over a cell (for example, you might click below the last row and the menu would have an option to create a new row). I tried the following but the events never seem to fire: windowOnMouse myGrid True (_ -> logMessage "mouse event" >> propagateEvent) windowOnContextMenu myGrid (logMessage "context menu") I have logMessage set to use stderr for output and I know it works great. Any ideas on how to do this? Thanks, Jason

1 0

Prefix/Infix operators
by Sara Kenedy 07 Jul '06

07 Jul '06

Hello everybody, I checked the topics in Haskell-Cafe about prefix/infix operators but I did not find them. Now I bring my questions to here to ask you. 1) I have a Common-Lisp code representing an expression result as follows ((MPLUS SIMP) ((MTIMES SIMP) ((RAT SIMP) 1 2) ((MEXPT SIMP) $X 2)) ((MTIMES SIMP) ((RAT SIMP) 1 3) ((MEXPT SIMP) $X 3))) 2) I attempted to change it to mathematics operators, replacing MPLUS SIMP -> + MEQUAL SIMP -> = RAT SIMP -> / MEXPT SIMP -> ^ translate :: String -> String translate [] = [] translate ('(':'M':'P':'L':'U':'S':' ':'S':'I':'M':'P':')':xs) = "(+)" ++ translate xs translate ('(':'M':'T':'I':'M':'E':'S':' ' :'S':'I':'M':'P':')':xs) = "(*)" ++ translate xs translate ('(':'M':'E':'Q':'U':'A':'L':' ' :'S':'I':'M':'P':')':xs) = "(=)" ++ translate xs translate ('(':'R':'A':'T':' ':'S':'I':'M':'P':')':xs) = "(/)" ++ translate xs translate ('(':'M':'L':'I':'S':'T':' ':'S':'I':'M':'P':')':xs) = "([])" ++ translate xs translate ('(':'M':'E':'X':'P':'T':' ':'S':'I':'M':'P':')':xs) = "(^)" ++ translate xs translate ('$':'X':xs) = "x" ++ translate xs translate ('$':'Y':xs) = "y" ++ translate xs translate (x:xs) = x:translate xs 3) And NOW I want to transfer from prefix operator into infix operator, for example: From ((+) ((*) ((/) 1 2) ((^) x 2)) ((*) ((/) 1 3) ((^) x 3))) in to the expression: 1/2*x^2+1/3*x^3 I try to figure out it, but this time it is not successfully. If you are familiar with that, please share with me. Many thanks to all. S.

2 1

Re: Packages and modules
by Chris Kuklewicz 07 Jul '06

07 Jul '06

seth(a)cql.com wrote: >> "Simon Peyton-Jones" <simonpj(a)microsoft.com> writes: >> >>> Brian Hulley wrote: >>> | import A.B.C( T1 ) from "foo" >>> | import A.B.C( T2 ) from "bar" >>> | type S = A.B.C.T1 -> A.B.C.T2 >>> | I'd suggest that the above should give a compiler error that A.B.C is >>> | ambiguous (as a qualifier), rather than allowing T1 to disambiguate >>> it, >>> But that's inconsistent with Haskell 98. >> FWIW, I agree with Brian that this is not good practice. If it can't >> be forbidden, I would suggest that compilers emit a warning about it. > > Is there really a case where someone would use that pattern intentionally? > I'd vote for making it an error by default. Perhaps then a flag would be > available that says "accept dangerous constructs that are legal according > to Haskell 98". > The Haskell 98 behavior compensates for the case where the module you used to import Old (foo,bar) has been split into two new modules, A(foo) and B(bar). You can import A as Old and B as Old so that Old.foo and Old.bar now resolve to A.foo and B.bar. I expect the pattern for the above would actually be closer to > import Old(T1,T2) from "original" > > mine :: Old.T1 -> Old.T2 becoming > import qualified A.B.C(T1) as Old from "foo" > import qualified D.E.F(T2) as Old from "bar" > > mine :: Old.T1 -> Old.T2 Which is a syntax that should be supported. -- Chris

1 0

Windows Haskell GUI
by Neil Mitchell 06 Jul '06

06 Jul '06

Hi, I want to develop a GUI using Haskell on Windows. As far as I can tell the options for a reasonably high level GUI toolkit are: * wxHaskell * Gtk2Hs Unfortunately I cannot find released packages for GHC 6.4.2 for either of them - Gtk supports only 6.4.1 and wx supports only 6.4.0. Does anyone have builds of either of these that work with 6.4.2? Thanks Neil

4 6

Haskell as embedded DSL
by Joel Reymont 06 Jul '06

06 Jul '06

Folks, Do you have examples of using Haskell as a DSL in an environment NOT targeted at people who know it already? I'm thinking of using Haskell to build my Mac trading app but I'm very concerned about dumping Haskell on the trading systems developers. It seems that using, say, Ruby as the trading systems DSL would give me a leg up since it's simple and syntax and generally warm and fuzzy. What do you think? Thanks, Joel P.S. Yes, I'm a big fan of "Composing Financial Contracts" -- http://wagerlabs.com/

4 4

Re: [Haskell-cafe] New Benchmark Under Review: Magic Squares
by Daniel Fischer 05 Jul '06

05 Jul '06

Am Mittwoch, 5. Juli 2006 21:28 schrieben Sie: > Hi Daniel, > > In the paragraph below it looks like you improved the performance of > 5x5 from one and one half hours to one second. Is that a typo or > should I be very, very impressed. :-) > > Cheers, David Err, neither, really. Apparently, I haven't expressed myself immaculately clearly, so let me try again. Josh Goldfoot's original code produced a 5x5 magic square on the benchmarking computer in 8063.01s, on my computer, I hit ctrl-C after about 4 1/2 hours. My first version produced a 5x5 square in a little over 4 seconds (or was it a little over 5s, I'm not sure), and a 6x6 square in 86.5s, but since I used better bounds for the possible moves - e.g., if we regard a 5x5 square with two entries, 1 at (1,1) and 2 at (1,2), JG's code would give [3 .. 25] as the list of possible moves for (1,3), whereas I took into account that the sum of (1,4) and (1,5) is at most 24 + 25 = 49 (and at least 3+4, but that doesn't help here), thus finding that (1,3) must be at leat 65 - (1+2) - 49 = 13 and [13 .. 25] as the list of possible moves. So I avoided a lot of dead ends, but produced a different magic square. This code I have pushed down to 1s for the 5x5 square and 5.4s for the 6x6 square (simply by replacing "intersect [a .. b]" with "takeWhile (<= b) : dropWhile (< a)"). I have then tuned Josh Goldfoot's code (throwing out the List <-> Set conversions, keeping a list of unused numbers and not much else), so that it produced a 5x5 square in 1 1/2 hours on my computer, giving the same list of possible moves as the original and hence the same magic square. That's not bad, but not really awe-inspiring. However, I've also combined the algorithms, using my better bounds, thus avoiding many dead ends, but calculating the priorities as if I used the original bounds, so exploring the branches in the same order and producing the same square as the original. This took about 12 minutes for a 5x5 square and impressed me - I expected it to be significantly slower than the fast code, but a factor of 720 was much more than I dreamed of. Cheers, Daniel > > On Jul 4, 2006, at 6:48 AM, Daniel Fischer wrote: > > Hi, > > I have now tuned Josh Goldfoot's code without changing the order in > > which the > > magic squares are produced, for a 5x5 magic square, my machine took > > about 1 > > 1/2 hours and used 2Mb memory (considering that the original code > > did not > > finish within 4 1/2 hours here, that should push time on the > > benchmarking > > machine under 3000s and put us in the lead, I hope). > > However, with the improved bounds for the possibilities, I can now > > get a 5x5 > > square in 1s, a 6x6 square in 5.5s (replacing intersect by takeWhile & > > dropWhile), so it's still sloooowwww. > > > > Brent, can I informally submit the code thus, or what formalities > > would I have > > to perform to submit my code? > > > > ---------------------------------------------------------------------- > > ----------------------------- > > {- The Computer Language Shootout > > http://shootout.alioth.debian.org/ > > > > benchmark implementation > > contributed by Josh Goldfoot > > modified by Daniel Fischer to improve performance -} > > > > {- An implementation using Data.Graph would be much faster. This > > implementation > > is designed to demonstrate the benchmark algorithm. -} > > > > import Data.Array > > import Data.List > > import System (getArgs) > > > > main = do > > n <- getArgs >>= return . read . head > > let mn = (n * (1 + n * n)) `div` 2 -- the magic number > > initialNode = makeSquare n mn (listArray ((1,1),(n,n)) > > (repeat 0), [1 > > .. n^2]) > > allSquares = bestFirst (successorNodes n mn) (initialNode:[]) > > putStrLn $ printMatrix n $ grid $ head allSquares > > where > > printMatrix n grid = unlines [ (rowlist grid n y) | y <- > > [1..n]] > > where > > rowlist grid n y = unwords [show $ grid ! (x,y) | x > > <- [1..n]] > > > > data Square = Square { grid :: Array (Int,Int) Int, > > ffm :: ([Int], Int, Int), > > unused :: [Int], > > priority :: !Int } > > > > {- bestFirst: Given a queue with one initial node and a function, > > successors, > > that takes a node and returns a list of nodes that are created > > by making > > all possible moves in a single cell, implements the Best-First > > algorithm, > > and returns a list of all nodes that end up with priority > > zero. In this > > implementation we only ever use the first node. > > -} > > bestFirst _ [] = [] > > bestFirst successors (frontnode:priorityq) > > > > | priority frontnode == 0 = frontnode:bestFirst successors > > > > priorityq > > > > | otherwise = bestFirst successors $ foldr (insertBy > > > > compSquare) priorityq > > (successors frontnode) > > where > > {- The priority queue is sorted first by > > the node's calculated priority; then, if the priorities > > are equal, by whichever node has the lowest numbers > > in the top-left of the array (or the next cell over, > > and so on). -} > > compSquare a b = case compare (priority a) (priority b) of > > EQ -> compare (grid a) (grid b) > > ot -> ot > > > > {- successorNodes: Find the cell with the fewest > > possible moves left, and then creates a new node for each > > possible move > > in that cell. > > -} > > successorNodes n mn squarenode = > > map (makeSquare n mn) [(thegrid//[((x, y), i)], delete i un) | > > i <- > > possibilities] > > where > > thegrid = grid squarenode > > un = unused squarenode > > (possibilities, x, y) = ffm squarenode > > > > {- makeSquare: Creates a node for the priority queue. In the > > process, this > > calculates the cell with the fewest possible moves, and also > > calculates > > this node's priority. The priority function is: > > (number of zeros in the grid) > > plus > > (number of possible moves in the cell with the fewest > > possible moves) > > the lower the priority, the sooner the node will be popped from > > the queue. > > -} > > makeSquare n mn (thegrid,un) = > > Square { grid = thegrid, ffm = moveChoices, unused = un, > > priority = > > calcPriority } > > where > > moveChoices@(poss,_,_) = findFewestMoves n mn thegrid un > > calcPriority = length un + length poss > > > > {- findFewestMoves: Go through the grid (starting at the top-left, > > and moving > > right and down), checking all 0 cells to find the cell with > > the fewest > > possible moves. > > -} > > findFewestMoves n mn grid un > > > > | null un = ([],0,0) > > | otherwise = (movelist, mx, my) > > > > where > > openSquares = [ (x,y) | y <- [1..n], x <- [1..n], (grid ! > > (x,y)) == 0] > > pm = possibleMoves n mn grid un > > openMap = map (\(x,y) -> (pm (x,y), (x,y))) openSquares > > mycompare f g = compare ((length . fst) f) ((length . fst) g) > > (movelist, (mx, my)) = minimumBy mycompare openMap > > > > {- possibleMoves: Return all moves that can go in the cell x,y for > > a given > > grid. A move is possible if the move (number) is not already > > in the grid, and if, after making that move, it is still > > possible to > > satisfy the magic square conditions (all rows, columns, > > diagonals adding > > up to mn, the magic number) > > -} > > possibleMoves n mn grid un (x,y) > > > > | grid ! (x,y) /= 0 = [] > > | null oneZeroGroups = takeWhile (<= highest) un -- [1 .. highest] > > > > `intersect` un > > > > | otherwise = case onePossible of > > > > [p] | p `elem` un -> [p] > > _ -> [] > > where > > cellGroups > > > > | x + y == n + 1 && x == y = [diag1 grid n, diag2 grid > > > > n, theRow, > > theCol] > > > > | x == y = [diag1 grid n, theRow, theCol] > > | x + y == n + 1 = [diag2 grid n, theRow, theCol ] > > | otherwise = [theRow, theCol] > > > > theRow = gridRow grid n x y > > theCol = gridCol grid n x y > > oneZeroGroups = filter (\x -> count 0 x == 1) cellGroups > > onePossible = nub ( [mn - (sum g) | g <- oneZeroGroups ] ) > > highest = minimum ( (n*n):[mn - (sum g) | g <- cellGroups] ) > > > > {- Utility functions to extract a single row, column, or diagonal. -} > > gridRow grid n _ y = [grid ! (xx, y) | xx <- [1..n]] > > gridCol grid n x _ = [grid ! (x, yy) | yy <- [1..n]] > > diag1 grid n = [grid ! (i, i) | i <- [1..n]] > > diag2 grid n = [grid ! (i, n - i + 1) | i <- [1..n]] > > > > {- Returns the number of times n appears n list xs -} > > count n xs = length $ filter ((==) n) xs > > > > ---------------------------------------------------------------------- > > ----------------------------- > > > > Am Sonntag, 2. Juli 2006 01:58 schrieb Brent Fulgham: > >> We recently began considering another benchmark for the shootout, > >> namely a Magic Square via best-first search. This is fairly > >> inefficient, and we may need to shift to another approach due to the > >> extremely large times required to find a solution for larger squares. > >> > >> I thought the Haskell community might be interested in the > >> performance we have measured so far (see "http:// > >> shootout.alioth.debian.org/sandbox/fulldata.php? > >> test=magicsquares&p1=java-0&p2=javaclient-0&p3=ghc-0&p4=psyco-0" > >> > >> Interestingly, Java actually beats the tar out of GHC and Python for > >> N=5x5 (and I assume higher, though this already takes on the order of > >> 2 hours to solve on the benchmark machine). Memory use in GHC stays > >> nice and low, but the time to find the result rapidly grows. > >> > >> I was hoping for an order of magnitude increase with each increase in > >> N, but discovered that it is more like an exponential... > >> > >> Thanks, > >> > >> -Brent > > > > Cheers, > > Daniel > > > > -- > > > > "In My Egotistical Opinion, most people's C programs should be > > indented six feet downward and covered with dirt." > > -- Blair P. Houghton > > > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > -------------------------------- > David F. Place > mailto:d@vidplace.com -- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton

1 0