- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] Splitting a list
by Steve Schafer 23 Apr '04

23 Apr '04

On Wed, 21 Apr 2004 14:57:57 +0100, you wrote: >How about implementing a directly recursive solution? Simply >accumulate the sum so far, together with the list elements you have >already peeled off. Once the sum plus the next element would exceed >the threshold, emit the accumulated elements, and reset the sum >to zero. > > splitlist threshold xs = split 0 [] xs > where > split n acc [] = reverse acc: [] > split n acc (x:xs) > | x >= threshold = error (show x++" exceeds threshold ") > | n+x > threshold = reverse acc : split 0 [] (x:xs) > | otherwise = split (n+x) (x:acc) xs Thanks. Apart from a small off-by-one problem (the "x >= threshold" test needs to be "x > threshold" instead), it works fine. I had actually started along those lines, but got bogged down in the details of passing the accumulator around, and ended up painting myself into a corner, so I abandoned that approach (prematurely, as it turns out). And thanks to everyone else who replied--I don't want to clutter the list with a lot of individual replies. As you can probably tell, I've only recently begun playing with Haskell, and the process of reconfiguring my neurons into recursive loops has not yet been completed. -Steve

1 0

Re: [Haskell-cafe] Syntax for modifying nested product types
by MR K P SCHUPKE 23 Apr '04

23 Apr '04

I would just do: f' = if cond0 then f else id g' = if cond1 then g else id foo { bar = f' (bar foo) , wib = g' (wib foo) } I like seeing the record updated, rather than hiding it in a function. Regards, Keean.

1 0

Splitting a list
by Steve Schafer 22 Apr '04

22 Apr '04

I have a list of integers, e.g.: [1,5,3,17,8,9] I want to split it into a pair of lists, with the criterion being that the sum of the elements in the first list is as large as possible, but not exceeding a threshold value. For example, if the threshold is 10, the result should be: ([1,5,3],[17,8,9]) and then I want to recursively apply this process to the remainder of the list, with the end result being a list of lists of integers. Using the same list along with a threshold of 18, I would get: [[1,5,3],[17],[8,9]] I have devised a means of doing this: 1) Create an auxiliary list of integers, where the n'th element is equal to the sum of the first n elements of the original list. 2) Zip the auxiliary list with the original list. 3) Use span to break the list in two according to the threshold. 4) Unzip the two resulting lists and discard the auxiliary portions. 5) Repeat from step 1, operating on the tail of the list, until there's nothing left. Here's the code that implements this: runningSum :: (Ord a, Num a) => [a] -> [a] runningSum [] = [] runningSum (i:[]) = i : [] runningSum (i:j:js) = i : runningSum (i+j : js) zipWithSum :: (Ord a, Num a) => [a] -> [(a,a)] zipWithSum xs = zip (runningSum xs) xs threshold :: (Ord a, Num a) => [a] -> a -> ([(a,a)],[(a,a)]) threshold xs t = let test x = (t >= (fst x)) in span test (zipWithSum xs) splitFirst :: (Ord a, Num a) => [a] -> a -> ([a],[a]) splitFirst xs t = let (ys,zs) = threshold xs t in (snd (unzip ys), snd (unzip zs)) splitAll :: (Ord a, Num a) => [a] -> a -> [[a]] splitAll [] _ = [] splitAll xs t = let (ys, zs) = splitFirst xs t in ys : (splitAll zs t) (One thing that's missing from this code is a check to verify that no single element in the list is greater than the threshold, which should raise an error, rather than get stuck in an infinite loop.) The algorithm as implemented works fine, but it seems overly complicated and not very elegant. I get the feeling that I'm missing some obvious simplification, but I can't find it. Any ideas? Thanks, -Steve Schafer

5 5

Re: [Haskell-cafe] Splitting a list (Modified by Doaitse Swierstra)
by Doaitse Swierstra 21 Apr '04

21 Apr '04

