- Haskell-Cafe - Haskell.org

External Sort: Sort a 10-million integer file with just 256M of ram.
by Thomas Hartman 27 Oct '08

27 Oct '08

Now on hackage: cabal install external-sort demo (included in distribution): thartman@thartman-laptop:~/external-sort>cat demo.hs {-# LANGUAGE PatternSignatures #-} import Algorithms.ExternalSort import Data.List import System.IO import System.Environment (getArgs) import System.Time import HSH -- to do: compare speed against unix sort util on a 10 million line file. -- pure in-memory prelude sort will crash your computer when the list gets over a million elements or so -- externalsort caches the sublists used in the sort algorithm on your hard drive, so you can sort a much larger list. {- The behavior below was on a demo executable, compiled. (In ghci, even last on a 10 million element list caused an out of memory error.) The test computer had 256M physical ram and was ulimited to 256M cache. *Main>:! ulimit -v 262144 For 10 million element list: *Main> :! time ./demo preludesort 7 demo: out of memory (requested 1048576 bytes) Command exited with non-zero status 1 4.88user 0.68system 0:21.11elapsed 26%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+64817minor)pagefaults 0swaps *Main> :! time ./demo externalsort 7 10000000 73.87user 1.96system 1:24.25elapsed 90%CPU (0avgtext+0avgdata 0maxresident)k 792inputs+156280outputs (6major+16739minor)pagefaults 0swaps ./demo unixsort 7 wrote bigfile, time: Mon Oct 20 15:25:26 CEST 2008 demo: out of memory (requested 1048576 bytes) For 100 million element list, external sort failed. Can it be made to work? maybe in some future version. time ./demo externalsort 8 demo: out of memory (requested 1048576 bytes) real 10m14.061s user 8m26.712s sys 0m11.793s thartman@thartman-laptop:~/external-sort>ls -lh ExternalSort.bin -rw-r--r-- 1 thartman thartman 764M Oct 20 15:50 ExternalSort.bin The problem is not fitting a 10^8 element list in memory, the following works fine (when compiled, though not in ghci): t = putStrLn . show . last $ [1..10^8::Int] Maybe think about this more later. -} main = do [s,e] <- getArgs let exp = read e case s of "preludesort" -> sortwith exp $ return . sort "externalsort" -> sortwith exp externalSort "unixsort" -> unixsort exp _ -> let msg = "usage: ./demo preludesort 7 or ./demo externalsort 7 or ./demo unixsort 7 \ \(sort 10 million element list)" in fail msg sortwith exp s = putStrLn =<< return . show . last =<< s ([1..10^exp ::Int]) unixsort exp = do let fn = "bigfile" withFile fn AppendMode (\h -> (mapM_ (hPutStrLn h . show) ([1..10^exp::Int]) ) ) putStrLn . ( ("wrote " ++ fn ++ ", time: ") ++ ) . show =<< getClockTime run $ "time tail -n1 | sort " ++fn :: IO String return () t = putStrLn . show . last $ [1..10^8::Int]

5 6

Instances of Lattice?
by Galchin, Vasili 27 Oct '08

27 Oct '08

Hi Henning, I am rereading my emails and I don't believe I got an examples of "instance Lattice". E.g. instance Lattice Bool. ?? Thanks, Vasili

2 1

Examples of Mutually Recursive Types
by Hugo Pacheco 26 Oct '08

26 Oct '08

Hi all, I have been searching for examples of Haskell "real scenarios" that employ mutually recursive datatype definitions. Does anyone know some interesting libraries or structures that I could play with? Thanks, hugo -- www.di.uminho.pt/~hpacheco

6 6

problem using ST monad
by Paul L 26 Oct '08

26 Oct '08

I'm have some trouble using the ST monad, and I think I'm confused about its use of existential type. > {-# OPTIONS -XRankNTypes #-} > import Control.Monad.ST > import Data.Array.ST I want to implement a map function that unfold all ST monads in a list: > mapST :: (a -> (forall s . ST s b)) -> [a] -> [b] > mapST f (x:xs) = runST (f x) : mapST f xs > mapST f [] = [] This is fine. However, it wouldn't typecheck if I had declared its type differently: mapST :: (a -> ST s b) -> [a] -> [b] I first thought the reason could be that runST has to take something of type (forall s . ST s b), but apparently this is not the case: > g :: (STArray s Int Int -> ST s a) -> ST s a > g f = newArray (0,0) 0 >>= f with this definition, runST (t (flip readArray 0)) happily returns me 0, despite the fact that the "s" in the type of "g" is not existentially quantified. Then when I try this one: mapST g [flip readArray 0] It fails to typecheck. Why? Is it possible, if at all, to implement a generic mapST? -- Regards, Paul Liu Yale Haskell Group http://www.haskell.org/yale

4 6

Slavomir Kaslev has invited you to radiusIM.com
by Slavomir Kaslev 26 Oct '08

26 Oct '08

2 1

Haskell Weekly News: Issue 90 - October 25, 2008
by Brent Yorgey 25 Oct '08

25 Oct '08

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20081025 Issue 90 - October 25, 2008 --------------------------------------------------------------------------- Welcome to issue 90 of HWN, a newsletter covering developments in the [1]Haskell community. One day a Haskell n00b asked the master coder, "Master, does (const 3 undefined) have the terminating nature, or not?" The master replied, "Of course." Cried the n00b, "But that changes everything! Why did you not tell me this before?" "You never asked." Immediately, the n00b was enlightened. Announcements Darcs hacking sprint. Eric Kow [2]announced that the [3]darcs hacking sprint is taking place this weekend! Lambdabot 4.2.2. Gwern Branwen [4]announced the release of [5]version 4.2.2 of lambdabot, the famous Haskell IRC bot. The new release has innumerable new features and bugfixes, trained suckling pigs, mermaids, etc. Autoproc Change of Maintainer (if you use procmail you should read this). Jason Dagit [6]announced that Gwern Branwen will be taking over the [7]autoproc project. Autoproc makes it quick and easy for Haskell programmers to make procmail recipes by using an embedded domain specific language. Once your recipes type check and compile, you simply run autoproc and it generates the corresponding procmail recipe. External Sort: Sort a 10-million integer file with just 256M of ram.. Thomas Hartman [8]announced the external-sort package. It implements an on-disk external sort algorithm in Haskell, which you can use to sort lists that will not fit in memory. IEEE-utils. Sterling Clover [9]announced the [10]IEEE-utils package, providing a number of bindings for anyone interested in doing hardcore floating-point programming. rewriting-0.1. Thomas van Noort [11]announced the release of [12]rewriting, a generic rewriting library for regular datatypes. Features include generic rewriting machinery, generic traversals, and rewrite rules defined as values instead of functions. REMINDER: Haskell Communities and Activities Report. Janis Voigtlaender [13]reminded everyone that the deadline for the November 2008 edition of the Haskell Communities and Activities Report (Friday, October 31) is approaching fast! If you haven't already, please write an entry for your new project, or update your old entry. For more information, see the original [14]call for contributions. lhs2tex-1.14. Andres Loeh [15]announced the release of [16]lhs2TeX version 1.14, a a preprocessor to generate LaTeX code from literate Haskell sources. colour 0.0.0. roconnor [17]announced an initial release of the [18]colour package. It is hoped that this library will become the standard colour library for Haskell. Discussion Hackage Improvement Ideas. Jason Dagit [19]suggested some improvements to Hackage and asked for others to contribute their ideas as well. Spine-lazy "multiqueue". Luke Palmer [20]asked for help implementing an efficient spine-lazy multiqueue. Jobs Functional programming job opening. Simon Peyton-Jones [21]announced a [22]job opening in functional programming at Microsoft. They are looking for "an experienced software development engineer who has mastered C/C++ and/or C# development and is now learning or is already an expert using F# (or Haskell)." Blog noise [23]Haskell news from the [24]blogosphere. * Eric Kow (kowey): [25]darcs hacking sprints - some pictures from Team Brighton. * Jason Dagit: [26]Understanding Darcs Commute. * Ketil Malde: [27]Optimization again: befuddled by bytestrings. * Creighton Hogg: [28]Revisiting old concepts. * Tupil: [29]On unit testing and type checking. * Eric Kow (kowey): [30]darcs weekly news #9. * >>> Alberto Corona: [31]Axioms and properties for haskell classes. Alberto demonstrates some code for adding checkable algebraic properties to type classes. * Creighton Hogg: [32]A serious problem. Creighton with some straight talk about typeclass abuse. * London Haskell Users Group: [33]Next meeting: Duncan Coutts on the Haskell Platform. * Manuel M T Chakravarty: [34]Keep those cores busy!. A comprehensive account of the full vectorisation transformation underlying the implementation of nested data parallelism in GHC. * Conal Elliott: [35]Simpler, more efficient, functional linear maps. * Conal Elliott: [36]Vector space bases via type families. * >>> Sebastian Fischer: [37]Constrained Monadic Computations. * Luke Palmer: [38]I know what I'm going to get for christmas. "I believe I have found a truly marvelous implementation of FRP which this blog post is too short to contain." * >>> codeflow: [39]On Haskell and C++. * >>> Simon Dobson: [40]Why Haskell will take over the world. Simon has some thoughts on functional programming and the future of programming languages. * >>> Falko: [41]Learning Haskell's Basics - Problems from Project Euler. Quotes of the Week * vixey: debugging code is admitting defeat * kaomoji: [on #haskell] man, you guys are really nerdy * sclv: I guess I'd believe the universe was lazy if the hubble looked at that stuff way at the edge of the big bang diaspora and when we magnified the picture we saw "stack overflow" * rwbarton: relational calculus? "DIFFERENTIATE TABLE users WITH RESPECT TO name" * heatsink: ban :: (BanContext no, UserIdentifer u) => u -> no u * rwbarton: I tried typechecking the value of unwords (replicate 125 "fmap") in ghci once, and it consumed all my memory * ghc: Step 3: Zonk the kinds About the Haskell Weekly News New editions are posted to [42]the Haskell mailing list as well as to [43]the Haskell Sequence and [44]Planet Haskell. [45]RSS is also available, and headlines appear on [46]haskell.org. To help create new editions of this newsletter, please see the information on [47]how to contribute. Send stories to byorgey at cis dot upenn dot edu. The darcs repository is available at darcs get [48]http://code.haskell.org/~byorgey/code/hwn/ . References 1. http://haskell.org/ 2. http://www.haskell.org//pipermail/haskell-cafe/2008-October/049775.html 3. http://wiki.darcs.net/index.html/Sprints 4. http://article.gmane.org/gmane.comp.lang.haskell.cafe/46842 5. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/lambdabot 6. http://article.gmane.org/gmane.comp.lang.haskell.cafe/46841 7. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/autoproc 8. http://article.gmane.org/gmane.comp.lang.haskell.cafe/46776 9. http://www.haskell.org//pipermail/haskell-cafe/2008-October/049760.html 10. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ieee-utils 11. http://article.gmane.org/gmane.comp.lang.haskell.cafe/46750 12. http://www.cs.uu.nl/wiki/GenericProgramming/Rewriting 13. http://article.gmane.org/gmane.comp.lang.haskell.cafe/46696 14. http://www.haskell.org/pipermail/haskell/2008-October/020651.html 15. http://article.gmane.org/gmane.comp.lang.haskell.general/16538 16. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/lhs2tex 17. http://article.gmane.org/gmane.comp.lang.haskell.general/16524 18. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/colour 19. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/46764 20. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/46710 21. http://article.gmane.org/gmane.comp.lang.haskell.general/16511 22. http://members.microsoft.com/careers/search/details.aspx?JobID=E29D3886-A15… 23. http://planet.haskell.org/ 24. http://haskell.org/haskellwiki/Blog_articles 25. http://koweycode.blogspot.com/2008/10/darcs-hacking-sprints-some-pictures.h… 26. http://blog.codersbase.com/2008/10/24/understanding-darcs-commute/ 27. http://blog.malde.org/index.php/2008/10/24/optimization-again-befuddled-by-… 28. http://abstractabsurd.blogspot.com/2008/10/revisiting-old-concepts.html 29. http://blog.tupil.com/on-unit-testing-and-type-checking/ 30. http://koweycode.blogspot.com/2008/10/darcs-weekly-news-9.html 31. http://haskell-web.blogspot.com/2008/10/axioms-properties-for-haskell-class… 32. http://abstractabsurd.blogspot.com/2008/10/serious-problem.html 33. http://www.londonhug.net/2008/10/22/next-meeting-duncan-coutts-on-the-haske… 34. http://justtesting.org/post/55387637 35. http://feeds.feedburner.com/~r/conal/~3/425946113/ 36. http://feeds.feedburner.com/~r/conal/~3/425935010/ 37. http://www-ps.informatik.uni-kiel.de/~sebf/projects/constraint-monad.html 38. http://luqui.org/blog/archives/2008/10/19/i-know-what-im-going-to-get-for-c… 39. http://codeflow.wordpress.com/2008/10/18/on-haskell-and-c/ 40. http://www.simondobson.org/?p=179 41. http://informatikr.wordpress.com/2008/10/13/learning-haskells-basics-proble… 42. http://www.haskell.org/mailman/listinfo/haskell 43. http://sequence.complete.org/ 44. http://planet.haskell.org/ 45. http://sequence.complete.org/node/feed 46. http://haskell.org/ 47. http://haskell.org/haskellwiki/HWN 48. http://code.haskell.org/~byorgey/code/hwn/

1 0

Hackage Improvement Ideas
by Jason Dagit 25 Oct '08

25 Oct '08

Hello, I was thinking of fun little projects people could work on to improve Hackage: 1) Popularity statistics -- like debian's popcon, gives stats on how many people have which packages from hackage installed 2) Per package ratings and feedback listed on the page for each package 3) A way to mark a package as "should be removed" 4) All the hackage pages should be wiki editable -- for example, the intro page refers to cabal-install as experimental but I think it's moved beyond that point but I'm not sure how to edit that sentence. What else should hackage do? Who wants to claim one of the above earn some serious karma? Jason

4 4

duplicate instance declarations. Why?
by Alberto G. Corona 25 Oct '08

25 Oct '08

with: >{-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-} >class A a >class R a >class S a >instance R a => A a >instance S a => A a ---------- GHC gives *Duplicate instance declarations* * instance R a => A a * * instance S a => A a * ** *Why?*

4 3

Crash!
by Andrew Coppin 25 Oct '08

25 Oct '08

Well what do you know? I have actually managed to write a pure Haskell program that generates an actual access violation when run! o_O I was under the impression that this is impossible, so I'm now slightly worried. The weird thing is, I spent 4 hours using the program without issue. However, when you feed it one specific input, it crashes. And I'm really not sure why. However, it appears to crash while asking GTK to save a PNG file. (??) That doesn't make a lot of sense, obviously. I do have some calls to unsafe array functions, but that doesn't appear to be where the crash is happening. Does anybody have any clue where I start with trying to diagnose this? I'm out of my depth...

13 21

3-state, 2-symbol busy beaver
by Maurício 25 Oct '08

25 Oct '08

Hi, Just some easy fun: $> ghci Prelude> :l busyBeaver.hs Prelude> map snd busyBeaver [A,B,A,C,B,A,B,B,B,B,B,A,C,Halt] Best, Maurício -- | busyBeaver.hs data State = A | B | C | Halt deriving Show data Value = Blank | NonBlank type Tape = (Integer -> Value) moveRight tape = \n -> tape $ n - 1 moveLeft tape = \n -> tape $ n + 1 (write tape) n = if n == 0 then NonBlank else tape n table :: (Tape,State) -> (Tape,State) table (tape,state) = case (tape 0,state) of (Blank,A) -> ((moveRight . write) tape , B) (NonBlank,A) -> ((moveLeft . write) tape , C) (Blank,B) -> ((moveLeft . write) tape , A) (NonBlank,B) -> ((moveRight . write) tape , B) (Blank,C) -> ((moveLeft . write) tape , B) (NonBlank,C) ->((moveRight . write) tape , Halt) (_,Halt) -> (tape,Halt) busyBeaver = bb (const Blank,A) where bb t@(_,Halt) = t:[] bb t = t:(bb $ table t)

1 0