January 2002 - Haskell-Cafe

memoization hints?
by Feuer 18 Jan '02

18 Jan '02

It seems that under some circumstances it might be good for a programmer to be able to tell the implementation not to remember something. In particular, intermediate data structures may be remembered for much longer than they should be. If I am not mistaken, full laziness (which I think ghc uses with -O ?) can make this worse. Would it be beneficial to have some kind of annotations to help deal with this? I don't really know how it would be implemented. Take a standard sort of example: fib n = let f = 0:1:zipWith (+) f (tail f) in f !! n -- code that first calculates fib 1000, then fib 3, fib 4, then does some other stuff I believe that the entire list will be maintained (when compiled with ghc -O) after calculating fib 1000, despite the fact that it will never be used again. If I could say instead fib n = let forget f = 0:1:zipWith (+) f (tail f) in f !! n and somehow get it to forget about f as often as possible (somehow suppressing laziness in this case). I would certainly want to forget about it whenever it goes out of scope, but in this case I would really want to somehow ensure that the list is never held entirely in memory (forgetting it as it is built in f !! n).

1 0

mzero
by Feuer 18 Jan '02

18 Jan '02

Why is mzero in MonadPlus rather than a separate MonadZero class?

1 0

functions not in type classes
by Cagdas Ozgenc 18 Jan '02

18 Jan '02

Greetings. Why does Haskell let you write functions that are not a part of type class? For example instead of elem :: Eq a => a -> [a] -> Bool map :: (a -> b) -> [a] -> [b] class Container a where elem :: Eq b => b -> a b -> Bool map :: (b -> c) -> a b -> a c would define methods that can work on all containers, and create a discipline to write more reusable and generic functions. Thanks

2 1

Regarding finding the number of unique elements in a list.
by Amrit K Patil ;012;VKSF6; 18 Jan '02

18 Jan '02

Hi, I am newbie at Haskell. I am not able to write a program to find the number of unique elments in a list in haskell. I am also not able to write a porgram to find the elements in the innermost list in a list within lists. Can anybody guide me as to g\how to go about it or better still send me the program. It would be of great help. Have a good day.. cheers, amrit. peace....

4 3

Re: Regarding finding the number of unique elements in a list.
by Ashley Yakeley 17 Jan '02

17 Jan '02

At 2002-01-17 15:14, Amrit K Patil ;012;VKSF6; wrote: >I am not able to write a program to find the number of unique elments in a >list in haskell. Have a look in the List library for a function that finds the unique elements of a list. >I am also not able to write a porgram to find the elements in the >innermost list in a list within lists. Well, this you'll have to do yourself. -- Ashley Yakeley, Seattle WA

1 0

Precision of `Double's in Hugs
by Liyang Hu 17 Jan '02

17 Jan '02

Hi, (I'm just a new convertee to the ways of Functional Programming, so please go easy on me! ^_^;;) Why is it that `Double's in Hugs only seem to have the same precision as a `Float'? I've some code here that only iterates a few hundred times, and the amount of accuracy lost is getting a bit ridiculous ... Exactly[0] the same code produces the much more accurate results in GHCi. I'd switch over, but at the very least I'd like to know why this is happening. BTW: From the description at http://haskell.cs.yale.edu/communities/ , I seem to get the impression that haskell(a)haskell.org should only be used for announcements, yet the archive shows quite a bit of general discussion going on. Should I have posted this to the aforementioned list as well / instead? /Liyang [0] Minus the non-Haskell 98 compliant bits, like the missing fromInt ... -_- Took me a while to figure that one out. -- .--| Liyang Hu |--| http://nerv.cx/ |--| Caius@Cam |--| ICQ: 39391385 |--. | A [programming] language that doesn't affect the way you think | | about programming is not worth knowing. |

5 6

newtype/datatype (was efficiency)
by Iavor Diatchki 17 Jan '02

17 Jan '02