I have the impression that my posting did not make it, so I am trying again: How about: splitList weight l = munch l weight where munch [] _ = [[]] munch p@(x:xs) w = if w >= x then let (r:rr) = munch xs (w-x) in (x:r):rr else []:munch p weight main = print (splitList 18 [1,5,3,17,8,9]) Doaitse Swierstra PS: note that your problem is a bit underspecified: -- what to return for an empty list -- what to do if a number is larger than the weight On 2004 apr 21, at 15:42, Steve Schafer wrote: > I have a list of integers, e.g.: > > [1,5,3,17,8,9] > > I want to split it into a pair of lists, with the criterion being that > the sum of the elements in the first list is as large as possible, but > not exceeding a threshold value. For example, if the threshold is 10, > the result should be: > > ([1,5,3],[17,8,9]) > > and then I want to recursively apply this process to the remainder of > the list, with the end result being a list of lists of integers. Using > the same list along with a threshold of 18, I would get: > > [[1,5,3],[17],[8,9]] > > I have devised a means of doing this: > > 1) Create an auxiliary list of integers, where the n'th element is > equal > to the sum of the first n elements of the original list. > > 2) Zip the auxiliary list with the original list. > > 3) Use span to break the list in two according to the threshold. > > 4) Unzip the two resulting lists and discard the auxiliary portions. > > 5) Repeat from step 1, operating on the tail of the list, until there's > nothing left. > > Here's the code that implements this: > > runningSum :: (Ord a, Num a) => [a] -> [a] > runningSum [] = [] > runningSum (i:[]) = i : [] > runningSum (i:j:js) = i : runningSum (i+j : js) > > zipWithSum :: (Ord a, Num a) => [a] -> [(a,a)] > zipWithSum xs = zip (runningSum xs) xs > > threshold :: (Ord a, Num a) => [a] -> a -> > ([(a,a)],[(a,a)]) > threshold xs t = let test x = (t >= (fst x)) > in span test (zipWithSum xs) > > splitFirst :: (Ord a, Num a) => [a] -> a -> ([a],[a]) > splitFirst xs t = let (ys,zs) = threshold xs t > in (snd (unzip ys), snd (unzip zs)) > > splitAll :: (Ord a, Num a) => [a] -> a -> [[a]] > splitAll [] _ = [] > splitAll xs t = let (ys, zs) = splitFirst xs t > in ys : (splitAll zs t) > > (One thing that's missing from this code is a check to verify that no > single element in the list is greater than the threshold, which should > raise an error, rather than get stuck in an infinite loop.) > > The algorithm as implemented works fine, but it seems overly > complicated > and not very elegant. I get the feeling that I'm missing some obvious > simplification, but I can't find it. Any ideas? > > Thanks, > > -Steve Schafer > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

WildCard question
by Paul Cosby 14 Apr '04

14 Apr '04

Hi, I am very new to haskell and the program hugs and I am having problems using the wildcard operator _ Every time I try to use it in an definition it says something like the symbol /017 is not recognised. I am sure my defintions are correct as I tested it with an example defintion from Alan Thompsons craft of functional programming book. I am guessing that all the relevant modules have not been loaded properly. I have reinstalled hugs with full implementation and this has not helped. I am using a windows 98 PC. Any help suggestions? Or has anyone just got the wildcard definition which are could just paste into my scripts Many thanks --------------------------------- Yahoo! Messenger - Communicate instantly..."Ping" your friends today! Download Messenger Now

5 4

[Haskell-cafe] Call for Contributions - HC&A Report (May 2004 edition)
by Arthur van Leeuwen 14 Apr '04

14 Apr '04

