October 2006 - Haskell

[Announce] Yhc Bytecode library 0.3
by Robert Dockins 29 Oct '06

29 Oct '06

[Please direct disccusion to the yhc list] Fellow Haskellers, I am pleased to announce the release of the Yhc Bytecode library, version 0.3. The major differences from version 0.2 are: * Updated to work with the current Yhc development branch as of 2006-10-13 * API modified to fully handle the string table so that it is no longer exposed to the user * Added support for the 'Ext' and 'Prim' object types * Slightly improved some error messages Source and Haddock documentation downloads are avaliable from: http://www.eecs.tufts.edu/~rdocki01/yhc-bytecode.html Direct access to the darcs repository from: http://www.eecs.tufts.edu/~rdocki01/yhc-bytecode/ Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG

1 0

How to find out who is leaking memory?
by szefirov＠ot.ru 29 Oct '06

29 Oct '06

My program is leaking memory. It is fairly complex and long running on the test that leaks. On that particular test it exits abnormally telling me that heap is overflown. Is there a way to find out what part is leaking memory without refactoring?

1 0

Animal guessing game - critique my code
by JTXX 29 Oct '06

29 Oct '06

Hello everybody. I'm trying to learn Haskell, and so I implemented the classic animal guessing game. However, I feel that there is probably a more elegant implementation than the one shown below, so any suggestions for improvement would be great. Cheers, Caleb \begin{code} data GuessTree = Answer String | GuessTreeQuestion {guessTreeQuestion :: String, guessTreeNo, guessTreeYes ::GuessTree} askQuestion :: String -> IO Bool askQuestion str = do putStrLn str response <- getLine return $ isYes response where isYes ('y':xs) = True isYes _ = False runTree :: GuessTree -> IO GuessTree runTree (Answer name) = do response <- askQuestion $ "Is it a " ++ name ++ "?" if response then do putStrLn "Ha!" return $ Answer name else do putStrLn "What is it?" animal <- getLine putStrLn $ "Enter a question to help distinguish between a " ++ name ++ " and a " ++ animal question <- getLine a <- askQuestion $ "Is the answer yes for " ++ animal ++ "?" (if a then id else flip) (\n y -> return $ GuessTreeQuestion {guessTreeQuestion = question, guessTreeNo = n, guessTreeYes = y}) (Answer animal) (Answer name) runTree GuessTreeQuestion {guessTreeQuestion = ques, guessTreeYes = yesTree, guessTreeNo = noTree} = do response <- askQuestion $ ques if response then do a <- runTree noTree return $ GuessTreeQuestion {guessTreeQuestion = ques, guessTreeNo = a, guessTreeYes = yesTree} else do a <- runTree yesTree return $ GuessTreeQuestion {guessTreeQuestion = ques, guessTreeNo = noTree, guessTreeYes = a} run :: GuessTree -> IO GuessTree run tree = do putStrLn "Think of an animal and press enter." getLine a <- runTree tree r <- askQuestion "Play again?" if r then run a else return a main = run $ Answer "bear" \end{code} Send instant messages to your online friends http://uk.messenger.yahoo.com

2 1

Lexically scoped type variables: new proposal
by Ben Rudiak-Gould 27 Oct '06

27 Oct '06

