- Haskell-Cafe - Haskell.org

Naturality condition for inits
by R J 08 Mar '09

08 Mar '09

Here's another Bird problem that's stymied me: The function "inits" computes the list of initial segments of a list; its type is inits :: [a] -> [[a]]. What is the appropriate naturality condition for "inits"? The only discussion in the text concerning naturality conditions concerns map, where the naturality conditions are stated in what seem to be quasi-commutativity laws over the composition operator, as follows: f . head = head . map f, where f is strict (i.e., f _|_ = _|_) map f . tail = tail . map f map f (xs ++ ys) = map f xs ++ map f ys map f . reverse = reverse . map f map f . concat = concat . map (map f) I believe that none of the following naturality conditions, extrapolated from those above, hold: a. head . inits = inits [head] b. tail . inits = inits . tail c. reverse . inits = inits . reverse d. concat . inits = inits . concat In case the definition of "inits" is relevant, my definition is: inits :: [a] -> [[a]] inits xs = [take n xs | n <- seglengths] where seglengths = [0..length xs] Thanks. _________________________________________________________________ Windows Live™: Life without walls. http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1a_explore_032009

4 3

Haskell Weekly News: Issue 108 - March 7, 2009
by Brent Yorgey 07 Mar '09

07 Mar '09

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20090307 Issue 108 - March 07, 2009 --------------------------------------------------------------------------- Welcome to issue 108 of HWN, a newsletter covering developments in the [1]Haskell community. The ICFP programming contest will be held from 26-29th June! It's not too early to start thinking about putting a team together. Announcements tar 0.3.0.0. Duncan Coutts [2]announceda major new release of the [3]tar package for handling ".tar" archive files. This release has a completely new and much improved API. storable 0.1 -- Storable type class for variable-sized data. Tomáš Janoušek [4]announced the first release of the [5]storable library, which fills the gap between Foreign.Storable and Data.Binary by adding support for marshalling (finite) values of variable-sized data types, like lists or trees, while preserving the performance and memory efficiency one expects from the Storable class. It also provides a (monadic) syntactic sugar that takes care of alignment restrictions by itself and makes instance deriving easy. CFP: Submit a talk proposal to CUFP. Kathleen Fisher [6]requested talk proposals for [7]CUFP. The Industrial Haskell Group. Duncan Coutts [8]announced the creation of the [9]Industrial Haskell Group (IHG). The IHG is an organisation to support the needs of commercial users of the Haskell programming language. Currently, the main activity of the IHG is a collaborative development scheme, in which multiple companies fund work on the Haskell development platform to their mutual benefit. The scheme has started with three partners of the IHG, including Galois and Amgen. pandoc 1.2. John MacFarlane [10]announced the release of [11]pandoc version 1.2. The most significant new feature is support for literate Haskell; you can now use pandoc directly on literate Haskell source files to produce syntax-highlighted HTML output. A Haskell binding for the Augeas API. Jude [12]announced a [13]Haskell FFI binding for the Augeas configuration editing API. Haskell Logo Voting will start soon!. Eelco Lempsink [14]announced that [15]voting for the new Haskell logo will begin on March 16! Everyone subscribed to haskell-cafe will receive a ballot; if you are not subscribed but would like to vote, email Eelco with the subject "haskell logo voting ballot request" and include a short, unique message. Happstack 0.2 Released. Matthew Elder [16]announced the [17]release of [18]Happstack 0.2. Extensible and Modular Generics for the Masses: emgm-0.3. Sean Leather [19]announced the third major release of [20]Extensible and Modular Generics for the Masses (EMGM), a library for generic programming in Haskell using type classes and a sum-of-products view. Deriving is now greatly improved, and there are several new functions, including case, everywhere, and everywhere'. major speed improvement: regex-tdfa reaches 1.0.0. ChrisK proudly [21]announced the version 1.0.0 release of [22]regex-tdfa. This is is not just a bug fix release; it is a serious improvement in the asymptotic running time of the library algorithms. Discussion Definitions of purity and Lazy IO. Oleg began a [23]discussion on lazy IO. Left fold enumerator - a real pearl overlooked?. Günther Schmidt began a [24]discussion of left-fold enumerators and their current status within the community. Jobs Looking for a co-founder for a startup using Haskell. Ed McCaffrey [25]is looking for a co-founder to work on a startup music project in Haskell. Email Ed for more information. Fully-funded doctoral studentships in dependently type programming at Oxford and Strathclyde. Jeremy Gibbons [26]announced two fully-funded doctoral student positions in dependently-typed programming at [27]Oxford and [28]Strathclyde. Blog noise [29]Haskell news from the [30]blogosphere. * Holumbus: [31]First release of Holumbus-MapReduce. * FP Lunch: [32]Breadth first labelling. * Sean Leather: [33]Experiments with EMGM: Emacs org files. * Galois, Inc: [34]Call for Proposals: CUFP 2009. * Matthew Elder: [35]Happstack 0.2 Released. * Yi: [36]Lazy and Incremental Parsing: the paper. * Xmonad: [37]xmonad as a multi-head sliding block puzzle. * Don Stewart (dons): [38]Playing with GHC's parallel runtime. * Bjorn Buckwalter: [39]Extended sessions with the Haskell Curl bindings. * Manuel M T Chakravarty: [40]Installing GtK2Hs on a Mac with the native GTK+ OS X Framework.. * Alex Mason: [41]If you need speed, don't talk to main!. * Luke Palmer: [42]New game: SpaceBattle. * Galois, Inc: [43]Galois Tech Talk: Specializing Generators for High-Performance Monte-Carlo Simulation in Haskell. * Bjorn Buckwalter: [44]Programmer Man. * Conrad Parker: [45]Random code: Pretty printing durations in Haskell. * The GHC Team: [46]New paper: Runtime Support for Multicore Haskell. * ganesh: [47]London Haskell Users Group. * Manuel M T Chakravarty: [48]This is the performance of a dot product of two vectors of 10.... * Sean Leather: [49]Template Haskell 2.3 or Cabal 1.2? EMGM can't have both!. * Tom Schrijvers: [50]Complete and Decidable Type Inference for GADTs. * Galois, Inc: [51]Trustworthy Voting Systems. * Well-Typed.Com: [52]The Industrial Haskell Group. * Sean Leather: [53]Incremental fold, a design pattern. * Darcs: [54]darcs weekly news #19. * FP Lunch: [55]Container eating. About the Haskell Weekly News New editions are posted to [56]the Haskell mailing list as well as to [57]the Haskell Sequence and [58]Planet Haskell. [59]RSS is also available, and headlines appear on [60]haskell.org. To help create new editions of this newsletter, please see the information on [61]how to contribute. Send stories to byorgey at cis dot upenn dot edu. The darcs repository is available at darcs get [62]http://code.haskell.org/~byorgey/code/hwn/ . References 1. http://haskell.org/ 2. http://www.haskell.org//pipermail/haskell-cafe/2009-March/056870.html 3. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/tar 4. http://article.gmane.org/gmane.comp.lang.haskell.general/16934 5. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/storable 6. http://article.gmane.org/gmane.comp.lang.haskell.general/16904 7. http://cufp.galois.com/2009/call.html 8. http://article.gmane.org/gmane.comp.lang.haskell.general/16903 9. http://industry.haskell.org/ 10. http://article.gmane.org/gmane.comp.lang.haskell.general/16899 11. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/pandoc 12. http://article.gmane.org/gmane.comp.lang.haskell.general/16897 13. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/augeas 14. http://article.gmane.org/gmane.comp.lang.haskell.cafe/54201 15. http://community.haskell.org/~eelco/poll.html 16. http://article.gmane.org/gmane.comp.lang.haskell.cafe/54144 17. http://blog.happstack.com/2009/03/04/happstack-02-released 18. http://blog.happstack.com/2009/03/04/happstack-02-released 19. http://article.gmane.org/gmane.comp.lang.haskell.cafe/54035 20. http://www.cs.uu.nl/wiki/GenericProgramming/EMGM 21. http://article.gmane.org/gmane.comp.lang.haskell.cafe/53943 22. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/regex%2Dtdfa 23. http://thread.gmane.org/gmane.comp.lang.haskell.general/16914 24. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/53873 25. http://article.gmane.org/gmane.comp.lang.haskell.cafe/54246 26. http://article.gmane.org/gmane.comp.lang.haskell.general/16927 27. http://web.comlab.ox.ac.uk/news/72-full.html 28. http://personal.cis.strath.ac.uk/~conor/phds/ 29. http://planet.haskell.org/ 30. http://haskell.org/haskellwiki/Blog_articles 31. http://holumbus.fh-wedel.de/blog/?p=17 32. http://sneezy.cs.nott.ac.uk/fplunch/weblog/?p=205 33. http://feedproxy.google.com/~r/splonderzoek/~3/6bxI33NIRMc/experiments-with… 34. http://www.galois.com/blog/2009/03/05/call-for-proposals-cufp-2009/ 35. http://blog.happstack.com/2009/03/04/happstack-02-released/ 36. http://yi-editor.blogspot.com/2009/03/lazy-and-incremental-parsing-paper.ht… 37. http://xmonad.wordpress.com/2009/03/04/xmonad-as-a-multi-head-sliding-block… 38. http://donsbot.wordpress.com/2009/03/04/playing-with-ghcs-parallel-runtime/ 39. http://flygdynamikern.blogspot.com/2009/03/extended-sessions-with-haskell-c… 40. http://justtesting.org/post/83333955 41. http://axman6.homeip.net/blog/2009/03/if-you-need-speed-dont-talk-to-main.h… 42. http://lukepalmer.wordpress.com/2009/03/04/new-game-spacebattle/ 43. http://www.galois.com/blog/2009/03/03/galois-tech-talk-specializing-generat… 44. http://flygdynamikern.blogspot.com/2009/02/programmer-man.html 45. http://blog.kfish.org/2009/03/random-code-pretty-printing-durations.html 46. http://ghcmutterings.wordpress.com/2009/03/03/new-paper-runtime-support-for… 47. http://www.londonhug.net/2009/03/03/80/ 48. http://justtesting.org/post/83014052 49. http://feedproxy.google.com/~r/splonderzoek/~3/WqqB1QrNZ_4/template-haskell… 50. http://tomschrijvers.blogspot.com/2009/03/complete-and-decidable-type-infer… 51. http://www.galois.com/blog/2009/03/02/trustworthy-voting-systems/ 52. http://blog.well-typed.com/2009/03/the-industrial-haskell-group/ 53. http://feedproxy.google.com/~r/splonderzoek/~3/tj_MkKqIlkQ/incremental-fold… 54. http://blog.darcs.net/2009/03/darcs-weekly-news-19.html 55. http://sneezy.cs.nott.ac.uk/fplunch/weblog/?p=201 56. http://www.haskell.org/mailman/listinfo/haskell 57. http://sequence.complete.org/ 58. http://planet.haskell.org/ 59. http://sequence.complete.org/node/feed 60. http://haskell.org/ 61. http://haskell.org/haskellwiki/HWN 62. http://code.haskell.org/~byorgey/code/hwn/

