February 2001 - Haskell

Tree handling
by Martin Gustafsson 27 Feb '01

27 Feb '01

Hello I'm a haskell newbie that tries to create a tree with arbitary numbers of childs. I create the data structure but i can't do anything on it can someone please help me with a small function that sums the values of the leafs, so i don´t loose my hair so fast. The datastructure looks like this and a binary tree built with it would look like this: data GeneralTree = Nil | Node (Integer,[GeneralTree]) tree = (20, [ (-20,[(30,[Nil]),(20,[Nil])]), (40,[(65,[Nil]),(-40,[Nil])]) ] ) Best regards Martin Gutsfsson

2 1

Re: Proposal: module namespaces.
by Ketil Malde 27 Feb '01

27 Feb '01

Malcolm Wallace <Malcolm.Wallace(a)cs.york.ac.uk> writes: > Proposal 1 > ---------- > Introduce nested namespaces for modules. The key concept here is to > map the module namespace into a hierarchical directory-like structure. > * The use of qualified imports becomes more verbose: for instance [...] > instance, either the fully-qualified or abbreviated-qualified names > Text.Xml.Parse.element > Parse.element > would be accepted and have the same referent, but a partial > qualification like > Xml.Parse.element > would not be accepted. Why not? Perhaps one could have a warning/error if there are multiple "Parse" modules? > * Another consequence of using the dot as the module namespace > separator is that it steals one extremely rare construction from > Haskell'98: [...] > No-one so far thinks this is any great loss, and if you really > want to say the latter, you still can by simply inserting spaces: > A.B . C.D Personally, I'm not overly enthusiastic about using (.) for function composition - but I guess e.g the degrees sign was ruled out since it's not in (7bit) ASCII - and I think it should require spaces anyway, in order to differentiate it from its other uses. > Proposal 2 > ---------- > Adopt a standardised namespace layout to help those looking for or > writing libraries, and a "Std" namespace prefix for genuinely > standard libraries. (These are two different things.) Sounds good! -kzm -- If I haven't seen further, it is by standing in the footprints of giants

1 0

Re: foldl, tail recursion, and strictness (was: stack overflow)
by George Russell 26 Feb '01

26 Feb '01

I know it's complete heresy to say so, but I use laziness very little in Haskell, while I probably pay quite a lot for it in CPU time and memory, because of all those thunks which have to be stored. However I prefer Haskell's type classes, syntax and purity to, say, Standard ML. So I wonder whether there ought to be a language "Strict Haskell", in the same way as someone implemented "Lazy ML" . . .

1 0

Re: foldl, tail recursion, and strictness (was: stack overflow)
by Ketil Malde 26 Feb '01

26 Feb '01

"C.Reinke" <C.Reinke(a)ukc.ac.uk> writes: > So foldl is indeed tail recursive, but this doesn't help if its > operator isn't strict because the tail recursion only builds up the > expression to be evaluated. Making strictness explicit by defining a > variant of foldl that evaluates its accumulator at each step helps to > solve the problem and documents programmer intentions. > This is quite common a trap for Haskellers to fall into It makes me wonder if it's common enough that strict foldl should be the default? Are there (many) cases where a partial foldl makes sense? -kzm -- If I haven't seen further, it is by standing in the footprints of giants

1 0

recip for Ratio
by Scott Turner 26 Feb '01

26 Feb '01

In the Haskell 98 Library Report, recip is defined for the Ratio type as: recip (x:%y) = if x < 0 then (-y) :% (-x) else y :% x Is it intentional that recip (0 % 1) is not an error? Everywhere else the denominator is forced to be positive. Infinity can be a useful number, if the type is consistent about it. -- Scott Turner p.turner(a)computer.org http://www.billygoat.org/pkturner

1 0

foldl, tail recursion, and strictness (was: stack overflow)
by C.Reinke 26 Feb '01

26 Feb '01