Dear Haskellers, two changes of season and one of editor later, we strongly suspect the Haskell community has also moved along admirably. Thus comes the need to refresh our list of all things Haskell, and give *you* the opportunity to tell all the world about your passion. We invite your contributions to the imminent sixth edition of the ================================================================ Haskell Communities & Activities Report http://www.haskell.org/communities/ Submission deadline: 7 May 2004 (please send your contributions to hcar(a)haskell.org, in plain ASCII or LaTeX format) ================================================================ The Haskell Communities & Activities Reports biannually report on the state of Haskell over the last 6 months, and sometimes on plans for the next 6 months. If you have only recently joined the Haskell world, browse the November 2003 edition -- you will find an overview of what's going on as well as starting points and links that may provide many answers. We would much like you to send your contributions in by the first week of May, and will then endeavor to publish the collective report roughly a month before the start of summer. Note that this is a great opportunity to gauge the state of your research, update your web pages, release new versions, announce entirely new projects, summarize developments in sub-communities for every Haskeller to see, etc. :) The way we like to do things is have you update all existing summaries, as the purpose of these reports is to show *recent/current* activities. We will drop any topics that haven't had any activity since May 2003, so if you haven't updated your topic since then, now is a good time! Ofcourse, if you have new things to share, so much the better. We would love to hear of it, and include it in the report. Please keep your contributions short though, a couple hundred words maximum, as we would like to keep the size of the report reasonable. It is intended as an overview after all. Looking forward to your contributions, Arthur (interim editor, May 2004 edition) ----------------------------------- topics New suggestions for current hot topics, activities, projects, etc. are welcome - especially with names and addresses of potential contacts, but here is a non-exclusive list of likely topics (see also http://www.haskell.org/communities/topics.html ): General Haskell developments; Haskell implementations; Haskell extensions; Standardization and documentation; Haskell tutorials, howtos and wikis; Organisation of Haskell tool and library development; Haskell-related projects and publications; new research, fancy tools, long-awaited libraries, cool applications; Feedback from specialist mailing lists to the Haskell community as a whole; Haskell announcements; all (recent) things Haskell Announcements: if you've announced anything new on the Haskell list over the last six months, you'll want to make sure that is reflected in this edition! Project pings: if you're maintaining a Haskell tool or library or somesuch, you'll want to let everyone know that it is still alive and actively maintained, even if there have been no new additions, but all the more if there have been new developments. Tutorials: if you've fought with some previously undocumented corner of Haskell, and have been kind enough to write down how you did manage to build that graphical user interface, or if you' ve written a tutorial about some useful programming techniques, this is your opportunity to spread the word (short, topic-specific, and hands-on tutorials that only show how to achieve a certain practical task would do a lot to make things easier for new Haskellers - please write some!) Applications: if you've been working quietly, using Haskell for some interesting project or application (commercial or otherwise), you might want to let others know about what you're using Haskell for, and about your experiences using the existing tools and libraries; are you using Haskell on your job? An interesting thread about using Haskell and more generally functional programming for non-Haskell things seems to recur with reasonable frequency - why not write a sentence or two about your use of Haskell for our report? Feedback: if you're on one of the many specialist Haskell mailing lists, you'll want to report on whatever progress has been made there (GUI API discussions, library organisation, etc.) If you're unsure whether a contact for your area of work has come forward yet, have a look at the report's potential topics page, or get in touch with me. I've contacted last time's contributors, hoping they will volunteer to provide updates of their reports, and will update the contacts on the topics page fairly regularly. But where you don't yet see contacts listed for your own subject of interest, you are very welcome to volunteer, or to remind your local community/project team/mailing list/research group/etc. that they really ought to get their act together and let the Haskell community as a whole know about what they've been doing! :-) -------------------------- what should I write? That depends on your topic, but as a general rule, it shouldn't take you long. A simple sentence or two about your use of Haskell could go into the "Individual Haskellers and their projects" section. If you're a company, or if you're working on a project using Haskell as the implementation language, a paragraph on that could go into the "Commercial Applications" and "Non-Commercial Applications" sections. A typical summary report about a tool/library/project/application/.. would be between 1 and 3 paragraphs of ASCII text (what's it about? major topics and results since the last report? current hot topics? major goals for the next six months?) plus pointers to material for further reading (typically to a home page, or to mailing list archives, specifications and drafts, implementations, meetings, minutes,..). For those who prefer templates to fill in, the report is edited in LaTeX, and an entry template might look something like this: \subsubsection{<MYSTUFF>} \report{<MY NAME}\\ <WHAT IS IT?> <WHAT IS ITS STATUS? / WHAT HAS HAPPENED SINCE LAST TIME?> <CAN OTHERS GET IT?> <WHAT ARE THE IMMEDIATE PLANS?> <FURTHER READING> \url{<PROJECT URL>} Browsing through previous editions should give you a good idea of the variety of possibilities, ranging from very brief to extensive. -- Haskell Communities and Activities Report (May 2004 edition) All contributions are due in by the 7th of May 2004! http://www.haskell.org/communities/

1 0

C Bindings?
by Russ Lewis 13 Apr '04

13 Apr '04

Does Haskell have some mechanism that allows it to link to C, or other imperative languages? I know, you could use the IO Monad to do it...using stdin and stdout as pipes to any other program. But is there a way to link Haskell into a C program? Thanks again for the help for a newbie... Russ

3 2

RE: [Haskell-cafe] Building Haddock on Windows
by Bayley, Alistair 13 Apr '04

13 Apr '04