1 0

Converting list comprehensions to combinatory style
by R J 07 Mar '09

07 Mar '09

Can anyone help with this problem from Bird: a. Convert the following list comprehensions to combinatory style: i. [(x, y) | x <- [1..n], odd x, y <- [1..n]] ii. [(x, y) | x <- [1..n], y <- [1..n], odd x] b. Are they equal? c. Compare the costs of evaluating the two expressions. I gather that by combinatory style, he means the use of concat, map, and filter. While Bird provides the following conversion rules, he doesn't prove them, justify them, or even provide an example using them: R1. [ f x | x <- xs ] = map f xs R2. [ x | x <- xs, p x ] = filter p xs R3. [ e | Q, P ] = concat [[e | P] | Q] R4. [ e | x <- [d | P] ] = [e [x := d] | Q, P] Thanks. _________________________________________________________________ Windows Live™ Groups: Create an online spot for your favorite groups to meet. http://windowslive.com/online/groups?ocid=TXT_TAGLM_WL_groups_032009

2 1

do you have to use fix with forkio?
by Daryoush Mehrtash 07 Mar '09

07 Mar '09

In this chat server implementation http://www.haskell.org/haskellwiki/Implement_a_chat_server forkIO is used with fix as in: reader <- forkIO $ <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:.> fix $ <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:.> \loop -> do (nr', line) <- readChan chan' when (nr /= <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:/=> nr') $ <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:.> hPutStrLn hdl line loop Do you have to use fix? Or is there a way to write this with a "let"? -- Daryoush

