- Haskell-Cafe - Haskell.org

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

09 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 08 Jan '04

08 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

Help!!!!
by Bhrein Brannick 08 Jan '04

08 Jan '04

2 1

HSQL Linking Problem with ghc6
by Charles Perkins 06 Jan '04

06 Jan '04

Hello Haskellians, I have been looking for a way to get ghc-compiled haskell programs to talk to a PostgreSQL database, and HSQL seems to be exactly what I need... And what's more, it appears to have downloaded and installed with minimal hassle... Alas (and I am sure this is a problem with my own lack of knowledge or misconfiguration of my system) I can't get ghc to link my program to the HSQL libHSSql.a library. At least I think that is the problem. On my debian-stable system, with some packages and libraries upgraded to -testing so I could install ghc6, I downloaded HSQL 1.0 from sourceforge and then ./configured with --enable-postgress and told it to make and then make -install the HSQL package. When I put an import HSQL statement in my program ghc compiles it without errors but the Linking phase reports the following (my program name is EnvPassed:) Linking ... EnvPassed.o: In function `__stginit_main_': EnvPassed.o(.text+0x25): undefined reference to `__stginit_HSQL_' Collect2: ld returned 1 exit status I get the same error when I do a standard compile and when I specify the library to link to as follows: ghc --make EnvPassed.hs -o EnvPassed -lHSsql -L/software/HSQL/ (I had expanded and built HSQL in the /software directory.) Am I doing something stupid? What should I check for this kind of error? Any help would be appreciated. Chuck

3 3

Re: Perspectives on learning and using Haskell
by Derek Elkins 05 Jan '04

05 Jan '04

On Tue, 23 Dec 2003 17:26:20 +0000 Graham Klyne <gk(a)ninebynine.org> wrote: (moved to Haskell-Cafe as this reply might generate several more) > I've spent part of the past few months learning Haskell and developing > a moderately sized application. I came to this from a long background > (20 years or so) of "conventional" programming in a variety of > languages (from Fortran and Algol W to Java and Python). For me, > learning Haskell has been one of the steepest learning curves of any > new language that I have ever learned. Before this project, I was > aware of some aspects of functional programming, but had never > previously done any "in anger" (i.e. for real). Well, the obvious question is: after climbing partway up that curve, what do you think of the view? Was it worth learning? Is it worth continuing to use? Does the code seem 'better' than what you might produce in other languages you've used? > Throughout this period, I've been accumulating some notes about some > things that I found challenging along the way. The notes are not > organized in any way, and they're certainly not complete. I've > published them on my web site [1] in case the perspective might be > useful to any "old hands" here. > > [1] http://www.ninebynine.org/Software/Learning-Haskell-Notes.html When I saw this page earlier, I was thinking about suggesting to you to add it and any new thoughts to the wiki so that it's more readily accessible to other Haskell newbies and can be annotated with pointers to resources and comments; kind of like an annotated unidirectional version of "A Newbie's on-going tutorial" on the Squeak wiki (http://minnow.cc.gatech.edu/squeak/1928) > Also on the topic of perspectives: > > In recent conversation with a colleague, he mentioned to me that the > term "functional programming" has an image problem. He suggested that > the term conveys an impression of an approach that is staid, > non-progressive or lacking novelty, and is prone to elicit a response > of "been there, done that" from programmers who don't realize the full > significance of the term "functional". I've also noticed that when I > talk about "functional programming", some people tend to think I'm > talking about using techniques like functions in C or Pascal (which is > course is very desirable, but old hat and not worthy of great > excitement). Yes. People often use the term 'procedural' to describe the C style break down of a problem. Of course, some people use procedural to refer to functional and others functional to refer to procedural. Then, of course, there are also dynamic typers who equate static typing with C/Pascal. On the OO side, there are the people who equate OO with C++/Java much to the chagrin of Smalltalkers and CLOS users. At any rate, functional programming is a pretty well established term so there isn't much Haskell can do about it. Perhaps throwing in 'higher-order' will help, and certainly laziness/purity can't be said to be lacking novelty.

8 13

Limiting resources on a per-function basis?
by Jeff Newbern 05 Jan '04

05 Jan '04

Hi all, I would really like to be able to set resource limits on a per-function basis. I am envisioning something like: limit :: l -> (a -> b) -> (a -> Maybe b) limit lim fn = ... which would convert a function so that it returns Nothing if a limit (on stack, heap, time, etc.) is exceeded during evaluation of that function. Is there any hope of being able to do this within the existing GHC libraries? If not, is it even possible to determine after-the-fact how much stack or heap space a function evaluation required? Thanks, Jeff Newbern -- Jeff Newbern <jnewbern(a)nomaware.com> Nomaware, Inc.

5 5

Stack usage with a state monad
by Joe Thornber 02 Jan '04

02 Jan '04

Hi, I was wondering if anyone could give me some help with this problem ? I'm trying to hold some state in a StateMonad whilst I iterate over a large tree, and finding that I'm running out of stack space very quickly. The simplified program below exhibits the same problem. This is the first time I've hit space problems in Haskell, I hope judicial use of 'seq' or '$!' would be enough to fix it, but I don't know where to start. Any ideas as to what I'm doing wrong would be much appreciated. Thanks, - Joe module Main (main) where -- Program to count the leaf nodes in a rose tree. Written to try and -- reproduce a stack space leak present in a larger program. -- How can I use a state monad to count the leaves without eating all -- the stack ? import Control.Monad.State data Tree = Tree [Tree] | Leaf buildTree :: Int -> Int -> Tree buildTree order = buildTree' where buildTree' 0 = Leaf buildTree' depth = Tree $ map (buildTree') $ take order $ repeat (depth - 1) countLeaves1 :: Tree -> Int countLeaves1 (Tree xs) = sum $ map (countLeaves1) xs countLeaves1 (Leaf) = 1 incCount :: State Int () incCount = do {c <- get; put (c + 1); return (); } countLeaves2 :: Tree -> Int countLeaves2 t = execState (aux t) 0 where aux :: Tree -> State Int () aux (Tree xs) = foldr1 (>>) $ map (aux) xs aux (Leaf) = incCount main :: IO ()B main = print $ countLeaves2 $ buildTree 15 6

5 10