Hi, everyone. Long time no see. I have a specific proposal for scoped type variables, which is totally different from plans A and B, and which I'd like people to pick to pieces for me. (Especially you, Simon.) Type variable scoping in System F is simple: the type bindings are explicit and follow the same rules as the value bindings. Type variable scoping in Haskell is complicated only because the actual binding sites of the underlying System F type variables aren't visible. In particular, GHC's type signatures are never located at type variable binding sites; at best they're nearby. I'm convinced that the only way that type variable scoping will ever make sense is if scoped type variable bindings are written at their actual System F binding sites. That's what this proposal is about. We introduce "anonymous type aliases", with the syntax decl -> ... | 'type' tycon or perhaps more conveniently decl -> ... | 'type' tycon1 ... tyconN These are like ordinary type aliases, except that instead of referring to a type specified by the programmer, they refer to a type to be inferred by the compiler. They can appear in local bindings; for example, let { type N ; x :: [N] ; x = "hello" } in ... results in N being an alias for (i.e. bound to) Char in the body of the let, just as x is bound to "hello". And that's all. Well, that's not all, but I think the system above, as an extension of Haskell 98, has the power of traditional scoped type variables. Note that the problem of distinguishing between local type variables and nonlocal (scoped) type variables goes away in this proposal. The rule is the same as Haskell 98's: lowercase identifiers are local to a type expression, and uppercase identifiers scope like value bindings. Explicit foralls at the top level of a type are never necessary. Also note that in this proposal, the binding site of the type variable is decoupled from the specification of the type; the type signature that fixes N (by forcing unification with a rigid type) can be located anywhere in N's lexical scope. But that's not all! (I wish it were.) The problem with putting the anonymous type aliases in let/where decls is that System F type variables aren't bound there. (They could be, but I don't think they ever are in GHC.) Where they are bound is in lambda expressions, in function bindings (when the function is called), and in pattern matching on existential dcons. The let/where syntax does suffice for those cases, but it's awkward -- you end up having to write something like f x' y = let type N x :: [N] x = x' in ... It should be possible to bind type aliases everywhere that System F type variables can be bound, for which I propose the following syntax: f (type N) (x::[N]) y = ... and analogously \(type N) (x::[N]) y -> ... case e of D (type N) (x::[N]) y -> ... The parentheses around (type N) are mandatory. This syntax is sensible inasmuch as functions really do take type arguments and dcons really do have type fields, and we're simply writing them explicitly in the place where they've always been. This syntax also harmonizes fairly well with the existing type alias syntax, which can kinda sorta be seen as a pattern binding in this picture. The type variables thus introduced have the same scope as pattern variables, except that they also scope over the pattern type signatures in subsequent arguments or dcon fields. And that's all, for old-style scoped type variables. I realize that capitalized type variables might take some getting used to, but I really feel like this approach, or something like it, is much easier to understand and a significantly better candidate for standardization than what we've got now. It's always clear which variables are scoped and which aren't, and the scoping rules are exactly what you'd naively expect them to be. There are no difficult choices to make in the design (except for syntax; beware of Wadler's Law). Things that worry me: * Do constraint (dictionary) parameters threaten this proposal? They aren't explicit either, and so can't be given type signatures for the purpose of fixing a scoped tyvar. Fortunately in this proposal you needn't identify the meaning of a tyvar at its binding spot, and my intuition is that, if the scoped tyvar is useful at all, there will always be somewhere in its scope where its meaning can be disambiguated by a type signature. But I'm not sure. * Something else that's slipped my mind, but I want to post this before going to bed. * What about the GHC 6.6 changes? See below. I don't know how to make this proposal compatible with GHC 6.6 because I don't understand yet how type inference works with GADTs and impredicativity. My best guess is that the correct change is to require that an anonymous type variable only alias a rigid System F type variable [introduced in the same scope], where I'm not sure whether the part in brackets is necessary. This change has the same disadvantages in my proposal as in the existing GHC implementation: you can no longer write things like "type N ; f (x::N) (y::N) = ..." to enforce monomorphic type equality, or "type N ; x :: [N]" to get partial type signatures. I have an idea for how we might get the best of both worlds: anonymous types bound in let/while declarations could be flexible (subject to unification), while anonymous types bound in argument or field lists could refer to rigid type variables actually bound there. I'm not sure how much sense this idea makes because, as I said, I don't grok the reason for the GHC 6.6 changes yet. If people are confused by any aspect of the proposal, give me GHC 6.4 or 6.6 examples and I will either translate them into my proposed syntax, or fail to do so and thereby learn something interesting. And that's really all. Comments solicited. -- Ben

1 0

Or-Patterns
by Lajos Nagy 26 Oct '06