8 11

Ambiguous type with PolymorphicComponents
by Maurício 07 Mar '09

07 Mar '09

Hi, When reading this code in ghci, I get an ambiguous type at last line: {-# LANGUAGE PolymorphicComponents #-} {-# LANGUAGE RankNTypes #-} import Graphics.UI.Gtk data Test = Test (forall w. WidgetClass w => w) toAction (Test w) = toWidget w It's interesting that if I replace 'Integral' for 'WidgetClass' and 'toInteger' for 'toWidget', I get no error messages, and I see no essencial diference between both classes and both functions. Do you know what am I missing? Thanks, Maurício

2 3

serializing large data structures, stack overflow
by friggin friggin 07 Mar '09

07 Mar '09

I'm playing around with Netflix, implementing a simple KNN-algorithm, I will later try SVD which seems to be the most successful approach. Using a database like Postgresqk is to slow so I want to serialize a datastructure containing the ratings. I'm not sure about the representation I will use just yet, if I should use multiple arrays or an Map/IntMap. However I tried Data.Binary and already for small sizes I get stack overflow when deserializing. The serializing works fine but when bringing it back it overflows. How can I solve this? This is just 2MB, I will eventually need soemthing like 2-500MB to store everything depending on what representatin I choose. module Serialize where import qualified Data.Binary as B import qualified Data.Binary.Put as P import qualified Data.Map as M import qualified Data.List as L genTest :: Int -> M.Map (Int,Int) Int genTest n = let movies = take n $ repeat 1 grades = take n $ repeat 4 in M.fromList $ ([1..n] `zip` movies) `zip` grades main = do let a = genTest 50000 B.encodeFile "C:/users/saftarn/desktop/bintest.txt" a print "Success" dec = B.decodeFile "C:/users/saftarn/desktop/bintest.txt" >>= \a -> return $ (a :: M.Map (Int,Int) Int)

3 2

Re: [Haskell-cafe] serializing large data structures, stack overflow
by Don Stewart 07 Mar '09

07 Mar '09

import Data.Binary and then write a variant of something like how Maps are currently serialised: instance (Ord k, Binary k, Binary e) => Binary (Map.Map k e) where put m = put (Map.size m) >> mapM_ put (Map.toAscList m) get = liftM Map.fromDistinctAscList get So you might want something that avoids flattening it to a list first -- Don frigginfriggins: > can you link to a good example of writing your own because I couldn't find one. > > On Sat, Mar 7, 2009 at 8:57 PM, Don Stewart <dons(a)galois.com> wrote: > > Increase the stack size, or use a different serialiser (they're only a > half dozen lines to write), or different data structure? > > -- Don > > frigginfriggins: > > I'm playing around with Netflix, implementing a simple KNN-algorithm, I > will > > later try SVD which seems to be the most successful approach. > > > > Using a database like Postgresqk is to slow so I want to serialize a > > datastructure containing the ratings. I'm not sure about the > > representation I will use just yet, if I should use multiple arrays or an > Map/ > > IntMap. > > > > However I tried Data.Binary and already for small sizes I get stack > overflow > > when deserializing. > > The serializing works fine but when bringing it back it overflows. > > How can I solve this? This is just 2MB, I will eventually need soemthing > like > > 2-500MB to store everything depending on what representatin I choose. > > > > module Serialize where > > import qualified Data.Binary as B > > import qualified Data.Binary.Put as P > > import qualified Data.Map as M > > import qualified Data.List as L > > > > genTest :: Int -> M.Map (Int,Int) Int > > genTest n = let movies = take n $ repeat 1 > > grades = take n $ repeat 4 in > > M.fromList $ ([1..n] `zip` movies) `zip` grades > > > > main = do > > let a = genTest 50000 > > B.encodeFile "C:/users/saftarn/desktop/bintest.txt" a > > print "Success" > > > > dec = B.decodeFile "C:/users/saftarn/desktop/bintest.txt" >>= \a -> > > return $ (a :: M.Map (Int,Int) Int) > > > > > > > > > > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > >

1 0

Zippers
by Cristiano Paris 07 Mar '09

07 Mar '09

Hi, I'm trying to catch the connection between delimited continuations and zippers so I wrote a (kinda) zipper interface to a simple tree structure. Here's the code: ------- module Main where import Data.Maybe data Tree a = Leaf a | Fork (Tree a) (Tree a) deriving Show tree = Fork (Fork (Leaf 1) (Leaf 2)) (Fork (Leaf 3) (Fork (Leaf 4) (Leaf 5))) data ZContext a = ZContext { moveUp :: Maybe (ZContext a), moveLeft :: Maybe (ZContext a), moveRight :: Maybe (ZContext a), this :: Maybe a } initZ t = doInitZ Nothing t where doInitZ c (Leaf a) = ZContext c Nothing Nothing $ Just a doInitZ c t@(Fork l r) = ZContext c (Just $ doInitZ s l) (Just $ doInitZ s r) Nothing where s = Just $ doInitZ c t ------- You access the tree in the following way (session from ghci): *Main> this $ fromJust . moveLeft $ fromJust . moveLeft $ initZ tree I read Haskell book's Chapter about Zippers on Wikibooks and I think I understood the underlying concept even if the implementation still seems to me a bit arbitrary (i.e. different implementation can be provided even if the proposed one is neat thinking of differentiation). Hence, I decided to go experimenting myself and came up with the above solution. I know that the interface to a tree having values only on leaves is pointless as the main advantage of using a Zipper is to get O(1) performance on updating but I wanted to keep it as simple as possible. So, can you provide some comments on that implementation? Thank you all, as usual! -- Cristiano

