- Haskell-Cafe - Haskell.org

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

foldr
by James Ealing 02 Jan '04

02 Jan '04

Hi all, If I have a function: it f [a0, a1, a2, ...] = [a0, f a1, f (f a2), ...] Is there any way of expressing it f as an instance of foldr? Many thanks, Jim ________________________________________________________________________ Yahoo! Messenger - Communicate instantly..."Ping" your friends today! Download Messenger Now http://uk.messenger.yahoo.com/download/index.html

2 1

Parsing library
by James Ealing 02 Jan '04

02 Jan '04

I'm trying to make use of the combinatorial parsing library to process strings. However, I can't figure out the correct syntax for the (|||) (^^^) (>>>) (<^^) and (^^>) functions. Can anyone see how to do it? If so it'd be really useful if you could put down a couple of examples of how each is used. Thanks Jim The library: Generic parsing functions >module Parse ( > Parse, succeed, token, spot, > (|||), (^^^), (<^^), (^^>), (>>>), > many, listOf, topLevel, > white, ws, parseVar, word, parseNum) >where --------------------------------------------------- -- Combinatory parsing library using Maybe types -- -- suitable for non-ambiguous grammars. -- -- sja4(a)mcs.le.ac.uk (21/10/96) -- --------------------------------------------------- >infixr 5 `into`, ^^^, <^^, ^^> >infixl 4 >>> >infixr 3 ||| Maybe defined in prelude: data Maybe a = Just a | Nothing --------------------- -- Type of parsers -- --------------------- >type Parse a = String -> Maybe (a, String) ------------------- -- Basic parsers -- ------------------- Succeed with the value given. >succeed :: a -> Parse a >succeed val inp = Just (val, inp) Recognize a specified token at the head of the input. >token :: Char -> Parse Char >token t (u:x) = if t == u then Just (t,x) else Nothing >token t [] = Nothing Recognize a token with a certain property. >spot :: (Char -> Bool) -> Parse Char >spot p (t:x) = if p t then Just (t,x) else Nothing >spot p [] = Nothing ------------------------- -- Parsing combinators -- ------------------------- A choice between two parsers. The function p1 ||| p2 returns the result of p1 whenever it succeeds and the result of p2 otherwise. >(|||) :: Parse a -> Parse a -> Parse a >(p1 ||| p2) inp = case p1 inp of > Nothing -> p2 inp > Just (v,x) -> Just (v,x) Sequencing of parsers. The function p1 ^^^ p2 returns the result, if any, of applying p1 to the input and then p2 to the remainder. >(^^^) :: Parse b -> Parse c -> Parse (b,c) >(p1 ^^^ p2) inp = > case p1 inp of > Nothing -> Nothing > Just (v,x) -> case p2 x of > Nothing -> Nothing > Just (u,y) -> Just ((v,u),y) Semantic action. The results from a parser p are transformed by applying a function f. >(>>>) :: Parse b -> (b -> c) -> Parse c >(p >>> f) inp = case p inp of > Nothing -> Nothing > Just (v,x) -> Just (f v, x) Sequencing of parsers, choosing one component or the other >(<^^) :: Parse b -> Parse c -> Parse b >p <^^ q = (p ^^^ q) >>> fst >(^^>) :: Parse b -> Parse c -> Parse c >p ^^> q = (p ^^^ q) >>> snd Repetition. The parser p is used as many times as possible and the results are returned as a list. >many :: Parse b -> Parse [b] >many p = ((p ^^^ many p) >>> cons) ||| (succeed []) >cons (x,xs) = x:xs ListOf p c applies parser p as many times as possible, with the instances separated by instances of c, and returns the result as a list. >listOf :: Parse b -> Char -> Parse [b] >listOf p sep = p ^^^ many (token sep ^^> p) >>> cons The top level parser is a function which maps a list of tokens to a value. A value p :: Parse a b can be converted to such a function by applying topLevel: >topLevel :: Parse b -> String -> b >topLevel p inp > = case p inp of > Just (result,[]) -> result > Just (result,rest) -> > error ("parse unsuccessful; input unconsumed:"++show rest) > other -> error "parse unsuccessful" Note there is an error if the input is not fully consumed. It is sometimes useful to test whether a given parser will accept the input without actually returning a result. >acceptedBy :: Parse b -> String -> Bool >acceptedBy parser inp > = case parser inp of > Just (result,[]) -> True > other -> False A more sophisticated form of sequencing. The into combinator allows the second parser to be chosen according the result of the first. >into :: Parse b -> (b -> Parse c) -> Parse c >into p f inp = case p inp of > Nothing -> Nothing > Just (v,x) -> f v x ========================================================================== Absorb white space >white = many (token ' ' ||| token '\t') >ws p = white ^^> p <^^ white ========================================================================== Consume and return variable: must start with small letter, and continue with alphanumberic characters >parseVar :: Parse String >parseVar = spot isLower ^^^ many (spot isAlphaNum) >>> cons Consume and return particular word >word :: String -> Parse String >word [c] = token c >>> (\ c -> [c]) >word (c:cs) = (token c ^^^ word cs) >>> cons Consume and return number >parseNum :: Parse Int >parseNum = spot isDigit ^^^ many (spot isDigit) >>> mknum > where mknum (d, ds) = foldl f (digitToInt d) ds > f n d = 10*n + digitToInt d ________________________________________________________________________ Yahoo! Messenger - Communicate instantly..."Ping" your friends today! Download Messenger Now http://uk.messenger.yahoo.com/download/index.html

2 1