June 2001 - Haskell-Cafe

Re: Haskell report typo (bad law for readsPrec)
by Wolfgang Lux 20 Jun '01

20 Jun '01

Patrik Jansson wrote > [Typo - you mean:] > head (readsPrec d (showsPrec d x "")) == (x,"") Yes. > Both formulations look OK to me, but neither is an essential change and > there are many other small variations possible with slight semantical > differences. One example is > > (x,"") `elem` readsPrec d (showsPrec d x "") > > And already the current (proposed) formulation is most likely impossible > to satisfy if the element x contains bottoms somewhere inside. (Example: > try to show and read the string (undefined : "hello").) True, but in any case it seems sensible to me to require that readsPrec should actually process the input string. With your proposal > > | fst (head (readsPrec d (showsPrec d x ""))) == x it would be possible to return [(42,"42")] for the expression readsPrec 0 (showsPrec 0 42 ""). Wolfgang -- Wolfgang Lux Phone: +49-251-83-38263 Institut fuer Wirtschaftinformatik FAX: +49-251-83-38259 Universitaet Muenster Email: wlux(a)uni-muenster.de

1 0

Re: Haskell report typo (bad law for readsPrec)
by Patrik Jansson 20 Jun '01

20 Jun '01

On Tue, 19 Jun 2001, Wolfgang Lux wrote: > > > | Another simple alternative is to weaken the the equation by > > > | replacing the variable r by the empty string: [Alternative B:] > > > | > > > | ... > > > | should be the case that > > > | > > > | fst (head (readsPrec d (showsPrec d x ""))) == x > > > > > > Yes, I like this alternative too. I'll implement it. > > > > Why not require > > > > readsPrec d (showPrec d x "") == [(x,"")] > > > > in this case? At least it should be > > > > head (readsPrec d x "") == (x,"") [Typo - you mean:] head (readsPrec d (showsPrec d x "")) == (x,"") Both formulations look OK to me, but neither is an essential change and there are many other small variations possible with slight semantical differences. One example is (x,"") `elem` readsPrec d (showsPrec d x "") And already the current (proposed) formulation is most likely impossible to satisfy if the element x contains bottoms somewhere inside. (Example: try to show and read the string (undefined : "hello").) I think we'll have to accept that Show and Read are to be used mainly for presentation, and not when real uniquely invertible behaviour is desired. I think a separate Serializable class designed for correct and portable (and efficient?) data transmission is necessary anyway. In that design process the laws would have to be thought through much more carefully. (There are suggestions for a library already - see below.) /Patrik A quick search: http://www.cs.york.ac.uk/fp/nhc98/libs/Binary.html The Bits Between The Lambdas: Binary Data in a Lazy Functional Language (1998) Malcolm Wallace Colin Runciman http://citeseer.nj.nec.com/260182.html Heap Compression and Binary I/O in Haskell Malcolm Wallace Colin Runciman http://citeseer.nj.nec.com/68962.html

1 0

Re: Stack leak... (?)
by Juan Carlos Arevalo Baeza 12 Jun '01

12 Jun '01

At 11:20 AM 6/11/2001 -0600, Alastair David Reid wrote: > > The problem is that my test program runs out of stack > > (not heap) on both GHC and Hugs when parsing a large-enough > > file (about 150K for GHC, a lot less for Hugs). > >The classic cause of this problem in parsers is tracking line numbers. >The problem is that line numbers have to be built but rarely get >observed. This means that a line number like 33 will be represented >by a thunk like this: > > 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1 > >This uses a lot of heap space (though it may not be too bad because of >sharing) but, more seriously, it takes stack space proportional to the >line number - hence the stack overflows you've been seeing. Thanx! That makes sense, kind of. I'm still not sure why the hit is in the stack. I guess the stack must be used in a different manner than in the lazy evaluator I programmed not long ago in C++ (it was a learning experience). In that evaluator, a line number represented like that would be just one more heap token/pointer stored in the stack, regardless of the internal complexity of the expression. Unless the stack overflow happens on evaluating the line number for printing it out. But then, in my evaluator, it would have been the previous line number plus one, and the previous line number would have been computed already when printing the previous line of code. Hmmm... Do you think I have to re-evaluate what I know of the internals of how Haskell works? Thanx for your help. Salutaciones, JCAB --------------------------------------------------------------------- Juan Carlos "JCAB" Arevalo Baeza | http://www.roningames.com Senior Technology programmer | mailto:jcab@roningames.com Ronin Entertainment | ICQ: 10913692 (my opinions are only mine) JCAB's Rumblings: http://www.metro.net/jcab/Rumblings/html/index.html

1 0

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

12 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 09 Jun '01

09 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 06 Jun '01

06 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 02 Jun '01

02 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