- Haskell-Cafe - Haskell.org

Stupid newbie question
by Brian Hurt 06 Jan '07

06 Jan '07

My apologies for wasting bandwidth on what I'm sure is a stupid newbie question. Given: -- Reimplementing the wheel here, I know data Option a = Some a | Empty deriving (Eq,Ord,Show,Read) nth 0 (x:xs) = Some x nth i (x:xs) = if i < 0 then Empty else nth (i-1) xs nth i [] = Empty That: nth 1000000 [1..10000000] returns the right answer, while: nth 1000000 [1..] blows stack. Furthermore, given: makelist i = i : (makelist (i-1)) Why is it that: nth 1000000 (makelist 1) blows stack? What are the rules for being tail recursive in Haskell? I'm an Ocaml programmer, so I'm familiar with this problem, I just don't see the solution. Some help would be appreciated. Thanks in advance, Brian

8 14

MVar style question
by Chad Scherrer 05 Jan '07

05 Jan '07

When using MVars, is there a reason to prefer using MVar (a,b) over (MVar a, MVar b), or vice versa? I'm not sure if this is really a question of style, or if there are practial implications I'm missing one way or another. Thanks! -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

4 5

Composing functions with runST
by Yitzchak Gale 05 Jan '07

05 Jan '07

Can anyone explain the following behavior (GHCi 6.6): Prelude Control.Monad.ST> runST (return 42) 42 Prelude Control.Monad.ST> (runST . return) 42 <interactive>:1:9: Couldn't match expected type `forall s. ST s a' against inferred type `m a1' In the second argument of `(.)', namely `return' In the expression: (runST . return) 42 In the definition of `it': it = (runST . return) 42 Thanks, Yitz

16 32

RE: [Haskell] Re: state of HaXml?
by Simon Marlow 05 Jan '07

05 Jan '07

[ moving to haskell-café... ] Norman Ramsey wrote: > > There seems to be a misunderstanding here: readFile in > itself is not the > > solution. readFile is defined thus: > > > > readFile name = openFile name ReadMode >>= hGetContents > > > and the original code was this: > > > > load fn = do handle <- IO.openFile fn IO.ReadMode > > contents <- IO.hGetContents handle > > IO.hClose handle > > return $ XP.xmlParse fn contents > > > Sure, you can replace the openFile/hGetContents pair by > readFile, but the > > real problem is the presence of the hClose. Removing that > will solve your > > problem (but note that you now have no control over when > the file is > > actually closed). > > Can I just leave it hanging and rely on the garbage collector to > close it in the fullness of time? Yes. The problem I was alluding to arises when you have many lazilly-closed files, and you run into the system's open file limit because the runtime doesn't close them eagerly enough. To be sure of closing the file at the right time, you need to force the entire file to be read (e.g. by forcing the result of the parse), then close the handle. > Because of laziness, I believe there's no point in my writing the > following: > > > load fn = do handle <- IO.openFile fn IO.ReadMode > > contents <- IO.hGetContents handle > > let xml = XP.xmlParse fn contents > > IO.hClose handle > > return xml > > Is that correct? Yes. Cheers, Simon

1 0

Re: [Haskell] Re: state of HaXml?
by dons＠cse.unsw.edu.au 05 Jan '07

05 Jan '07

nr: > > Sure, you can replace the openFile/hGetContents pair by readFile, but the > > real problem is the presence of the hClose. Removing that will solve your > > problem (but note that you now have no control over when the file is > > actually closed). > > Can I just leave it hanging and rely on the garbage collector to close > it in the fullness of time? Yeah, once your program has demanded the entire file, it'll close the Handle. > Because of laziness, I believe there's no point in my writing the > following: > > > load fn = do handle <- IO.openFile fn IO.ReadMode > > contents <- IO.hGetContents handle > > let xml = XP.xmlParse fn contents > > IO.hClose handle > > return xml > > Is that correct? Yep. Its not neccessary in the usual programming cases to explicitly close the handle. IF you start really hammering the filesystem do you start to care about ensuring files are closed (so you don't hang on to too many FDs). Or if you start mutating files on disk. For these situations there are strict readFiles, or Data.ByteString.readFile -- Don

1 0

Haskell Weekly News: January 02, 2007
by dons＠cse.unsw.edu.au 04 Jan '07

04 Jan '07

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20070102 Issue 55 - January 02, 2007 --------------------------------------------------------------------------- Welcome to issue 55 of HWN, a weekly newsletter covering developments in the Haskell community. This week brings a new release of vty and HsColour, and some interesting discussion over the holiday break. Announcements hscolour-1.6. Malcolm Wallace [1]announced HsColour, a popular syntax-highlighter for Haskell code. It can generate ANSI terminal colour codes, HTML, and CSS, and can insert hyperlink anchors for function definitions (useful in conjunction with [2]Haddock). [3]HsColour-1.6 is now available. The major addition is a new LaTeX output mode. 1. http://article.gmane.org/gmane.comp.lang.haskell.general/14677 2. http://haskell.org/haddock 3. http://www.cs.york.ac.uk/fp/darcs/hscolour Dimensional: Statically checked physical dimensions. Bj�rn Buckwalter [4]announced version 0.1 of [5]Dimensional, a module for statically checked physical dimensions. The module facilitates calculations with physical quantities while statically preventing e.g. addition of quantities with differing physical dimensions. 4. http://article.gmane.org/gmane.comp.lang.haskell.general/14691 5. http://code.google.com/p/dimensional/ vty 2.0. Stefan O'Rear [6]announced a new major version of [7]vty. Differences from 1.0 include: vty now uses a record type for attributes, instead of bitfields in an Int; vty now supports setting background colors; you can now explicitly specify 'default' colors; vty now supports Unicode characters on output, automatically setting and resetting UTF-8 mode. 6. http://article.gmane.org/gmane.comp.lang.haskell.general/14703 7. http://members.cox.net/stefanor/vty 'Lambda Revolution' tshirts. Paul Johnson [8]announced the creation of a new Haskell tshirt, on the theme of 'The Lambda Revolution'. Tshirts are available from [9]CafePress, and the designs are freely available. 8. http://article.gmane.org/gmane.comp.lang.haskell.cafe/17916 9. http://www.cafepress.com/l_revolution Discussion Beautiful concurrency. Simon Peyton-Jones [10]mentioned that he's been writing a chapter on concurrency and transactional memory for a new book, 'Beautiful code'. [11]A first draft is available and Simon welcomes constructive suggestions for improvement. The book is aimed at a general audience of programmers, not Haskell geeks, so tries to explain everything necessary. If you are not a Haskell expert, your input would be particularly valuable. 10. http://article.gmane.org/gmane.comp.lang.haskell.general/14681 11. http://haskell.org/haskellwiki/Talk:SantaClausProblem Limits to implicit parallelism in functional applications. John DeTreville [12]announced a short paper about how much implicit parallelism there might be in ordinary functional applications. 12. http://article.gmane.org/gmane.comp.lang.haskell.general/14699 Inlining higher order functions. Norman Ramsey [13]asked about fine grained control for inlining in higher order functions. 13. http://article.gmane.org/gmane.comp.lang.haskell.glasgow.user/11467 Red-black trees as a nested datatype. Jim Apple [14]described how to implement red-black trees as a nested datatype. 14. http://article.gmane.org/gmane.comp.lang.haskell.cafe/17957 SYB for XML: deserialization and collections. Alexander Jacobson [15]asked about approaches to simplifying boilerplate in HAppS associated with XML serialization and state deserialization. 15. http://article.gmane.org/gmane.comp.lang.haskell.cafe/17922 Flattening a lisp-style tree. pphetra [16]asked about flattening heterogeneous lists (or trees) in Haskell. 16. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/17976/focus=17976 Jobs Functional programming at Jane Street Capital. Yaron Minsky [17]announced that [18]Jane Street Capital is again looking to hire some top-notch functional programmers. Of particular note is that Jane Street Europe Ltd. now has an office in London, and we are particularly interested in hiring someone for that office with strong systems administration skills in addition to experience with functional programming languages. The ideal candidate has: a commitment to the practical, experience with functional programming languages (such as Haskell). Applicants should also have experience with UNIX and a deep understanding of computers and technology and a strong mathematical background. 17. http://article.gmane.org/gmane.comp.lang.haskell.general/14683 18. http://www.janestcapital.com/tech.html Blog noise [19]Haskell news from the blogosphere. * [20]Secret Santas in Haskell III: Lather, Rinse, Repeat 1 * [21]More Haskell in Java 7 or 8? * [22]Generalized vs. dynamic interfaces * [23]Type classes in Java * [24]Static vs dynamic typing: do what thou wilt * [25]Hoogle 4 progress * [26]Hoogle Progress, HsMan features * [27]The York Haskell Compiler: 1000 patches! * [28]Evaluating cellular automata is co-monadic * [29]Tying Knots Generically * [30]Rails -> Ruby -> Haskell * [31]A Sermon on Programming Languages * [32]Thoughtful revision control * [33]readFile' * [34]Code unraveller * [35]The Haskell Meta Tutorial * [36]Monads * [37]My Haskell Experience * [38]Communities * [39]Darcs: The source code management system of the future? * [40]On strong type systems * [41]On Programming Languages and Productivity 19. http://planet.haskell.org/ 20. http://mult.ifario.us/articles/2006/12/22/secret-santas-in-haskell-iii-coll… 21. http://blogs.msdn.com/ralflammel/archive/2006/12/21/more-haskell-in-java-7-… 22. http://blogs.msdn.com/ralflammel/archive/2006/12/23/generalized-vs-dynamic-… 23. http://syntaxfree.wordpress.com/2006/12/23/et-tu-brute/ 24. http://syntaxfree.wordpress.com/2006/12/24/static-vs-dynamic-typing-do-what… 25. http://neilmitchell.blogspot.com/2006/12/hoogle-4-progress.html 26. http://neilmitchell.blogspot.com/2006/12/hoogle-progress-hsman-features.html 27. http://yhc06.blogspot.com/2006/12/1000-patches.html 28. http://sigfpe.blogspot.com/2006/12/evaluating-cellular-automata-is.html 29. http://sigfpe.blogspot.com/2006/12/tying-knots-generically.html 30. http://rubynations.wordpress.com/2006/12/28/evolutionrails-ruby-haskell/ 31. http://www.dailyspeculations.com/wordpress/?p=101 32. http://koweycode.blogspot.com/2006/12/distributed-chiming-in.html 33. http://koweynlg.blogspot.com/2006/12/meh.html 34. http://koweycode.blogspot.com/2006/12/unraveller.html 35. http://koweycode.blogspot.com/2006/12/haskell-metatutorial.html 36. http://hierodule.livejournal.com/69052.html 37. http://kawagner.blogspot.com/2006/12/my-haskell-experience.html 38. http://gravityboy.livejournal.com/31930.html 39. http://www.iovene.com/content/view/93/1/ 40. http://blog.tmorris.net/strong-type-systems/ 41. http://www.neilmix.com/2007/01/01/on-programming-languages-and-productivity/ Quotes of the Week * chessguy: [in regards to #haskell] man, it's amazing the difference between what happens when someone asks for help here, and what happens when they ask for help in another language channel * cjeris: It's amazing what some languages do to make thinking impossible, seemingly justified by the assumption that no one thinks anyway, so it's more important to make non-thinking programming as easy as possible. * edwinb: I've just walked past a poster advertising a gig by a band called 'The Awkward Squad'. I assume this means they provide output, play concurrently, and people take exception to them. * kfish: Apparently @pl also doubles as the command for producing an unintelligible flip-stream * Binkley: [Monads as clothes] using unsafePerformIO is kind of like going naked in public, might be safe in some contexts, but you really don't want to know what happens if you do it in a really bad one * quazimodo: I know why you guys are so ready to deal with me and put up with noob questions ... you program so fast compared to other language users that you have time to mess around? * iulus: IO, IO, it's off to bind we go ... * dons: all your imperative are belong to us * Logan Capaldo: I like constructing things with type errors. It lets me read the error and try and figure out what I'm really trying to do * glguy: In true Haskell form, after I realized what I was actually doing... all my functions melted down to about 2 lines each * jcreigh: I've found learning Haskell makes me feel vastly inferior to Haskell coders. ('Oh,', they say, 'That's just a fold over the hyper-monad fluxbox list. Here's the one-line replacement for your entire program.') * Saizan: [New Year's Fun] Yesterday I was so drunk I was trying to typecheck the people at the party... 'What's your monad!?' Code Watch Wed Dec 27 17:03:48 PST 2006. Manuel M T Chakravarty. [42]Parse and desugar equational constraints. With -findexed-types, equational constraints can appear in contexts wherever class predicates are allowed. The two argument types need to be boxed and rank 0. 42. http://article.gmane.org/gmane.comp.lang.haskell.cvs.ghc/18551 About the Haskell Weekly News Each week, new editions are posted to [43]the Haskell mailing list as well as to [44]the Haskell Sequence and [45]Planet Haskell. [46]RSS is also available, and headlines appear on [47]haskell.org. Headlines are available as [48]PDF. The Haskell Weekly News is also [49]available in Spanish translation. To help create new editions of this newsletter, please see the [50]contributing information. Send stories to dons at cse.unsw.edu.au. The darcs repository is available at darcs get [51]http://www.cse.unsw.edu.au/~dons/code/hwn 43. http://www.haskell.org/mailman/listinfo/haskell 44. http://sequence.complete.org/ 45. http://planet.haskell.org/ 46. http://sequence.complete.org/node/feed 47. http://haskell.org/ 48. http://www.cse.unsw.edu.au/~dons/code/hwn/archives/20070102.pdf 49. http://haskell.org/haskellwiki/HWN/es 50. http://haskell.org/haskellwiki/HWN 51. http://www.cse.unsw.edu.au/~dons/code/hwn

3 2

Arrays performance
by paolo.veronelli＠gmail.com 04 Jan '07

04 Jan '07

Good year everyone. I'm timing the following script.I'm not expert to evaluate th O'ness of this code, I hope someone can do it. The program clusters n integers in m buckets based on their distance. Anyway I thing should be linear.So I timed som executions changing the first arg. First argument n is the number of integers to be clustered.Their are choosen randomly between 0 and 100. Second argument m is the number of buckets.For them I choose a value choosen like before. In the timings second argument is always 10. Points Time (ms) 100 40 200 93 400 269 800 831 1600 3063 3200 12693 6400 54708 I'd like to know if the algorithm is the cause for this timings (it's not linear) or if I need to use other kinds of Arrays Thanks Paolino ---------------------------------------------------------------- import Data.Maybe import Data.List import Data.Array.Diff import System.Environment import Control.Monad.State import Control.Arrow import Random inc l i = l // [(i,l!i + 1)] switch l i = l // [(i,not (l!i))] constArray n v = listArray (0,n-1) (repeat v) data CState = CState {clusters :: [(Int,Int)],remi :: Int,colsHeap ::DiffArray Int Int ,rowsFlag :: DiffArray Int Bool} devil [] _ = return () devil (l@(row,col):ls) d = do s@(CState cs r hs fs) <- get let ns = s { clusters = (l:cs), rowsFlag = switch fs row, colsHeap = inc hs col } update | c < d = put ns | (c == d) && (r > 0) = put ns { remi = r - 1 } | otherwise = return () where c = hs ! col when (not (fs ! row)) update devil ls d comp f g x y = (f x) `g` (f y) swap = snd &&& fst collapse = (head &&& unzip) >>> (fst *** snd) mcluster :: [(Int,Int)] -> [(Int,[Int])] mcluster ls = let (lr,lc) = (f *** f) (unzip ls) where f = length.nub -- coo space width (k,r) = divMod lr lc CState cs _ _ _ = execState (devil ls k) CState{clusters = [],remi = r,colsHeap = constArray lc 0,rowsFlag = constArray lr False } in map collapse . groupBy (comp fst (==)) . sort . map swap $ cs coupage ls = zip [0..] ls delta fxy xs ys = [(abs(x-y),(n,m))|(n,x) <- coupage xs, (m,y) <- coupage ys] decoupage ls n = fromJust $ lookup n (coupage ls) test xs ys = let d = snd.unzip.sort $ delta (\x y -> abs (x -y)) xs ys in map (decoupage ys *** map (decoupage xs)) (mcluster d) -- call it with 2 args, the number ov values and the number of clusters -- <prog> 101 10 will cluster 101 values in 10 clusters main = do args <- getArgs gen <- getStdGen let [n,m] = map read args let (ps,bs) = splitAt n (take (m + n) (randomRs (0,100) gen)) print $ test ps bs

4 4

GADT proofs of FunDeps?
by Roberto Zunino 04 Jan '07

04 Jan '07

I am investigating mixing FunDeps with the type equality GADT data Teq a b where Teq :: Teq a a Basically, I would like to write something like proof :: (C a b1, C a b2) => Teq b1 b2 proof = unsafeCoerce# Teq provided the FunDep class C a b | a -> b Is this safe? Any caveat? Regards, Roberto Zunino.

1 0

darcs repo for yampa + gadt
by Joel Reymont 04 Jan '07

04 Jan '07

Folks, I have a version of Yampa with Henrik Nilsson's GADT optimizations that I cleaned up for ghc 6.6 and cabalized. Would it be possible to set it up at darcs.haskell.org and if so how should I go about it? Thanks, Joel -- http://wagerlabs.com/

2 1

State separation/combination pattern question
by Reto Kramer 03 Jan '07

03 Jan '07

I'm looking for a pattern to use for "state separation" in my application. I need to write two "stateful libraries". One is a partitioned in- memory store, the other a disk based store with an in-memory cache fronting it. Both store modules need the IO and State monad. My aim is to write the libraries independently from one another in such a way that they are not aware of the context they will be used in. Both stores are called from a breadth first search loop. The example below extracts the essence of my current approach. foo is function in one of the store modules, bar is from the other type of store. Both manipulate their type of state (StateA, StateB). They extract their slice of the "global" application level state (AppStateRec). What I don't like is that the code in foo and bar know about the AppStateRec and that they need to get the "a", or "b" slot respectively. The store modules should not have such coupling with their client code. I've tried to thread the two states (StateA and StateB) using a chain of StateT ... StateT ..., but couldn't really make that work. It seems rather arbitrary in this case which state to make the inner/ outer one and depending on this ordering the "lifts" have to go with one or the other set of store calls. What I'm really looking for is not so much the chaining of StateT compositions, but rather the isolation of StateA from StateB while they both flow from the search loop into the respective library calls (foo, bar) transparently to the application programmer. I'm hoping there's a way to have the loop be in a State monad whose content is the sum of the two states that are needed for the foo and bar call made to the stores from inside the loop. The calls sites for foo and bar should then extract the right component of the global state and thread only that state through into the modules. Sounds like magic, but how close can I get? I've been unable to find a pattern on the WIKI or the web that refers to this type of "state composition" (or I may not have recognized the match). I trust many of you have run into this and there's an obvious and straight forward best way to address this type of state handling. Thanks, - Reto -------------------------- -- ghci -fglasgow-exts ... -- type StateA = [Integer] type StateB = [Integer] data AppStateRec = AppStateRec { a :: StateA, b :: StateB } deriving Show foo :: MonadState AppStateRec m => m () foo = do st <- get put $ st { a = 1:(a st) } bar :: MonadState AppStateRec m => m () bar = do st <- get put $ st { b = 2:(b st) } type Eval a = StateT AppStateRec Identity a exec :: Eval () exec = do foo bar foo foo bar go = runIdentity $ runStateT exec AppStateRec { a = [], b = [] } Prints: ((),AppStateRec {a = [1,1,1], b = [2,2]})

5 4