- Haskell-Cafe - Haskell.org

Re: Why is there a space leak here?
by Ketil Malde 11 Jun '01

11 Jun '01

Fergus Henderson <fjh(a)cs.mu.oz.au> writes: > If experts like Alastair Reid > have trouble understanding the operational behaviour of simplified > examples like this one, how are ordinary programmers to cope with > complicated programs? Is lazy functional programming too difficult for > ordinary mortals? Of course, you can just go the strict route, and generate the whole list before processing it. Which will blow up (since it requires an equal amount of space), but do so in a more predictable and comprehensible way. :-) -kzm -- If I haven't seen further, it is by standing in the footprints of giants

3 2

my MutableList module (If anybody cares)
by Jay Cox 08 Jun '01

08 Jun '01

Attached is my first attempt at a library containing functions for the construction and modification of "imperative lists". Such can allow for the replacement of nodes, appending, truncation, etc in constant time. (of course, all this is done through the IO or ST monad). Basically, anything you could do with lists in C (without modifying the actual node values) you can do with these lists. I'm not sure if this would be useful to anybody, (indeed I thought the idea of functional programming was to get away from this stuff!) but I would like some input as to the design of this module or other comments before I continue developing it. Could a refined version of this module (perhaps with more abstraction, name changes, and name hiding) be beneficial to the development of haskell? (Perhaps in the very least does anybody think it as a tutorial for a non-trivial use of IORef or STRef?) Thanks for your reply, Jay Cox module MutList where import IOExts import ST data S m a = Nil | Cons a (m (S m a)) class Monad m => MyRef m f where newRef :: a -> m (f a) readRef :: f a -> m a writeRef :: f a -> a -> m () -- modifyRef :: f a -> (a -> a) -> m () instance MyRef IO IORef where newRef = newIORef readRef = readIORef writeRef = writeIORef -- modifyRef = modifyIORef instance MyRef (ST s) (STRef s) where newRef = newSTRef readRef = readSTRef writeRef = writeSTRef --modifyRef = modifySTRef mkempty :: MyRef m myref => m (myref (S myref a)) mkempty = newRef Nil push ref val = newRef (Cons val ref); mpush ref val = do x<-readRef ref y<-newRef x writeRef ref (Cons val y) pop ref = do x <- readRef ref case x of (Cons _ ls) -> return ls _ -> error "empty list" mpop ref = do x<-pop ref; y<-readRef x writeRef ref y top ref = do x <- readRef ref case x of (Cons value _) -> return value _ -> error "empty list" safepop ref = do x <- readRef ref case x of (Cons _ ls) -> return (Just ls) _ -> return Nothing safempop ref = do x<-safepop ref y<-result x writeRef ref y where result Nothing = return Nil result (Just ls) = readRef ls safetop ref = do x <- readRef ref case x of (Cons value _) -> return (Just value) _ -> return Nothing -- the above could easily be replaced with versions -- which use the maybe datatype --printM :: (MyRef m myref,Show a) => (myref (S myref a)) -> m () printM x = (readRef x) >>= printM1 where printM1 Nil = print "Nil" printM1 (Cons a x) = do print "Cons " print (show a) y <- readRef x printM1 y -- this might be doable with foldM or somesuch makeM :: MyRef m myref => [a] -> m ( myref (S myref a)) makeM x = (makeM' x)>>= newRef makeM' :: MyRef m myref => [a] -> m (S myref a) makeM' [] = return Nil makeM' (x:xs) = do rest <- makeM' xs refrest <- newRef rest return (Cons x refrest) makeM1 refmaker arry = (makeM' arry) >>= refmaker makeIORefM :: [a] -> IO (IORef (S IORef a)) makeIORefM = makeM --or makeIORefM = makeM1 newIORef makeSTRefM :: [a] -> ST s (STRef s (S (STRef s) a)) makeSTRefM = makeM --or makeSTRefM = makeM1 newSTRef unmakeM :: MyRef m myref => myref (S myref a) -> m [a] unmakeM = foldrM (:) [] foldrM :: MyRef m myref => (a->b->b)->b->myref(S myref a)-> m (b) foldrM f init ref = do x<-readRef ref case x of Nil -> return init (Cons val rest) -> do value <- foldrM f init rest return (f val value) foldlM :: MyRef m myref => (b->a->b) -> b -> myref (S myref a) -> m (b) foldlM f acc ref = do x<-readRef ref case x of Nil -> return acc (Cons val rest) -> foldlM f (f acc val) rest -- cut off part of a list and replace part with another list replaceM ::MyRef m myref => myref (S myref a) -> Int -> myref (S myref a) -> m () replaceM x n y = do z <-readRef y; replaceM1 x n z replaceM1 ::MyRef m myref => myref (S myref a) -> Int -> (S myref a) -> m () replaceM1 x 0 y = writeRef x y replaceM1 x n y = do z <- readRef x case z of Nil -> do --print "cannot replace list part" writeRef x Nil (Cons a ls)-> replaceM1 ls (n-1) y truncateM x n = replaceM1 x n Nil splitwhere:: MyRef m myref => (a-> Bool) ->myref (S myref a) -> m (myref (S myref a),myref (S myref a)) splitwhere f original = something original where something l = do z <- readRef l case z of Nil -> do x1 <-newRef Nil return (original,x1) (Cons val ls) -> if (f val) then do x1 <- newRef z writeRef l Nil return(original,x1) else something ls mymapM :: MyRef m myref => (a->b) -> myref (S myref a) -> m ( myref (S myref b)) mymapM f ls = readRef ls >>= mymapM1 f where mymapM1 :: MyRef m myref => (a->b) -> (S myref a) -> m ( myref (S myref b)) mymapM1 f Nil = newRef Nil mymapM1 f (Cons x ls) = do y <-readRef ls zs <- (mymapM1 f y) newRef (Cons (f x) zs) duplicateM :: MyRef m myref => myref (S myref a) -> m (myref (S myref a)) duplicateM = mymapM id -- The following could go into another file and make another module -- data MyRef m myref => O1appendList m myref a = Lt{list::myref(S myref a),butt::myref(myref(S myref a))} makelist:: MyRef m myref => [a] -> m (O1appendList m myref a) makelist ls = do x<-mkempty t<- newRef x let p = Lt x t in m ls p where m [] p = return p m (h:t) p = do x <- m t p y<- push (list x) h return (x {list=y}) makeSTReflist :: [a] -> ST s (O1appendList (ST s) (STRef s) a) makeSTReflist = makelist makeIOReflist :: [a] -> IO (O1appendList IO IORef a) makeIOReflist = makelist listappend :: MyRef m myref => (O1appendList m myref a) -> (O1appendList m myref a) -> m () listappend l1 l2 = do end<- readRef (butt l2) middle <- readRef (butt l1) beginl2 <-readRef (list l2) writeRef middle beginl2 writeRef (butt l1) end printlist x = printM (list x) --the following function is good to get out of the state world. unmakelist x = unmakeM (list x)

1 0

Re: Why is there a space leak here?
by Fergus Henderson 05 Jun '01

05 Jun '01

David Bakin <davidbak(a)cablespeed.com> wrote: > I have been puzzling over this > for nearly a full day (getting this reduced version from my own code > which wasn't working). and Alastair Reid <reid(a)cs.utah.edu> replied: > Executive summary: David's program has an incredibly subtle space leak > in it (or I'm being incredibly dumb). I don't think you were being dumb. The space leak was easy enough to understand once explained, but I don't think it was obvious -- at any rate it was not obvious to me. I take this as another data point showing how lazy evaluation can cause space leaks that are difficult to debug. If experts like Alastair Reid have trouble understanding the operational behaviour of simplified examples like this one, how are ordinary programmers to cope with complicated programs? Is lazy functional programming too difficult for ordinary mortals? -- Fergus Henderson <fjh(a)cs.mu.oz.au> | "I have always known that the pursuit | of excellence is a lethal habit" WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.

1 0

Re: [off-topic] LaTex for [[ ... ]]
by Fergus Henderson 01 Jun '01

01 Jun '01

Sorry for the off-topic post, but I figured someone here would know... can anyone please tell me how to do the double-square-bracket symbols that are often used in denotational semantics in LaTex? It's like "[[" but a single symbol without the space between the two brackets. (I checked the Latex companion, but it's not listed there AFAICT.) -- Fergus Henderson <fjh(a)cs.mu.oz.au> | "I have always known that the pursuit | of excellence is a lethal habit" WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.

6 6

Re: [off-topic] LaTex for [[ ... ]]
by Keith Wansbrough 01 Jun '01

01 Jun '01

> Sorry for the off-topic post, but I figured someone here would know... > can anyone please tell me how to do the double-square-bracket symbols > that are often used in denotational semantics in LaTex? It's like > "[[" but a single symbol without the space between the two brackets. > (I checked the Latex companion, but it's not listed there AFAICT.) \newcommand{\lsem}{[\![} \newcommand{\rsem}{]\!]} is what I use; there are some real ones in \usepackage{stmaryrd} if you really want them. --KW 8-) -- Keith Wansbrough <kw217(a)cl.cam.ac.uk> http://www.cl.cam.ac.uk/users/kw217/ Cambridge University Computer Laboratory.