hello, it looks like a lot of Haskell experts are at POPL (prog. language conference) and are not checking their email... so here is my attempt at explaining the differences between data and newtype. data T -- has 1 vale: _|_ data T = T -- has 2 values: _|_, T data T = T () -- has 3 values: _|_, T _|_, T () newtype T = T () -- has 2 values: _|_, T () basically the "data" declaration in Haskell "lifts" a type, by adding a new _|_ element. the reason for this is that in general a data may have different shapes (hence the constructors) and while trying to make a value of the type one might non-terminate before they computed what constructor should be applied. the annoying thing is that this happens even for datatypes which dont have different shapes, i.e. data declarations with only one different shape. Even if there is only one possible shape we always remember the shape (constructor) in the representation and when pattern matching check to see if the value is of this shape. i dont know why. to (kind of) avoid this, if you have a datatype with only one shape and one field you should use a newtype. unfortunatelly if you have multiple fields you are stuck with the additional _|_. i dont think there should be any difference in efficiency between: data P a b = P a b and newtype P a b = P (a,b) unless there are some hard-coded tuple specific optimizations done by the current implementations. i cannot see any reasons why these optimizations shouldnt happen for the data declarartion as well (i am not experienced compiler writer however...) which of the above is better is a matter of personal preference - i prefer the 1st one as i think it leads to more readable patterns. finaly there was the question about strictness annotations - they seem to be quite orthogonal to the whole newtype/data issue and enable you to specify that some constructors of your datatype are strict - i.e. when you construct something with a strict constructor it will first be evalued (until it becomes a function or an application of a lazy constructor to some arguments) and only then will the disired value be created. since this evaluation might not terminate of course, some "different" values in the lazy version of the datatype all collapse to teh same thing. so in some sense newtype makes things more lazy, while ! makes them more eager. sorry for the long email hope it helped iavor -- ---------------------------------------+---------------------------------------- Iavor S. Diatchki | email: diatchki(a)cse.ogi.edu Dept. of Computer Science | web: http://www.cse.ogi.edu/~diatchki OGI School of Science and Engineering | work phone: 5037481631 OHSU | home phone: 5036434085 ---------------------------------------+----------------------------------------

6 5

monad binding and garbage collection
by Christian Schuhegger 17 Jan '02

17 Jan '02

hi all, i'm new to haskell and i have a question on a general problem concerning monad binding and garbage collection. my question will be on how to approach this type of problem? consider the following simple program: >------ buildIOList :: [a] -> IO [a] buildIOList li = return li main = do {li <- buildIOList [1..]; putStr (show (take 100000000 li)); } <------ if i compile this program with ghc and run it it has constant memory usage because of the lazy nature of haskell. on the other hand if i use runhugs then i get: ERROR - Garbage collection fails to reclaim sufficient space i think this is because the compiler can examine the code and sees that the binding li is not used after putStr any more and therefore the garbage collector can safely collect all the list elements that were already put onto the screen, but hugs as a interpreter does not have this knowledge and therefore has to keep all the memory that the binding li refers to. if i modify this program a bit: >------ main = do {li <- buildIOList [1..]; putStr (show (take 100000000 li)); putStr (show (take 100000000 li)); } <------ i get the same memory problem with a ghc compiled file, because now all the cells in the list bound by li that are evaluated stay in the system, because the gc cannot collect them as the third line in the do expression uses li again. with a little modification: >------ main = do {li <- buildIOList [1..]; putStr (show (take 100000000 li)); li <- buildIOList [1..]; putStr (show (take 100000000 li)); } <------ the program has again constant memory usage, because the name li is bound again later in the program so the gc can collect the elements of the first li. again a modification would be: >------ buildIOList :: [a] -> [IO a] buildIOList [] = [] buildIOList (hd : tl) = (return hd) : buildIOList tl main = do {printString (buildIOList [1..]); printString (buildIOList [1..]); } printString :: Show a => [IO a] -> IO () printString [] = return () printString (hd : tl) = do {c <- hd; putStr (show c); printString tl} <------ this program has also constant memory usage, but here i have to modify a lot to propagate the "little bits of monads" in the program. my question is now how an experienced haskell programmer would attack the problem? i would also like to have a solution that works for hugs so that my code is independent of the environment it is run in. many thanks for any suggestions! -- Christian Schuhegger The most likely way for the world to be destroyed, most experts agree, is by accident. That's where we come in; we're computer professionals. We cause accidents. -- Nathaniel Borenstein

2 1

Re: efficiency
by Marcin 'Qrczak' Kowalczyk 16 Jan '02

16 Jan '02

Tue, 15 Jan 2002 13:06:58 +0100, Rijk-Jan van Haaften <rjchaaft(a)cs.uu.nl> pisze: > This feature is one I consider among the worst in Haskell. If > a datatype with just a single constructor can be optimized away, It can't. newtype has a different semantics than data, as others explained. It would be weird if data had non-uniform semantics for the one-constructor-with-one-field case, even though usually newtype is the variant we prefer. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ QRCZAK

1 0

efficiency
by Feuer 16 Jan '02

16 Jan '02

In http://www.cs.columbia.edu/~cdo/icfp99.ps Okasaki does a couple things I'm not sure I quite understand: He has a datatype newtype Empty a = E () I cannot for the life of me figure out why he didn't just do data Empty a = E The other weird thing was: newtype Pair v w a = P (v a, w a) I can't see why he didn't do data Pair v w a = P (v a) (w a) I was wondering if anyone on this list knew of any reasons the types he chose would be more efficient than mine.... David

4 4