26 Oct '06

Whatever happened to the idea of Or-Patterns? http://www.haskell.org/pipermail/glasgow-haskell-users/2000-December/001535… I find them more than occasionally useful :) Is there some theoretical difficulty or is it just that nobody had the time/will to implement it? Regards, Lajos Nagy

1 0

Monad transformer question
by Cyril Schmidt 26 Oct '06

26 Oct '06

Working on a Monte-Carlo simulation where I have to calculate the values of a certain function on the given set of inputs, I noticed that some of the input variables change for every iteration, while others do not. To give a simple example, let's suppose I have a function f a1 a2 p = a1*a2 + p and I have to get its values for [ (a1,a2,p) | a1 <- [0.1,0.2], a2 <- [0.1,0.2], p <- [0..9] ] For efficiency, I want to pre-calculate (a1*a2) for each pair of a1 and a2, and then calculate f for each p. (The real function is far more complicated, but the idea is the same: pre-calculate all that depends on seldom-changing variables, and then run the rest of the iterations using the pre-calculated value). I built my function f as a Reader monad because my real f has many input parameters, so it is handy to have them packed in the Reader's environment. There are two Readers, in fact: the first environment contains the seldom- -changing variables, the second contains the variable that changes often. My code looked as follows. >{-# OPTIONS -fno-monomorphism-restriction #-} >module Main where >import Control.Monad.Reader The variable that changes most often: >data Inner = Inner { p1 :: Double } The variables that change seldom >data Outer = Outer { a1 :: Double, > a2 :: Double } Function precalc pre-calculates (a1*a2) >precalc = do > a1 <- asks a1 > a2 <- asks a2 > let r = {-# SCC "r" #-} a1*a2 > return r Function f in monadic form: >f :: Reader Outer (Reader Inner Double) >f = do > r <- precalc > return $ do { p1 <- asks p1 > ; let s = {-# SCC "s" #-} r+p1 > ; return s } Function runf runs f over all values of p: >runf (a1,a2) = do > let reader = runReader f $ Outer a1 a2 > results = map (runReader reader) [ Inner { p1 = x } | x <- [0..9] ] > putStrLn $ "a1 = "++show a1++", a2= "++show a2++", results = " > ++show results The main function >main = mapM_ runf [(a1,a2) | a1 <- [0.1,0.2], a2 <- [0.1,0.2]] This all works fine; the profiler shows that the (a1*a2) calculation is performed exactly 4 times, while addition, just as expected, 40 times. I noticed that f f :: Reader Outer (Reader Inner Double) can be implemented using monad transformer: f' :: ReaderT Outer (Reader Inner) Double The only difference in the implementation is that f' uses lift instead of return: >f' :: ReaderT Outer (Reader Inner) Double >f' = do > r <- precalc > lift $ do { p1 <- asks p1 > ; let s = {-# SCC "s" #-} r+p1 > ; return s } > >runf' (a1,a2) = do > let reader = runReaderT f' $ Outer a1 a2 > results = map (runReader reader) [ Inner { p1 = x } | x <- [0..9] ] > putStrLn $ "a1 = "++show a1++", a2= "++show a2++", results = " > ++show results However similar they look, f and f' have very different behaviour (their results are the same, of course). When I use runf' instead of runf, the profiler shows that precalc is invoked 40 times, which means that all the benefits of pre-calculating (a1*a2) are gone. (In the real application, I pre-calculate a much more complicated and expensive expression, that's why it matters). I am curious why this happens. As far as I can see, the lift function of ReaderT is the same as return of Reader, and the >>= in Reader and ReaderT are pretty similar to each other, so why is the behaviour different? This is a question of a purely theoretical significance for me; it does not hinder my work in any way. Still, I would greatly appreciate any ideas. By the way, I am using GHC 6.4.2 on Windows. Kind regards, Cyril

3 2

package mounting
by Frederik Eaton 26 Oct '06

26 Oct '06

Hi lists, I recently read Simon Peyton Jones' proposal: http://hackage.haskell.org/trac/ghc/wiki/GhcPackages and disagreed with some of the design decisions. (To be fair, the aspects I disagree with are shared with most or all of the other proposals) So I've put an alternative proposal here: http://hackage.haskell.org/trac/ghc/wiki/PackageMounting Discussion is welcome (but only on the libraries@ list, please). Hopefully we can weigh the benefits of each proposal, and reach an agreement and write up a more formal specification within the next few months or so provided that people decide that this is an extension we want to implement. Cheers, Frederik P.S. (I'm sorry that I missed Sven's earlier package mounting thread in July. But I hope the above article covers what my response would have been) -- http://ofb.net/~frederik/

1 0

Re: [Haskell] Monad transformer question
by Cyril Schmidt 25 Oct '06

25 Oct '06

Lajos, Point taken, thanks. My question, though, is not as much about how I speed up my program, as it is about the behaviour of the ReaderT monad transformer. There is something I do not understand about it, namely, why does such a small change in the code change the behaviour so much. Regards, Cyril > Based on what you wrote, I'm not sure that monads are the right answer > in this situation. It seems like to me that simple memoization of > function > values would yield a purely functional but equally efficient solution. > > A typical way to memoize the fibonacci function: > > fib = ((map fib' [0 ..]) !!) > where > fib' 0 = 0 > fib' 1 = 1 > fib' n = fib (n - 1) + fib (n - 2) > > (It only gives you a speed up if you compile with -O2 though.) > > Regards, > > Lajos Nagy

