- Haskell-Cafe - Haskell.org

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

Trading with Haskell
by Joel Reymont 05 Jul '06

05 Jul '06

Is there anyone trading with Haskell or interested in doing it? Thanks, Joel -- http://wagerlabs.com/

3 3

Re: Comments from Brent Fulgham on Haskell and the shootout
by Simon Marlow 05 Jul '06

05 Jul '06

John Meacham wrote: > On Tue, Jun 27, 2006 at 02:58:05PM +0100, Simon Marlow wrote: > >>>.. (and jhc already generates native C code, so it will have at least >>>one substantial advantage over GHC) ... >> >>Compiling via C is a dead end. We realised this about 5 years ago, and >>yet we still haven't managed to shake off the C backend from GHC, but I >>remain hopeful that one day we will. /me heads for the cafe... > > Out of curiosity, compiling via C as opposed to what? c--? Parrot? JVM? C-- ultimately, but in the meantime GHC's built in native-code generator. Our NCG is quite reasonable, and we plan to push it forward in various ways to improve the generated code. There's a wiki page with some ideas: http://hackage.haskell.org/trac/ghc/wiki/BackEndNotes Cheers, Simon

6 13

Darcs-synchronisation tool
by Christophe Poucet 05 Jul '06

05 Jul '06

Hello, I typically back up my darcs repositories on different computers. However I do always use the same structure for the different "forests" of darcs repositories. Lately my laptop charger has died which has led me to constantly use a usbstick to move these repositories. Therefore I have started working on a little tool that will automatically sychronise similarly laid out darcs-forests. At the moment it's very bare-to-the-bones. IT will only darcs pull from the repositories in one forest to the other. I later plan to add options to automatically darcs init when necessary (another thing which I've personally missed from time to time). So, if you find yourself in a similar situation, or you have thoughts, concerns, comments regarding it, feedback is welcome! The source can be found at http://www.notvincenz.com/wiki/uploads/Personal/ApplyDarcs.hs and requires Neil Mitchell's http://www.cs.york.ac.uk/fp/darcs/filepath/System/FilePath.hs renamed as plain FilePath.hs. Cheers, Christophe (vincenz)

1 0

Cyclic Type-synonyms
by Christophe Poucet 05 Jul '06

05 Jul '06

Hello, I use the Indirect Composite pattern a lot, and this means that typically, especially with recursive types (such as an AST), you end up with a lot of data-constructors. I understand that it is not possible to have pure cyclic types (because haskell requires iso-recursive and not equi-recursive types). However I wonder why certain cases can not be allowed. For instance, assume the following somewhat simplified AST: data Exp e = ELet String e e -- let x = a in b | ECond e e e -- If then else construct Now if I wanted to decorate this structure, I would use something like: data AnnotExp a = AE { unAE :: Exp (AnnotExp a), note :: a } However, and this example might be slightly too trivial to motivate it, however it does exemplify what can be done, one might not want to annotate at all and just have a recursive data AST. At this point, one either uses AnnotExp () or creates a new data type. It would be nice if instead one could use cyclic type-declarations, with the knowledge that we're going through a data-constructor and hence the type iso-recursive and not equi-recursive: type AST = Exp AST -- This is iso-recursive as it goes through the data constructors ELet and ECond Sadly this is not possible with the current GHC (I'm using 6..4.2). Is this possible with 6.6? Is there any reason why this is not possible. Feedback regarding this is welcome. A more motivating example can be seen below. Cheers, Christophe ----------------------------- data Exp var ident func exp stm = ELit Lit -- ^ Literals | EVar ident -- ^ Identifiers | EData Const [exp] -- ^ Data Constructors | ECall func -- ^ Function Calls | ELet var stm stm -- ^ Scoping | ECond exp stm stm -- ^ Conditional | ELoop exp stm -- ^ Looping deriving (Eq, Show) data AExp exp annot = AExp { unAExp :: exp, aexpNote :: annot, aexpLoc :: Location } type UnCorExp var annot = Exp var -- ^ Let-binders var -- ^ Named identifiers (Ident, [AExp UnCorExp var annot]) -- ^ Function calls (AExp UnCorExp var annot) -- ^ Expressions (AExp UnCorExp var annot) -- ^ Statements -- Flattened AST: function parameters can only be variables, similar for while- and if- conditions type UnSimExp var annot Exp var -- ^ Let-binders var -- ^ Named identifiers (Ident, [var]) -- ^ Function calls (var) -- ^ Expressions (AExp UnSimExp var annot) -- ^ Statements

1 1

Clever generic ByteString hack?
by John Goerzen 05 Jul '06

05 Jul '06

Hi, In MissingH, I have a bunch of little functions that operate on lists. Some, like uniq (which eliminates duplicate elements in a list), operate on (Eq a => [a]) lists. Others, like strip (which eliminates whitespace at the start and end), operate on Strings only. Most functions of both types would be useful on ByteStrings and lazy ByteStrings. Most of these functions are written in terms of Data.List functions or list primitives that have equivolents in Data.ByteString. So, my question is: is there a clever hack available to me so that I could have 1 version of each function, and have it work on all three different types of input? I'd rather avoid having 3 versions, that are exactly the same except for imports. Thanks, -- John

4 6

Re: [haskell] ANNOUNCE: HNOP 0.1
by mvanier 05 Jul '06