> Try upgrading GHC. Thanks, I'll try that. Would it be too much to ask that Haddock be distributed with GHC? Reasons for: - GHC library docs are produced with Haddock - GHC library docs already include Haddock interface files - would ensure version of Haddock matches that used to produce interface files - would save lazy developers like myself from downloading and compiling. Think of it as one less barrier to overcome; a small step closer to more widespread adoption. Reasons against: - would favour one documentation tool over others - would add an unnecessary item to GHC build/packaging procedure (is this much of an overhead?) Mind you, if you include Haddock, why stop there? Why not include other developers tools, like (say) Hmake, Happy, Hat, ...? Alistair. > -----Original Message----- > From: Simon Marlow [mailto:simonmar@microsoft.com] > Sent: 13 April 2004 10:59 > To: Bayley, Alistair > Cc: haskell-cafe(a)haskell.org > Subject: RE: [Haskell-cafe] Building Haddock on Windows > > > Yes, I suspect you have a mismatch between the version of Haddock on > your system and the version of Haddock used to produce the interfaces. > Try upgrading GHC. > > Cheers, > Simon > > > -----Original Message----- > > From: Bayley, Alistair [mailto:Alistair_Bayley@ldn.invesco.com] > > Sent: 05 April 2004 16:19 > > To: Simon Marlow > > Cc: haskell-cafe(a)haskell.org > > Subject: RE: [Haskell-cafe] Building Haddock on Windows > > > > Trying to invoke Haddock with > > --read-interface=c:\ghc\ghc-6.0\doc\html\base\base.haddock > > > > Initially I get a stack overflow, so I added: +RTS -K2M -RTS ... > > > > and now I get: > > Fail: end of file > > Action: Data.Binary.getWord8 > > > > Is the --read-interface option specified correctly? This is > > where my GHC > > installation is, and the base.haddock file exists in there. I > > assume this is > > the interface file. > > > > Is this a compatibility problem? i.e. haddock file > > distributed with GHC 6.0 > > too old for Haddock 0.6? ----------------------------------------- ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

1 0

What's wrong with my Haskell code?
by Meihui Fan 13 Apr '04

13 Apr '04

when loading the following code, hugs escaped and reported that ERROR "cal24.hs":10 - Instance of Integral (Ratio Integer) required for definition of Main.eval I don't know why and how to solve it, anyone help me? data ETree = Add ETree ETree | Sub ETree ETree | Mul ETree ETree | Div ETree ETree | Node Integer deriving Show eval :: ETree->Maybe Rational eval (Node x) = Just (fromInteger x) eval (Add t1 t2) = do { x<-eval t1; y<-eval t2; if x>=y then return (x+y) else Nothing } eval (Sub t1 t2) = do { x<-eval t1; y<-eval t2; return (x-y) } eval (Mul t1 t2) = do { x<-eval t1; y<-eval t2; if x>=y then return (x*y) else Nothing } eval (Div t1 t2) = do { x<-eval t1; y<-eval t2; if y/=0 then return (x `div` y) else Nothing }

2 1

RE: [Haskell-cafe] Building Haddock on Windows
by Simon Marlow 13 Apr '04

13 Apr '04

Yes, I suspect you have a mismatch between the version of Haddock on your system and the version of Haddock used to produce the interfaces. Try upgrading GHC. Cheers, Simon > -----Original Message----- > From: Bayley, Alistair [mailto:Alistair_Bayley@ldn.invesco.com] > Sent: 05 April 2004 16:19 > To: Simon Marlow > Cc: haskell-cafe(a)haskell.org > Subject: RE: [Haskell-cafe] Building Haddock on Windows > > Trying to invoke Haddock with > --read-interface=c:\ghc\ghc-6.0\doc\html\base\base.haddock > > Initially I get a stack overflow, so I added: +RTS -K2M -RTS ... > > and now I get: > Fail: end of file > Action: Data.Binary.getWord8 > > Is the --read-interface option specified correctly? This is > where my GHC > installation is, and the base.haddock file exists in there. I > assume this is > the interface file. > > Is this a compatibility problem? i.e. haddock file > distributed with GHC 6.0 > too old for Haddock 0.6? > > > > -----Original Message----- > > From: Simon Marlow [mailto:simonmar@microsoft.com] > > Sent: 17 March 2004 15:29 > > To: Bayley, Alistair > > Cc: haskell-cafe(a)haskell.org > > Subject: RE: [Haskell-cafe] Building Haddock on Windows > > > > > > > - why doesn't it know what Int, String, Float, IO, Monad, > > > Show, etc are? > > > What invocation option do I need to ensure it links to > > > Prelude/hierarchical-library stuff? (I think it's > > > --read-interface; must I > > > generate interface files for the Prelude and libraries though?) > > > > You get the interfaces for the libraries with a GHC > > installation. Just > > use the --read-interface flag to tell Haddock about them. > > > > Cheers, > > Simon > > ----------------------------------------- > ***************************************************************** > Confidentiality Note: The information contained in this > message, and any attachments, may contain confidential > and/or privileged material. It is intended solely for the > person(s) or entity to which it is addressed. Any review, > retransmission, dissemination, or taking of any action in > reliance upon this information by persons or entities other > than the intended recipient(s) is prohibited. If you received > this in error, please contact the sender and delete the > material from any computer. > ***************************************************************** > >

1 0