- Haskell - Haskell.org

RE: [Haskell] Can anyone help me with partition numbers?
by E. Zuurbier (Erik) 25 Nov '05

25 Nov '05

Doaitse, For generate 4 this gives a.o. three equivalent solutions: [1,1,2], [1,2,1] and [2,1,1]. I guess the ultimate idea would be to prune permutations. Regards Erik Zuurbier Onderwerp: Re: [Haskell] Can anyone help me with partition numbers? Or (since we started to do someone's homework anyway) generate 0 = [[]] generate n = [x:rest | x <- [1..n], rest <- generate (n-x)] Doaitse Swierstra On 2005 nov 25, at 10:29, Tomasz Zielonka wrote: > On Thu, Nov 24, 2005 at 05:52:23PM +0100, Jan van Eijck wrote: >> Like so: >> >> generatePs :: (Int,[Int]) -> [[Int]] >> generatePs (n,[]) = [take n (repeat 1)] >> generatePs (n,(x:xs)) = >> (take n (repeat 1) ++ (x:xs)) : generatePs (pack (x-1) ((n >> +x),xs)) >> where >> pack :: Int -> (Int,[Int]) ->(Int,[Int]) >> pack 1 (m,xs) = (m,xs) >> pack k (m,xs) = if k > m then pack (k-1) (m,xs) >> else pack k (m-k,k:xs) >> >> parts :: Int -> [[Int]] >> parts n | n < 1 = error "part: argument <= 0" >> | n == 1 = [[1]] >> | otherwise = generatePs (0,[n]) > > How about a shorter version? > > part :: Integer -> [[Integer]] > part = gen 1 > where > gen m 0 = [[]] > gen m n = [ x:xs | x <- [m..n], xs <- gen x (n - x) ] > > Best regards > Tomasz > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell _______________________________________________ Haskell mailing list Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell

1 0

Broken monad laws
by Iavor Diatchki 24 Nov '05

24 Nov '05

Hello, I just noticed that the GHC/Hugs "standard" libraries have acquired a list monad transformer, which is broken, because it does not satisfy the associativity law when applied to non-commutative monads. I am not referring to some corner-case strictness problem, but rather a fairly well known result. The associativity law is important, because without it the 'do' notation can be very confusing. Bellow is an example, for people not familiar with the porblem. -Iavor import Control.Monad.List say :: String -> ListT IO () say x = lift (putStr x) one_two, ex1,ex2 :: ListT IO () one_two = say "1 " `mplus` say "2 " ex1 = do one_two say "3 " say "4 " ex2 = do do one_two say "3 " say "4 " main = runListT ex1 >> putStrLn " or " >> runListT ex2

2 1

Lazy state monads
by Yitzchak Gale 23 Nov '05

23 Nov '05

(Moved from the libraries list to the haskell list.) I wrote: > > createItems :: RandomGen g => State g [Item] > > createItems = > > liftM catMaybes $ runListT $ > > flip evalStateT initialState $ runMaybeT $ > > do > > item <- liftRandom $ repeatM randomItem > > updateState item > > needMoreItems >>= guard > > return item > > where > > liftRandom = lift . lift . lift Udo Stenzel wrote: > ...but this is probably broken anyway. After > (repeatM randomItem) presumably the state (the > RandomGen) is _|_, but the type of createItems > would suggest it is still usable. No, it works. MaybeT tells ListT when to stop its iteration. After that, the RandomGen can be used again elsewhere. > I wouldn't do that. Other than that it's a bit > hard to see what you're trying to accomplish > here. Lazy monads are an important programming paradigm in practice. Laziness helps to completely decouple the various ingredients of the algorithm from each other. This helps in debugging, and in dividing tasks among different development teams. The monadic approach helps makes refactoring easy (a common complaint against Haskell). For example, it would be trivial to add exception handling, or logging. The algorithm is clearly specified as an iteration of a series of steps, the way most people would naturally think of it. Yet the calculation is completely pure. So a compiler is not required to follow the steps literally. It can split the calculation across different threads, processors, http connections, etc., if it is smart enough. This is the way industrial software development should be done. It is clearly far better than imperative OO. Regards, Yitz

1 0

Haskell Weekly News: November 22, 2005
by John Goerzen 22 Nov '05

22 Nov '05

Haskell Weekly News: November 22, 2005 Greetings, and thanks for reading the 16th issue of HWN, a weekly newsletter for the Haskell community. Each Tuesday, new editions will be posted (as text) to [1]the Haskell mailing list and (as HTML) to [2]The Haskell Sequence. 1. http://www.haskell.org/mailman/listinfo/haskell 2. http://sequence.complete.org/ New Releases There are several exciting releases to report this week. * hmp3. Donald Bruce Stewart [3]announced hmp3, an ncurses-based music player written in Haskell. 3. http://article.gmane.org/gmane.comp.lang.haskell.general/12637 * Frag. Mon Hon Cheong [4]announced Frag, a first-person shooter written in Haskell using HOpenGL. Several comments were posted offering thanks and seeking more information. [5]Screenshots are also available. 4. http://thread.gmane.org/gmane.comp.lang.haskell.general/12628 5. http://haskell.org/hawiki/Frag * Haskell Communities & Activities Report. The November 2005 editition of this report is now [6]available. 6. http://article.gmane.org/gmane.comp.lang.haskell.general/12624 * Haskell Server Pages 0.4.0. The latest release of HASP is now [7]available, featuring a new bytecode generator and less of a need for many other add-on packages. 7. http://article.gmane.org/gmane.comp.lang.haskell.general/12617 * Blobs diagram editor. The first release of Blobs was [8]announced this week. It is based on earlier work that has been shown at some Haskell conferences. 8. http://article.gmane.org/gmane.comp.lang.haskell.general/12603 Requests for Participation Take 10 list. Kenneth Hoste [9]posted a request for user contributions regarding a top 10 list of Haskell libraries. 9. http://article.gmane.org/gmane.comp.lang.haskell.general/12639 Discussion Updating Haskell. It's been a busy week for these discussions. There have been threads on [10]records (~ 200 messages) and [11]GHC. Unfortunately your HWN editor hasn't had time to read these monster threads, so have at it! 10. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/9201 11. http://thread.gmane.org/gmane.comp.lang.haskell.general/12592 About Haskell Weekly News Want to continue reading HWN? Please help us create new editions of this newsletter. Please see the [12]contributing information, or send stories to hwn -at- complete -dot- org. There is also a Darcs repository available. 12. http://sequence.complete.org/hwn-contrib

1 0

take 10 [1..] article series: Libraries ( please contribute ! )
by Kenneth Hoste 22 Nov '05

22 Nov '05

As was already announced, I'll try to provide an article for each upcoming TMR [1] issue, regarding some subject in the world of Haskell. My intention is to write a short piece on some item which fits the monthly subject. The first topic for the series of 'take 10 [1..]' articles is Libraries, and will be published in the next TMR issue (December). I'll choose a top 10 (without ordering, this is no popularity contest), and try and summarize what the library is meant for, who is maintaining it, why you should use it, ... I'd like to ask this mailing list to make a contribution: which Haskell library is your favorite, which ones do you _really_ need for your work with Haskell, which ones do you like. Please feel free to reply one or more suggestions, or adjust the wiki [2]. [1] http://haskell.org/tmrwiki [2] http://haskell.org/tmrwiki/TopTenHaskell_25Libraries boegel -- Statistics are like a bikini. What they reveal is suggestive, but what they conceal is vital (Aaron Levenstein) Kenneth Hoste ELIS - Ghent University http://elis.ugent.be/~kehoste

1 0

ANNOUNCE: hm p3 - an ncurses mpeg layer 3 player
by dons＠cse.unsw.edu.au 22 Nov '05

22 Nov '05

hmp3 : an ncurses music player written in Haskell hmp3 is an ncurses-based music player, for MPEG Layer 3 audio files, written in Haskell. It uses mpg321 or mpg123 for its decoding backend. It is designed to be simple, fast and robust. By web (screenshot): http://www.cse.unsw.edu.au/~dons/hmp3.html By darcs: darcs get --partial http://www.cse.unsw.edu.au/~dons/code/hmp3 Thanks go to Stefan Wehr and Samuel Bronson for testing. In particular Sam burnt many cpu cycles testing stability. Thanks! Cheers, Don

1 0

Re: Type Class Question
by oleg＠pobox.com 22 Nov '05

22 Nov '05

Paul Govereau wrote: > BTW, The above program is a translation of an idiomatic use of > functors in ML (pardon my syntax): > > module A : sig type t = ... end > module B : funsig(X:SHOW where t = A.t) sig bar : A.t -> string end > module C : SHOW where t = A.t > open A > open B(C) ML modules poorly correspond to Haskell modules. Rather, they correspond to Haskell typeclasses: {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} module Foo where -- module A : sig type t = ... end -- A is a constraint on type t class A t -- different instances of A will define what t actually means -- module B : funsig(X:SHOW where t = A.t) sig bar : A.t -> string end class (A t, Show t) => B t where bar :: t -> String -- module C : SHOW where t = A.t -- A restriction on Show such that its type parameter is constrained to -- be in A class (A t, Show t) => C t instance (A t, Show t) => C t -- open A -- Perhaps some implementation of A must be provided somewhere... -- open B(C) instance C t => B t where bar = show -- Eventually we need to give a structure that implements signature A data X = X instance A X instance Show X where show _ = "X" test = bar X

1 0

RE: [Haskell] Type Class Question
by Simon Peyton-Jones 22 Nov '05

22 Nov '05

GHC insists that every type class constraint mentions a type variable that is quantified just outside the constraint. E.g. forall a b c. (C a c, D b) => ... The constraints (C a c), (D b) must each mention at least one of a,b,c. Why? Because it makes it much easier to know when a constraint must be solved. Consider f :: K a => ... g :: E b => b -> b g x = let h :: D b => ... h x = ....(f e).... in ... Notice that there is no 'forall' on the type sig for h, so it disobeys GHC's rule. Suppose the call to f is at type (Tree [b]). That gives rise to the constraint (K (Tree [b])). Now, can the constraint (K (Tree [b])) be satisfied by the (D b)? Or by the enclosing constraint (E b)? Or by a combination of the two? At the moment GHC's rule means it can use the rule "a constraint C floats outwards until it hit a 'forall' that binds one of the type variables mentioned in C. Then C must be solved using the constraints bound at that forall". All this makes solving easier. Everything would work fine without the restriction, but inference would be a bit harder. So far, solving that harder inference problem hasn't seemed important enough, but it's certainly soluble. (Martin Sulzmann's implication constraints suggest how.) Simon | -----Original Message----- | From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Paul Govereau | Sent: 22 November 2005 07:56 | To: haskell(a)haskell.org | Subject: Re: [Haskell] Type Class Question | | | Ah yes, but this forces me to write my instance of Show right away. I | cannot write: | | module A where data X = X | module B where | import A | bar x = show x -- here is the problem | moduel C where | import A | instance Show X where show x = "X" | module Main where | import A | import B -- Show instance used | import C -- Show instance defined | | I am not saying that this is terribly useful, I am just wondering why | it is a problem to allow it? | | Paul | | BTW, The above program is a translation of an idiomatic use of | functors in ML (pardon my syntax): | | module A : sig type t = ... end | module B : funsig(X:SHOW where t = A.t) sig bar : A.t -> string end | module C : SHOW where t = A.t | open A | open B(C) | | | On Nov 21, Cale Gibbard wrote: | > data X = X deriving Show | > | > bar :: X -> String | > bar x = show x | > | > There's no need for the class constraint at all. If it's an instance | > of Show, then you're okay with just applying show to it. There's no | > need to actually assert that it's actually an instance of Show again. | > | > The only purpose of class constraints is to restrict polymorphism. If | > a function isn't polymorphic to begin with, you should never need | > them. | > | > - Cale | > | > On 21/11/05, Paul Govereau <govereau(a)eecs.harvard.edu> wrote: | > > Hello, | > > | > > I was hoping that someone could answer a question I have about the | > > type class system. In Haskell, I cannot write a term with an exact | > > constraint: | > > | > > > data X = X | > > > bar :: Show X => X -> String | > > > bar x = show x | > > | > > According to the Haskell 98 report, a qualifier can only be applied to | > > type variables, but I don't see where the trouble is. The term seems | > > to have reasonable type, and I don't see any reason why the | > > dictionary-passing translation shouldn't work out; I am wondering what | > > problems you run into if this restriction is lifted? | > > | > > Note, with GHC and Glasgow extensions you can write this program: | > > | > > > data Y a = Y | > > > foo :: Show (Y a) => Y a -> String | > > > foo x = show x | > > | > > However, the first program is still ruled out. Are there any | > > type-class experts out there that can offer an explanation? | > > | > > Thanks, | > > Paul | > > _______________________________________________ | > > Haskell mailing list | > > Haskell(a)haskell.org | > > http://www.haskell.org/mailman/listinfo/haskell | > > | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell

1 0

Type Class Question
by Paul Govereau 22 Nov '05

22 Nov '05

Hello, I was hoping that someone could answer a question I have about the type class system. In Haskell, I cannot write a term with an exact constraint: > data X = X > bar :: Show X => X -> String > bar x = show x According to the Haskell 98 report, a qualifier can only be applied to type variables, but I don't see where the trouble is. The term seems to have reasonable type, and I don't see any reason why the dictionary-passing translation shouldn't work out; I am wondering what problems you run into if this restriction is lifted? Note, with GHC and Glasgow extensions you can write this program: > data Y a = Y > foo :: Show (Y a) => Y a -> String > foo x = show x However, the first program is still ruled out. Are there any type-class experts out there that can offer an explanation? Thanks, Paul

2 2

PADL 2006 Call for Participation
by Logic Programming Rsrch Association 21 Nov '05

21 Nov '05

-------------------------------------------------------------------------------- CALL FOR PARTICIPATION CALL FOR PARTICIPATION [ - Apologies for multiple messages; - Deadline for early registration: Dec 15th] Eighth International Symposium on Practical Aspects of Declarative Languages PADL 06 Charleston Place Hotel Charleston, South Carolina January 9-10, 2006 http://www.cs.brown.edu/people/pvh/PADL06.html Co-located with ACM's Principles of Programming Languages, (POPL Dates: January 11-13, 2006) You are cordially invited to attend the 8th Symposium on Practical Aspects of Declarative Languages to be held in Charleston, SC. PADL has a very interesting program that includes invited speakers as well contributed papers. Contributed papers range over diverse topics: from bioinformatics to music modeling to semantic web. Invited Speakers: Phil Wadler, University of Edinburgh, speaking on Links: Linking Theory to Practice for the Web David Roundy, Cornell University Implementing and verifying the darcs patch formalism Erik Meijer, Microsoft Research (title TBA) Contributed papers: Using CHRs to generate functional test cases for the Java Card Virtual Machine Sandrine-Dominique GOURAUD and Arnaud GOTLIEB. Generic Cut Actions for External Prolog Predicates Tiago Soares, Ricardo Rocha and Michel Ferreira. Controlling search space materialization in a practical declarative debugger Ian MacLarty and Zoltan Somogyi. Automatic Verification of a Model Checker by Reflection Bow-Yaw Wang. Probabilistic-logical Modeling of Music Jon Sneyers, Joost Vennekens and Danny De Schreye. Using Dominators for Solving Constrained Path Problems Luis Quesada, Peter Van Roy, Yves Deville and Raphakl Collet. JQuery: A Generic Code Browser with a Declarative Configuration Language Kris De Volder. A Hybrid BDD and SAT Finite Domain Constraint Solver Peter Hawkins and Peter Stuckey. Adding constraint solving to Mercury Ralph Becket, Maria Garcia de la Banda, Kim Marriott, Zoltan Somogyi, Peter Stuckey and Mark Wallace. Modeling Genome Evolution with a DSEL for Probabilistic Programming Martin Erwig and Steve Kollmansberger. Tabling in Mercury: Design and Implementation Zoltan Somogyi and Konstantinos Sagonas. Translating Description Logic Queries to Prolog Zsolt Nagy, Gergely Lukacsy and Piter Szeredi. Efficient top-down set-sharing analysis using cliques Jorge Navas, Francisco Bueno and Manuel Hermenegildo. Querying Complex Graphs Yanhong A. Liu and Scott D. Stoller. Incremental Evaluation of Tabled Prolog: Beyond Pure Logic Programs Diptikalyan Saha and C. R. Ramakrishnan.

1 0