1 0

Compilation of big, computed tables
by Stefan Karrmann 24 Oct '06

24 Oct '06

Dear all, can ghc compile huge tables into efficient code if they are constant at compile time? Two examples may clearify the question: big1 :: UArray Int Char big1 = array (0,1000) $! map (\i -> (i,toEnum i)) [0..1000] big2 = sum [0..10000]::Int -- == 50005000 == n*(n+1)/2 where n = 10000 Both values are constant at compile time. As they are given by pure functions, the compiler could evaluate them and write the *result* into the object file 'foo.o'. This would save code size and run time. I peeked into 'foo.hc' but I didn't found 0x2fb0408 nor an array {0, 1, 2, 3, ..., 1000} or similar things. The function in big2 should show that the computation of the value could be very time consuming. If the compiler does not compute it, the source file could be generated by a helper program (or template Haskell?). The function in big1 should show that the conversion of the data into an array could be run-time, code-size and heap-size consuming. (You need the list (maybe explicitly - think of 1000 fixed pseudo-random numbers) and convert it into an array.) If the compiler generates the unboxed array directly it could be rather efficient. PS: I compiled with: ghc6 -c -O2 -keep-tmp-files -keep-hc-files foo.hs Regards, -- Stefan Karrmann

9 12

Haskell Weekly News: October 24, 2006
by dons＠cse.unsw.edu.au 24 Oct '06

24 Oct '06