05 Jul '06

[Moving to haskell-cafe] OK, after going through this several times, here's what I've found: 1) The Debian linux build of haskell produces large executables. 2) The generic x86 binary distribution produces smallish executables (383765 bytes; still kind of large; stripped it's 191584 bytes). 3) I removed my entire source distribution, and recompiled from scratch with this build.mk file: SRC_HC_OPTS = -H64m -O2 GhcLibHcOpts = -O2 -fgenerics SplitObjs = YES I did an "autoreconf; configure; make; make install" and then recompiled hnop from scratch. I got large executables (2838528 bytes unstripped, 1540072 stripped). I'm at a loss here. Somehow, the SplitObjs option doesn't seem to be doing the job. Any suggestions would be appreciated. Mike Donald Bruce Stewart wrote: > Hmm. Did you build from scratch? Perhaps the libraries didn't get > rebuilt with split objs ? > > > mvanier: >> I've tried doing a manual build with SplitObjs set to YES, but without >> success; either the compiler was broken or it would still generate large >> executables. So as a sanity check, I installed the debian unstable build. >> But that one also gives me a huge executable: >> >> % ls -l >> total 2720 >> -rw-r--r-- 1 mvanier mvanier 818 Jun 29 20:48 LICENSE >> -rw-r--r-- 1 mvanier mvanier 308 Jun 30 04:59 Main.hi >> -rw-r--r-- 1 mvanier mvanier 80 Jun 29 20:48 Main.hs >> -rw-r--r-- 1 mvanier mvanier 1928 Jun 30 04:59 Main.o >> -rw-r--r-- 1 mvanier mvanier 43 Jun 29 20:48 Makefile >> -rwxr-xr-x 1 mvanier mvanier 2756151 Jun 30 04:59 hnop >> -rw-r--r-- 1 mvanier mvanier 807 Jun 29 23:56 hnop.tar.gz >> >> Am I the only person in the world with this problem? >> >> Also, for some inexplicable reason, debian puts ghci into /usr/X11R6/bin, >> though ghc is in the more sensible /usr/bin/ghc. >> >> TIA, >> >> Mike >> >> Donald Bruce Stewart wrote: >>> mvanier: >>>> Nope, just ghc-6.4.2 that I compiled myself on a Dell x86 laptop (Pentium >>>> M). I didn't use any strange configure options. Is there a special >>>> configure flag for split objects? If not, how is this determined? >>> Ah ha! You need to add -split-objs to the build.mk used by ghc to build >>> its libraries, as described here: >>> http://cvs.haskell.org/cgi-bin/cvsweb.cgi/~checkout~/fptools/ghc/HACKING?co… >>> >>> You want: >>> SplitObjs = YES >>> >>> in mk/build.mk >>> >>> It's not enabled by default, since it doesn't work on every platform. >>> The ghc that is distributed in the debian package system does have split >>> objs on, though. >>> >>> Cheers, >>> Don

3 4

Where is Data.Atom ?
by Brian Hulley 04 Jul '06

04 Jul '06

Hi - I seem to remember from some discussion long ago that there is a Data.Atom module somewhere (hopefully with a BSD licence), but a search on Hoogle turned up no results so maybe I'm mistaken. What I'm looking for is an Atom type and the following operations: fromString :: String -> Atom toString :: Atom -> String instance Eq Atom instance Ord Atom -- this is where things get difficult! It is particularly important that the ordering comparison is extremely fast, preferably independent of the length of the original String, and that it preserves the lexicographic ordering between the original Strings. I can see that an "unsafe" global ref to a Trie of Char with Unique as the "value" of a node would allow me to implement fromString, toString, and instance Eq Atom, but I've got no idea how to implement instance Ord Atom so that the order is independent of the order in which Atoms are created and exactly the same as the lexicographic ordering of the String without being O(n) where n is the min of the lengths of the Atoms being compared. I'm also hoping that Atoms which are no longer in use would manage to magically vanish by themselves. In a Trie implementation, this would mean maintaining an invariant that leaf nodes are always held by a weak link and internal nodes by a strong link. Any ideas (or pointers to a nice downloadable module that already does all this :-) )? Thanks, 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

8 14

HDF5
by Joel Reymont 04 Jul '06

04 Jul '06

Does anyone have bindings for HDF5 [1]? [1] http://hdf.ncsa.uiuc.edu/whatishdf5.html Thanks, Joel -- http://wagerlabs.com/

2 3

EclipseFP (Haskell IDE) 0.10.0 released
by Thiago Arrais 04 Jul '06

04 Jul '06

EclipseFP 0.10 has been released since last Friday. It is an open-source development environment for Haskell code. EclipseFP integrates GHC with an Haskell-aware code editor and also supports quick file browsing through an outline view, automatic building/compiling and quick one-button code execution. For this new release we have been working on code assistance support, something that has been heavily requested, and a Cabal editor. Downloads and more information are available on the project home page http://eclipsefp.sourceforge.net/ This release requires Eclipse 3.2, as opposed to Eclipse 3.1 that was required on the previous release. You may need to upgrade your Eclipse platform if you plan to use version 0.10. I have taken the liberty to create a wiki page for EclipseFP. You can post your comments and feature requests there, if you'd like. It is located at http://www.haskell.org/haskellwiki/EclipseFP Cheers, Thiago Arrais

7 12