- Haskell-Cafe - Haskell.org

pet project - 7 Millennium Prize problemss
by Christopher Milton 13 Jan '04

13 Jan '04

Folks, I think Haskell can be used to solve several, if not all, of the seven problems. Now I have to decide which problem to tackle first. Chris ===== Christopher Milton cmiltonperl(a)yahoo.com

4 6

ghc optimization of incremental update
by Doug Brown 13 Jan '04

13 Jan '04

Does ghc make any attempt to analyze dataflow and eliminate unnecessary copying for incremental updates? I compile the code below with -O, and based on the time it takes to run I'd guess it's copying the array with every update, even though there's no need in this particular case to do that. Perhaps there's a compiler flag or pragma to turn on the analysis? module Main where import Array main = print (take 1 (reverse (elems (array_neg (setup 100000))))) setup i = listArray (1,i) [1..i] -- the next three lines are the important part. array_neg array = array_neg2 (length (elems array)) array array_neg2 0 array = array array_neg2 i array = array_neg2 (i-1) (array // [(i,-i)]) I realize I can force it to stop copying if I use a Monad, and there are of course more efficient ways to code this contrived testcase. I want to know if ghc can make it efficient as it stands.

1 0

RE: no continuations
by Kevin S. Millikin 12 Jan '04

12 Jan '04

On Tuesday, December 30, 2003 5:04 PM, Kevin S. Millikin [SMTP:kmillikin@atcorp.com] wrote: > Oh, sure. I didn't mean to quibble with the idea that continuations > are computational effects. Just wanted to point out that (I think) > you can't macro express mutation with call/cc, unless you've already > got mutation anyway. [snip] > Yup. If you do that, you can use d as your setter and c as your > getter: > > > (define c (make-cell)) > > (define d c) > > ((d 'set) 9) > > (c 'get) > 9 > > ((d 'set) 17) > > (c 'get) > 17 It sure looks like the example contradicts the assertion, but I happen to know that there is a set! (or some other assignment) in the macro expansion of define. I'm just using call/cc to get at that, rather than getting at the one in the expansion of letrec. Moved to Haskell Cafe.

4 9

Hi, I have a question!
by NamO 12 Jan '04

12 Jan '04

Hi. I am a student, who get interesting in Haskell. So, nowdays, I study Hakell with "Introduction to Functional Programming using Haskell - second edition" And today, I face an error from bellow code. ---------------------------- module OperationTest where data Nat = Zero | Succ Nat deriving (Show) (+) :: Nat -> Nat -> Nat m + Zero = m m + Succ n = Succ (m + n) ---------------------------- But above source make an error like bellow Reading file "g:\Haskell\OperationTest.hs": Dependency analysis ERROR "g:\Haskell\OperationTest.hs":8 - Ambiguous variable occurrence "+" *** Could refer to: OperationTest.+ Prelude.+ above source is from the text book - "Introduction to Functional Programming using Haskell - second edition" and I use Hugs to interpret it. I understand what interpreter say, but I don't know How I can solve this problem. Please, Help me!!! - 5 - P.S. Tank you very much to read my broken english letter.

4 5

JVM bridge
by Mark T.B. Carroll 11 Jan '04

11 Jan '04

With haskell-jvm-bridge-0.2.1 I get: ghc -package javavm HelloWorld.o HelloWorld_JVM.o Class_java_io_PrintStream.o Class_java_lang_System.o -o HelloWorld gcc: unrecognized option `-rpath' gcc: unrecognized option `-rpath' gcc: unrecognized option `-rpath' /usr/bin/ld: cannot open /usr/lib/jvm-bridge/lib/: File format not recognized $ ld --version GNU ld version 2.12.90.0.1 20020307 Debian/GNU Linux Copyright 2002 Free Software Foundation, Inc. This program is free software; you may redistribute it under the terms of the GNU General Public License. This program has absolutely no warranty. $ gcc --version 2.95.4 $ ghc --version The Glorious Glasgow Haskell Compilation System, version 6.2 I don't suppose anyone can hand-hold me through tracking this problem down? -- Mark

4 5

RE: no continuations
by Kevin S. Millikin 10 Jan '04

10 Jan '04

On Friday, January 09, 2004 2:48 AM, Ashley Yakeley [SMTP:ashley@semantic.org] wrote: > > Do you have an example of use of Y for letrec where a program would > violate R5RS? Sure, take a look at my implementation of Ben Rudiak-Gould's implementation of Alan Bawden's implementation of boxes. In 4.2.2 of R5RS, it says, re letrec: Semantics: The <variable>s are bound to fresh locations holding undefined values, the <init>s are evaluated in the resulting environment (in some unspecified order), each <variable> is assigned to the result of the corresponding <init>, the <body> is evaluated in the resulting environment, and the value(s) of the last expression in <body> is(are) returned. Each binding of a <variable> has the entire `letrec' expression as its region, making it possible to define mutually recursive procedures. The result of the corresponding <init> is *assigned to* each <variable> (anyone know why the wording is backward above?), and that is after the <init>s are evaluated, which is after the <variable>s are bound. There was a discussion on comp.lang.scheme a couple of years ago about this. http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&th=fdcf3 554852a3cad&seekm=3AC66F16%40MailAndNews.com#link1 http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&th=a47e0 3e456b2dc2a&seekm=200102220358.TAA77339%40adric.cs.nps.navy.mil#link1 http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&th=58a68 6525be78d16&rnum=1

1 0

Re: Combining distinct-thread state monads?
by Graham Klyne 09 Jan '04

09 Jan '04

[Reply thread moved to Haskell-cafe] At 18:19 06/01/04 +1030, Dr Mark H Phillips wrote: >I am still learning about monads. I have a problem >in mind and am wondering whether state monads are >able to solve it. The difficulty is that it would >necessitate the interaction of two state threads >and I'm not sure whether Haskell state monads >allow this. Let me explain what I'm getting at. I'm not an expert in this, but I think what you are proposing is possible, to a point, possibly assuming that your monads have associated functions to combine and separate the monadic parts. Hmmm, let's try something... Given: combine :: ma -> mb -> mab separate :: mab -> (ma,mb) (where ma, mb, mab are the separate and combined state monads) f :: ma () -> mb () -> mc () f a b = do { ma1 <- fa1 a -- process state in a, returning ma1 -- fa1 :: ma -> mc ma ; mb1 <- fb1 b -- process state in b, returning mb1 ; let mab1 = combine ma1 mb1 ; mab2 = fab mab1 ; let (ma2,mb2) = separate mab2 ; ma3 <- fa3 ma2 -- process state in ma2 ; mb3 <- fb3 mb2 -- process state in mb2 ; return (fc ma3 mb3) } (This code is speculative, not tested in any way.) In this case, a third monad is used to schedule the operations on the separate monads, so in that respect the entire sequence is performed in a composite monad, within which methods defined for the separate monads can be invoked. To get the results, Monad 'mc' would need to provide a way to pick them out. It looks as if the combined monad 'mab' is probably superfluous. I think the composite monad 'mc' might be avoided, but some of the efficiency advantage of monads would be lost as the single-threading of each monad is potentially broken. I think that this may be all be achieved more cleanly using the monad transformer libraries and 'lift' methods -- can a state transformer be applied to a state monad? What I have noticed in my work with monads is that in most respects they can be treated just like any other value. Although they look different, a do sequence is just a monad-returning function, and any monad-returning function may be a do sequence. <aside> In my own work, I was pleasantly surprised how easy it was to use a Parsec parser monad (effectively a state monad, I think) to parse some data and return a combined state+IO monad, effectively precompiling a script, which which could then be executed by applying the resulting monad to an initial state, all within an IO monad. The code which does this can be seen at: http://www.ninebynine.org/Software/Swish-0.2.0/SwishScript.hs The main parser declaration is: script :: N3Parser [SwishStateIO ()] where 'script' is a Parsec parser monad which parses a script and returns a list of 'SwishStateIO ()' values, each of which is a combined state+IO monad. </aside> #g -- >Consider two state threads. The first has each state >being a non-negative int, thought of as a string of >binary digits. The second thread has each state >being a bool. > >Now I want to have a state monad which modifies >both threads as follows. Consider input states i (the >int thought of as binary string) and b (the bool), >and output states i' and b'. > > b' = not (b && (i `mod` 2)) > i' = i `div` 2 > >As you can see, both of these should be able to do >update-in-place provided the above order is adhered to. >We could achieve this using state monads where state >is an (Int, Bool) pair. We would have one monad >which did the first line, leaving i unchanged and >a second monad which did the second line, leaving >b' unchanged. > >But... what if before this interaction, the int >thread and the bool thread were separate monads >doing their own thing, and we just wanted to >combine these threads briefly (using the above >interaction) before letting the threads do their >own thing again? Is this possible? > >Also, suppose we have previously defined an int thread >monad which takes i, returns a value of i `mod` 2, >and changes the state to i' = i `div` 2. Suppose >also we have previously defined a bool thread >monad which takes b, returns a nothing value, and >changes the state to b' = not b. Can we use >these two monads (each acting on different >threads), to form a combined-interaction monad >that does (same as before): > > b' = not (b && (i `mod` 2)) > i' = i `div` 2 > >I hope this is possible. It would facilitate >both code reuse and readability. However I >fear that it is not, requiring one to instead >explicitly rewrite the two separate thread monads >into (Int, Bool) pair acting ones. > >Cheers, > >Mark. > > >_______________________________________________ >Haskell mailing list >Haskell(a)haskell.org >http://www.haskell.org/mailman/listinfo/haskell ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

3 2

Type checking
by Lee Dixon 09 Jan '04

09 Jan '04

Hi, Can anyone explain to me how hugs manages to derive that f x y z = y (y z) x is of type f :: a -> ((a -> b) -> a -> b) -> (a -> b) -> b Many thanks and a happy new year to all! Lee _________________________________________________________________ Stay in touch with absent friends - get MSN Messenger http://www.msn.co.uk/messenger

3 2

RE: Help!!!!
by Garner, Robin 09 Jan '04

09 Jan '04

It looks like the only data structure you use here is a list, which has an access time of O(n). Perhaps if you used a log(n) data structure (like a FiniteMap) or a constant structure (like an array) the runtime might improve. It's difficult to see from your program exactly what the algorithm you're using is. Or even how to run it. Have you done an analysis of its time complexity ? cheers -----Original Message----- From: Bhrein Brannick [mailto:bhrein_brannick@hotmail.com] Sent: Friday, 09 January, 2004 3:25 AM To: haskell-cafe(a)haskell.org Subject: Help!!!! Hi Guys, I'm a fourth year computer science in Ireland and I'm doing my final year project on Haskell programming. What I'm doing is writing a program in Haskell for the maths department for my college. What it involves is this: There is a class of 50 students and there are about 25 staff members. Now some staff member's take on three students, two students or even just one student depending on the staff member for supervising students. The students rank the projects the staff members have on offer in order of preference from 1 to 4 (see Haskell code in mail attachment). The program finds the best assignment of projects for students based on their ranking. The program works fine and that but my problem is that it takes way too much time to execute the program. When I reduced class number to 10 students and only included 10 staff for allocation projects it took thirty seconds to execute. That was fine. But when I increased class number to 20 students it took 10 minutes to execute. I tried it once for a class of 50 students and I wouldn't let it finish since it was taking far too long. I'm just wondering is there any way that the program can be improved so that execution of program can be faster. Even if there were software available that makes Haskell programs runs faster that would be a great help. I have a presentation in this, which I have only ten minutes to show the department what I'm talking about, and I want to include a demonstration of the program in it. Can you please help me with this since I tried a number of things with this and it never once seemed to improve performance. Thank you, Bhrein Brannick, Maths department, NUI Galway, Ireland. <http://graphics.hotmail.com/emsmile.gif> beano #7 <http://www.music.com/> _____ The new MSN 8: <http://g.msn.com/8HMAEN/2737??PS=> smart spam protection and 2 months FREE*

1 0

Re: Help!!!!
by Thomas Davie 09 Jan '04

09 Jan '04

> <html><div style='background-color:'><P>Hi Guys,</P> > <P>Im a fourth year computer science in Ireland and Im doing my > final year project on Haskell programming. What Im doing is writing a > program in Haskell for the maths department for my college. What it > involves is this: There is a class of 50 students and there are about > 25 staff members. Now some staff members take on three students, two > students or even just one student depending on the staff member for > supervising students. The students rank the projects the staff members > have on offer in order of preference from 1 to 4 (see Haskell code in > mail attachment). The program finds the best assignment of projects > for students based on their ranking. The program works fine and that > but my problem is that it takes way too much time to execute the > program. When I reduced class number to 10 students and only included > 10 staff for allocation projects it took thirty seconds to execute. > That was fine. But when I increased class number to 20 students it > took 10 minutes to execute. I > tried it once for a class of 50 students and I wouldnt let it > finish since it was taking far too long. Im just wondering is there > any way that the program can be improved so that execution of program > can be faster. Even if there were software available that makes > Haskell programs runs faster that would be a great help. I have a > presentation in this, which I have only ten minutes to show the > department what Im talking about, and I want to include a > demonstration of the program in it. Can you please help me with this > since I tried a number of things with this and it never once seemed to > improve performance. </P> One thing you might consider is whether or not it needs to run that fast - what happens if a student runs out of project choices? Do they need to pick new choices? We have a similar system here at York, and it ends up taking several days to run because students have to modify their choices to allow it to work. I've snipped your code and ignored it, because I'm guessing that your uni's rules on collusion are as strict as they are here, and they wouldn't be too chuffed if I were to give you a hand with it. Hope this helps Bob

1 0