"Julian Assange" <proff(a)iq.org>: > .. > | When used with a 170k input file, makemap suffers from a stack > | overflow. foldl should be tail recursive. What's the score? "Simon Peyton-Jones" <simonpj(a)microsoft.com>: > Consider > foldl (+) 0 [x1,x2,x3,x4,... > > This rewrites to > > foldl (+) (0 + x1) [x2,x3,x4,...] > => foldl (+) (0 + x1 + x2) [x3,x4,...] > => foldl (+) (0 + x1 + x2 +x3) [x4,...] > > And so on. So we build up a giant chain of thunks. > Finally we evaluate the giant chain, and that builds up > a giant stack. So foldl is indeed tail recursive, but this doesn't help if its operator isn't strict because the tail recursion only builds up the expression to be evaluated. Making strictness explicit by defining a variant of foldl that evaluates its accumulator at each step helps to solve the problem and documents programmer intentions. This is quite common a trap for Haskellers to fall into (and was certainly already considered well-known when I first saw it;-), so it might be worth documenting it somewhere, and mentioning it in introductory courses. <plug> You can see some of this using GHood http://www.cs.ukc.ac.uk/people/staff/cr3/toolbox/haskell/GHood/ The three folds over lists (foldr, foldl, foldl') are one of the online examples for GHood (in fact, foldl was mentioned as an example of the potential use for animated observations in Andy Gill's Hood paper). If you stop the animation of the foldl example somewhere around step 40 (of 66), you can see that the spine of the input list has been observed completely(!), and the functional parameter has been applied once for each list element, but none of the applications has yet returned an observable result. Instead, a long chain of yellow nodes indicates that the observation of the end result depends on several intermediate computations (such chains roughly indicate stack usage). The next step will observe the second parameter to foldl, and from then on the chain unwinds again, and only then the elements of the input list will be observed.. </plug> > Why can't GHC evaluate as it goes? Because it's only > correct to do so if the function is strict in its second argument, ..first argument..?-) foldl (\x y->y) (error "don't touch!") [1/0,2/0,3/0,4] => 4.0 Hth, Claus

1 0

Lectureships in Nottingham
by Graham Hutton 26 Feb '01

26 Feb '01

Dear all, We are currently advertising for new lecturers in Nottingham. There are no particular research areas specified for these positions, but applications in the area of the Languages and Programming research group (http://www.cs.nott.ac.uk/Research/lap/) would be most welcome. The closing date for applications is Friday 16th March 2001. Graham Hutton ---------------------------------------------------------------------- THE UNIVERSITY OF NOTTINGHAM School of Computer Science and Information Technology Lecturers Applications are invited for the above posts in a rapidly-expanding School based at one of the UK's strongest research-led universities. The School was graded 4 in the 1996 Research Assessment Exercise and is now building up its research strengths for a further improvement in grade. These posts are part of a steady increase in the size of the School, which moved to new purpose-built accommodation in September 1999. Although the successful candidates will have the opportunity of teaching within their specialist area at undergraduate and postgraduate level, there will also be a requirement to teach general computer science and information technology modules outside of any particular specialisation. Candidates should already have a PhD in computer science, or another closely related discipline, together with strong evidence of existing research work and the potential for future research at Grade 5 level. Outstanding candidates will be welcomed from any area of computer science. Salary will be within the range #18,731 - #30,967 per annum, depending on qualifications and experience. Informal enquiries may be addressed to Professor P H Ford, Head of School, tel: +44 (0)115 951 4251 or Email: Peter.Ford(a)Nottingham.ac.uk. Further information about the School is available on the WWW at: http://www.cs.nott.ac.uk. Further details and application forms are available from the Personnel Office, Highfield House, The University of Nottingham, University Park, Nottingham, NG7 2RD. Tel: +44 (0)115 951 5927. Fax: +44 (0)115 951 5205. Email: Carole.Matthews(a)Nottingham.ac.uk. Please quote ref. LEG/548. Closing date: 16 March 2001. ----------------------------------------------------------------------

1 0

RE: stack overflow
by Simon Peyton-Jones 26 Feb '01

26 Feb '01

Consider foldl (+) 0 [x1,x2,x3,x4,... This rewrites to foldl (+) (0 + x1) [x2,x3,x4,...] ==> foldl (+) (0 + x1 + x2) [x3,x4,...] ==> foldl (+) (0 + x1 + x2 +x3) [x4,...] And so on. So we build up a giant chain of thunks. Finally we evaluate the giant chain, and that builds up a giant stack. Why can't GHC evaluate as it goes? Because it's only correct to do so if the function is strict in its second argument, which (+) is, and so is addToFM. If GHC were to inline foldl more vigorously, this would happen. Maybe we should make it do so, to avoid gratuitous leaks. Simon | -----Original Message----- | From: Julian Assange [mailto:proff@iq.org] | Sent: 24 February 2001 10:50 | To: haskell(a)haskell.org | Cc: proff(a)iq.org | Subject: stack overflow | | | -- compile with: | -- ghc -i/usr/lib/ghc-4.08.1/imports/data -lHSdata | -fglasgow-exts -O -fglasgow-exts wordfreq.hs -o wordfreq | module Main where | import List | import Char(toLower) | import FiniteMap(fmToList,emptyFM,addToFM,lookupWithDefaultFM) | | main = interact (unlines . pretty . sort . fmToList . | makemap . words . lower) | where | pretty l = [w ++ " " ++ show n | (w,n) <- l] | sort = sortBy (\(_,n0) (_,n1) -> compare n0 n1) | makemap = foldl f emptyFM | where | f fm word = addToFM fm word (n+1) | where | n = lookupWithDefaultFM fm 0 word | lower = map toLower | | | | When used with a 170k input file, makemap suffers from a stack | overflow. foldl should be tail recursive. What's the score? | | Julian | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell |

1 0

Lo mejor de Internet aqu�
by promocionesdosmiluno＠yahoo.es 25 Feb '01

25 Feb '01

Visita esta web http://MundoEspanya.redireccion.com

1 0

stack overflow
by Julian Assange 24 Feb '01

24 Feb '01

-- compile with: -- ghc -i/usr/lib/ghc-4.08.1/imports/data -lHSdata -fglasgow-exts -O -fglasgow-exts wordfreq.hs -o wordfreq module Main where import List import Char(toLower) import FiniteMap(fmToList,emptyFM,addToFM,lookupWithDefaultFM) main = interact (unlines . pretty . sort . fmToList . makemap . words . lower) where pretty l = [w ++ " " ++ show n | (w,n) <- l] sort = sortBy (\(_,n0) (_,n1) -> compare n0 n1) makemap = foldl f emptyFM where f fm word = addToFM fm word (n+1) where n = lookupWithDefaultFM fm 0 word lower = map toLower When used with a 170k input file, makemap suffers from a stack overflow. foldl should be tail recursive. What's the score? Julian

1 0