4 8

Running HUnit tests when pushing to darcs on haskell.org
by Colin Paul Adams 07 Mar '09

07 Mar '09

Hello cafe, I've just followed the instructions at http://www.haskell.org/haskellwiki/How_to_write_a_Haskell_program to create my first library project on haskell.org, using darcs. I tried using the darcs setpref test command to execute: runhaskell tests/*.hs (which works locally) but it fails because it can't find Test.HUnit. When I looked back at the webpage, I see it specifically mentions QuickCheck and not HUnit, so I guess I should not have been surprised. But I would like to know if this is possible, and if so, how to arrange that runhaskell can find Test.HUnit. -- Colin Adams Preston Lancashire

1 0

Interesting problem from Bird (4.2.13)
by R J 07 Mar '09

07 Mar '09

Could someone provide an elegant solution to Bird problem 4.2.13? Here are the problem and my inelegant solution: Problem ------- Since concatenation seems such a basic operation on lists, we can try to construct a data type that captures concatenation as a primitive. For example, data (CatList a) = CatNil | Wrap a | Cat (CatList a) (CatList a) The intention is that CatNil represents [], Wrap x represents [x], and Cat x y represents x ++ y. However, since "++" is associative, the expressions "Cat xs (Cat ys zs)" and "Cat (Cat xs ys) zs" should be regarded as equal. Define appropriate instances of "Eq" and "Ord" for "CatList". Inelegant Solution ------------------ The following solution works: instance (Eq a) => Eq (CatList a) where CatNil == CatNil = True CatNil == Wrap z = False CatNil == Cat z w = ( z == CatNil && w == CatNil ) Wrap x == CatNil = False Wrap x == Wrap z = x == z Wrap x == Cat z w = ( Wrap x == z && w == CatNil ) || ( Wrap x == w && z == CatNil ) Cat x y == CatNil = x == CatNil && y == CatNil Cat x y == Wrap z = ( x == Wrap z && y == CatNil ) || ( x == CatNil && y == Wrap z ) Cat x y == Cat z w = unwrap (Cat x y) == unwrap (Cat z w) unwrap :: CatList a -> [a] unwrap CatNil = [] unwrap (Wrap x) = [x] unwrap (Cat x y) = unwrap x ++ unwrap y instance (Eq a, Ord a) => Ord (CatList a) where x < y = unwrap x < unwrap y This solution correctly recognizes the equality of the following, including nested lists(represented, for example, by Wrap (Wrap 1), which corresponds to [[1]]): Wrap 1 == Cat (Wrap 1) CatNil Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) == Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) Wrap (Wrap 1) == Wrap (Cat (Wrap 1) CatNil) Although this solution works, it's a hack, because unwrap converts CatLists to lists. The question clearly seeks a pure solution that does not rely on Haskell's built-in lists. What's the pure solution that uses cases and recursion on CatList, not Haskell's built-in lists, to capture the equality of nested CatLists? _________________________________________________________________ Windows Live™ Contacts: Organize your contact list. http://windowslive.com/connect/post/marcusatmicrosoft.spaces.live.com-Blog-…

6 7