1 0

Re: Announcement: new HOpenGL Tutorial
by Sven Panne 30 May '01

30 May '01

[ redirected to haskell-cafe ] Ronald Legere wrote: > Looks great! I think the community will really > appreciate it. And I extremely appreciate it when other people write documentation for my stuff. :-) Thanks, great job! > I will have to 'give it a whirl' myself, if I can > ever get HOpenGL to compile on my solaris sparc. (I > keep having trouble with 'test' in the makefiles. I > must have a wierd version of test or something. I am no > OS guru :) (If anyone has ever seen this problem, let > me know ) Just a note: HOpenGL has been moved into GHC's fptools repository, and the tar balls on my web page are quite old. I'm not sure if they will work with more recent versions of GHC, so if you're totally stuck, join the bleeding edge and compile GHC from CVS, adding --enable-hopengl to configure's options. This builds an OpenGL package, too, but the resulting GHC doesn't know about it, so you will have to fiddle around with GHC's options a bit. Furthermore, the binding is not yet complete again, I guess about 80% has been ported. Not optimal, but I'm working on it... Alas, other Haskell systems are not yet supported, but given the recent advances in the FFI and library area, this will hopefully change in the near future. Cheers, Sven

1 0

Re: Functional programming in Python
by Marcin 'Qrczak' Kowalczyk 29 May '01