--------------------------------------------------------------------------- Haskell Weekly News http://haskell.org/haskellwiki/HWN Issue 46 - October 24, 2006 --------------------------------------------------------------------------- Welcome to issue 46 of HWN, a weekly newsletter covering developments in the Haskell community. Announcements * MissingH 0.16.0. John Goerzen [1]announced that the latest version of MissingH is now available. MissingH is a suite of 'missing' library functions. New features include: render numbers as binary units, a progress tracker, turn QuickCheck tests into HUnit tests, and GHC 6.6 support. 1. http://article.gmane.org/gmane.comp.lang.haskell.general/14400 * SMP parallel Pugs on GHC. Audrey Tang [2]announced that parallel support, on top of GHC's new SMP runtime system, has been added to Pugs, the standard bearer [3]Perl6 implementation. 2. http://thread.gmane.org/gmane.comp.lang.haskell.general/14402/focus=14402 3. http://pugs.blogs.com/pugs/2006/10/smp_paralleliza.html * YAHT is now a part of the wikibook. Eric Kow [4]announced that the famous 'Yet Another Haskell Tutorial' has been imported into [5]the Haskell wikibook. Let the great Haskell Remix begin! 4. http://koweycode.blogspot.com/2006/10/yaht-badly-imported.html 5. http://en.wikibooks.org/wiki/Haskell Haskell' This section covers the [6]Haskell' standardisation process. * [7]Pattern guards * [8]Standard syntax for preconditions, postconditions, and invariants * [9]Indentation of If-Then-Else * [10]Module imports anywhere 6. http://hackage.haskell.org/trac/haskell-prime 7. http://thread.gmane.org/gmane.comp.lang.haskell.prime/1750/focus=1750 8. http://thread.gmane.org/gmane.comp.lang.haskell.prime/1773/focus=1773 9. http://thread.gmane.org/gmane.comp.lang.haskell.prime/1763/focus=1763 10. http://thread.gmane.org/gmane.comp.lang.haskell.prime/1764/focus=1764 Discussion * Ruby puzzles. Jim Burton [11]mentioned that he was working on the [12]Ruby quiz puzzles in Haskell -- an interesting exercise. 11. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/16056/focus=16056 12. http://www.rubyquiz.com/ * DeepSeq and parallel strategies. Chad Scherrer [13]started a bit of a discussion about the connection between the deepSeq function, and Control.Parallel.Strategies.rnf 13. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/16047/focus=16047 * Type level functions. Oleg Kiselyov [14]described how to use type level programming to create a type of constrained lists. 14. http://article.gmane.org/gmane.comp.lang.haskell.cafe/15978 * Extending the core libraries. Josef Svenningsson [15]started a largish thread on adding a concat.intersperse function to the base library, leading to an interesting discussion on whether the time has come for an formal process for extending core libraries. 15. http://thread.gmane.org/gmane.comp.lang.haskell.libraries/5280/focus=5280 * data Void. Conor McBride [16]proposed adding the type with no inhabitants other than _|_ to the core libraries. 16. http://thread.gmane.org/gmane.comp.lang.haskell.libraries/5321/focus=5321 Blog noise [17]Haskell news from the blogosphere. * [18]Optimus prime is actually dead, or, monadic transformers * [19]Haskell, PDF and penrose tilings * [20]Not everyone can dine at the Beverly Hills Social Club of Programming Languages * [21]Would you like a side of referential transparency with your order.. * [22]John Baez on lambda calculus and games * [23]Monads: a field guide * [24]Catch+YHC beats GHC 17. http://planet.haskell.org/ 18. http://brokenhut.livejournal.com/172054.html 19. http://www.alpheccar.org/en/posts/show/57 20. http://sequence.complete.org/node/215 21. http://weblog.raganwald.com/2006/10/would-you-like-side-of-referential.html 22. http://wadler.blogspot.com/2006/10/john-baez-on-lambda-calculus-and-games.h… 23. http://sigfpe.blogspot.com/2006/10/monads-field-guide.html 24. http://neilmitchell.blogspot.com/2006/10/30-faster-than-ghc.html About the Haskell Weekly News Each week, new editions are posted to [25]the Haskell mailing list as well as to [26]the Haskell Sequence and [27]Planet Haskell. [28]RSS is also available, and headlines appear on [29]haskell.org. The Haskell Weekly News is also [30]available in Spanish translation. To help create new editions of this newsletter, please see the [31]contributing information. Send stories to dons at cse.unsw.edu.au. The darcs repository is available at darcs get http://www.cse.unsw.edu.au/~dons/code/hwn 25. http://www.haskell.org/mailman/listinfo/haskell 26. http://sequence.complete.org/ 27. http://planet.haskell.org/ 28. http://sequence.complete.org/node/feed 29. http://haskell.org/ 30. http://haskell.org/haskellwiki/HWN/es 31. http://haskell.org/haskellwiki/HWN

1 0