29 May '01

29 May 2001 22:44:38 +0200, Ketil Malde <ketil(a)ii.uib.no> pisze: > Wouldn't > x f g > in a Forth'ish machine mean > g(f,x) -- using "standard" math notation, for a change > rather than > g(f(x)) > ? It depends whether f changes the value at top of the stack or only puts something there. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

1 0

Re: Functional programming in Python
by Ketil Malde 29 May '01

29 May '01

Jerzy Karczmarczuk <karczma(a)info.unicaen.fr> writes: >> BTW, before I knew Haskell I exprimented with a syntax in which 'x f' >> is the application of 'f' to 'x', and 'x f g' means '(x f) g'. > Hmmm. An experimental syntax, you say... > Oh, say, you reinvented FORTH? Wouldn't x f g in a Forth'ish machine mean g(f,x) -- using "standard" math notation, for a change rather than g(f(x)) ? -kzm -- If I haven't seen further, it is by standing in the footprints of giants

2 1

Why is there a space leak here?
by Tom Pledger 29 May '01

29 May '01

David Bakin writes: : | I have been puzzling over this for nearly a full day (getting this | reduced version from my own code which wasn't working). In | general, how can I either a) analyze code looking for a space leak | or b) experiment (e.g., using Hugs) to find a space leak? Thanks! | -- Dave a) Look at how much of the list needs to exist at any one time. | -- This has a space leak, e.g., when reducing (length (foo1 1000000)) | foo1 m | = take m v | where | v = 1 : flatten (map triple v) | triple x = [x,x,x] When you consume the (3N)th cell of v, you can't yet garbage collect the Nth cell because it will be needed for generating the (3N+1)th, (3N+2)th and (3N+3)th. So, as you proceed along the list, about two thirds of it must be retained in memory. | -- This has no space leak, e.g., when reducing (length (foo2 1000000)) | foo2 m | = take m v | where | v = 1 : flatten (map single v) | single x = [x] By contrast, when you consume the (N+1)th cell of this v, you free up the Nth, so foo2 runs in constant space. | -- flatten a list-of-lists | flatten :: [[a]] -> [a] : Rather like concat? Regards, Tom

5 6

Re: Functional programming in Python
by Marcin 'Qrczak' Kowalczyk 29 May '01

29 May '01

Mon, 28 May 2001 10:23:58 +0100, Malcolm Wallace <Malcolm.Wallace(a)cs.york.ac.uk> pisze: > It seems that right-associativity is so intuitive that even the > person proposing it doesn't get it right. :-) And even those who correct them :-) >> f x (foldr1 f xs) f x foldr1 f xs > > Wouldn't the rhs actually mean f x (foldr1 (f xs)) in current notation? No: f (x (foldr1 (f xs))) Basically Haskell's style uses curried functions, so it's essential to be able to apply a function to multiple parameters without a number of nested parentheses. BTW, before I knew Haskell I exprimented with a syntax in which 'x f' is the application of 'f' to 'x', and 'x f g' means '(x f) g'. Other arguments can also be on the right, but in this case with parentheses, e.g. 'x f (y)' is a function f applied to two arguments. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

2 1