- Haskell-Cafe - Haskell.org

Derived Read instance for types with infix constructors (ghc 6.4.1)
by Misha Aizatulin 09 Sep '06

09 Sep '06

hi, the Haskell Report 10.4 says that "The result of show is readable by read if all component types are readable" however if I define a type like data T = A | T `And` T deriving (Read, Show) then *Main> show $ A `And` A "A And A" *Main> (read "A And A") :: T *** Exception: Prelude.read: no parse *Main> In fact, I wasn't able to guess, what I should type so that the value (A `And` A) gets parsed. I have ghc 6.4.1. Looking into the code of the derived instance I see that it expects Text.Read.Lex.lex to return (Symbol "And") for the constructor. If I understand the code for lex correctly, then it parses things as Symbol if they consist only of "!@#$%&*+./<=>?\\^|:-~" How then do I read values of type T defined above? Thanks in advance for any directions. Cheers, Misha

7 12

[Newbie] Cannot derive Eq and Show. Why?
by Peter Arrenbrecht 09 Sep '06

09 Sep '06

Hi all I am stumped again. The following code generates the error "ERROR file:.\Cube.hs:12 - An instance of IArray UArray a is required to derive Eq (Cube a b)" in Hugs. But I did specify the IArray UArray k constraint. So what is wrong? module Cube( Cube(..) ) where import Data.Array.Unboxed data (Ord k, IArray UArray k, IArray UArray v) => Cube k v = Empty | Values (UArray Int k) (UArray Int v) | Subs (UArray Int k) (Array Int (Cube k v)) deriving (Show, Eq) Thanks for any help -peo -- View this message in context: http://www.nabble.com/-Newbie--Cannot-derive-Eq-and-Show.-Why--tf2239265.ht… Sent from the Haskell - Haskell-Cafe forum at Nabble.com.

2 1

Reading integers
by Bertram Felgenhauer 08 Sep '06

08 Sep '06

Hi, prompted by a discussion about http://www.spoj.pl/problems/MUL/ on #haskell I implemented some faster routines for reading integers, and managed to produce a program that passes this problem. Currently I have a single module that provides reading operations for Integers and Ints. I'm not quite sure what to do with it. Ideally, read should use faster code for parsing numbers. This is hard to do though, because read for numbers is specified in terms of lex, which handles arbitrary tokens. One nasty side effect of this, besides bad performance, is that for example read ('"':reapeat 'a') :: Int diverges, even though there's obviously no possible parse. Incorporating faster integer reading code into read without breaking backward compatibility is not trivial. The next obvious place to put the functions is the Numeric module. This sounds like a good idea until one realizes that readSigned (which is the obvious thing to use for signed integers) again uses lex, with all the complications above. A third option is to put it all in a separate module. This would probably be hard to find, so few people would use it. I'm pondering breaking compatibility with Haskell 98 to some extent and implementing read instances for Int and Integer that don't diverge on weird inputs, but handle all valid numbers that Haskell 98 supports. This still requires some work to support octal and hexadecimal numbers, whitespace and parentheses. What do you think? The code (quite unpolished) is available with darcs get http://int-e.home.tlink.de/haskell/readinteger (browsing directly doesn't work) It also includes a simple benchmark for comparing reads, Numeric.readDec and my readInteger functions. Results for my computer are included as well. regards, Bertram

5 9

Monad laws
by Deokhwan Kim 08 Sep '06

08 Sep '06

What is the practical meaning of monad laws? (M, return, >>=) is not qualified as a category-theoretical monad, if the following laws are not satisfied: 1. (return x) >>= f == f x 2. m >>= return == m 3. (m >>= f) >>= g == m >> (\x -> f x >>= g) But what practical problems can unsatisfying them cause? In other words, I wonder if declaring a instance of the Monad class but not checking it for monad laws may cause any problems, except for not being qualified as a theoretical monad? Cheers, -- Deokhwan Kim

10 10

Does this function already exist in the libraries?
by Jason Dagit 08 Sep '06

08 Sep '06

Hello, Sometimes I find that I have two lists I want to combine, but I only want to combine them for as much as I have elements in both lists to combine and then the rest I just want to pass through unmodified. I've now found the following function useful in three different programs I've written: zipWith' :: (a -> a -> a) -> [a] -> [a] -> [a] zipWith' _ [] ys = ys zipWith' _ xs [] = xs zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys Does it already exist or maybe there is another natural solution to use in its place? Thanks, Jason

2 1

head as a total function
by oleg＠pobox.com 07 Sep '06

07 Sep '06

Jo'n Fairbairn wrote in response to Neil Mitchell: > > And as you go on to say, if you apply it to the infinite > > list, who cares if you used head. Head is only unsafe on > > an empty list. So the problem then becomes can you detect > > unsafe calls to head and let the programmer know. > No, that's the wrong approach because it relies on detecting > something that (a) the programmer probably knows already and > (b) is undecidable in general. It would be far better for > the programmer to express this knowledge in the > programme. It is indeed possible -- and quite easy -- to write programs where head and tail are total functions. That issue was discussed, for example, at the end of an old message: Exceptions in types and exception-free programming http://www.haskell.org/pipermail/haskell/2004-June/014271.html The first two thirds of the message showed how to make exceptions apparent in the signature of a function, so we can see if a function could potentially raise the `head of an empty list' exception just by looking at its (inferred) type. The exception-free programming is far more rewarding, and practical as well. We don't actually need to introduce subtyping; explicit injection/projections don't seem to be as much of (syntactic) overhead. There is absolutely no runtime overhead! The non-empty lists have exactly the same run-time representation as the regular lists. The technique generalizes to arrays, even numbers, sorted lists (and, seemingly, to strings that are safe to include into HTML/SQL documents). That technique has been mentioned several times recently (perhaps not on this forum). Quite complex algorithms like Knuth-Morris-Pratt string search (with mutable arrays, packed strings, general recursion and creative index expressions) can be handled. Again, without introducing any runtime overhead: http://pobox.com/~oleg/ftp/Haskell/KMP-deptype.hs The approach is formalizable; the recent PLPV talk by Chung-chieh Shan presented the types systems and the proof techniques. Some of the proofs have been formalized in Twelf: http://pobox.com/~oleg/ftp/Computation/lightweight-dependent-typing.html#Fo… In short, the safety property (absence of `head of an empty list' exception) is a corollary to the Progress theorem, for a type system with dependent-type flavor. The type system doesn't actually have dependent types. Furthermore, whatever dependent-type flavor there is, it can be erased while maintaining the safety guarantees, given some precisely stated conditions on the safety kernel. P.S. Algol68 was my favorite language too.

5 5

Hello Monads
by Hans van Thiel 07 Sep '06

07 Sep '06

Hello All, Being at the "Hello Monads" level, and having spent many hours on understanding the following code from YAHT, maybe this will be helpful to others. {-cross ls1 ls2 = do x <- ls1 y <- ls2 return (x,y) -} In the List Monad the value of cross is a list of pairs from the two lists. Rewriting to: {-cross ls1 ls2 = ls1 >>= \x -> ls2 >>= \y -> return (x, y) -} The actual function which gives an ordered pair is: --hf1 = (\x y -> (x,y)) In the list Monad >>= is defined as the infix of bind, and return is the same as make. bind = flip concatMap make x = [x] So now cross can be written as: --cross ls1 ls2 = ls1 `bind` (\x -> ls2 `bind` (\y -> make (x,y))) With the prefix version of bind this becomes: cross ls1 ls2 = bind ls1 (\x -> bind ls2 (\y -> make(x,y))) Bind takes a list and a function. That function still looks complicated (to me), because of the lambda abstraction, but the format is that the second bind takes the list ls2 and another function, make, which has a list of tuples as its value. The point I want to make is, that the monadic computation is just another function. The only difference is that the >== and return functions have been defined centrally in the List Monad. Moreover, the same notation has been defined in all other monads, but with different meanings, appropriate to that monad. But you can use them. Cross ls1 ls2, for example, also works in the Maybe Monad, without any change at all. So the Monad class is, in essence, no different from the Num class (or any other) where you also use predefined functions. These also will be different for the different subordinate types. Surely this is an oversimplification but, in for a dime, in for a dollar: An input procedure like getLine cannot be a function, because it will return a different value each time it is called. Putting getLine inside an IO Monad does not change this. What you can state, however, is that a certain occurrence of getLine will return a certain value. So, if you have a chain of IO actions, the first getLine will get this, the fifth that, and so on. The value of these occurrences cannot change, simply because they are uniquely identified. But this is what the monadic sequence of actions achieves, it puts all IO into a well defined chain where each action becomes unique, even though names (like getLine) on the different positions are the same. But again, the monadic computation is still a function. I'd appreciate your comments. Regards, Hans van Thiel -- Don't worry, be happy, learn Haskell.

1 0

how do you debug programs?
by Tamas K Papp 07 Sep '06

07 Sep '06

Hi, I would like to learn a reasonable way (ie how others do it) to debug programs in Haskell. Is it possible to "see" what's going on when a function is evaluated? Eg in f a b = let c = a+b d = a*b in c+d evaluating f 1 2 would output something like f called with values 1 2 c is now (+) a b => (+) 1 2 => 3 d is now (*) a b => (*) 1 2 => 2 ... Or maybe I am thinking the wrong way, and functional programming has its own debugging style... Thanks, Tamas

15 32

Re: [Haskell-cafe] does the compiler optimize repeated calls?
by John Hughes 06 Sep '06

06 Sep '06

On 9/6/06, Tamas K Papp <tpapp(a)princeton.edu> wrote: >> or does the compiler perform this optimization? More generally, if a >> function is invoked with the same parameters again (and it doesn't >> involve anything like monads), does does it makes sense >> (performancewise) to "store" the result somewhere? > > I was wondering something like this too, and then I found this email: http://www.haskell.org/pipermail/glasgow-haskell-bugs/2004-December/004530.… So I guess it is as Stephane said: theoretically possible but not actually done? --eric the perpetual newbie The trouble is that this isn't always an optimisation. Try these two programs: powerset [] = [[]] powerset (x:xs) = powerset xs++map (x:) (powerset xs) and powerset [] = [[]] powerset (x:xs) = pxs++map (x:) pxs where pxs = powerset xs Try computing length (powerset [1..n]) with each definition. For small n, the second is faster. As n gets larger, the second gets slower and slower, but the first keeps chugging along. The problem is that the second has exponentially higher peak memory requirements than the first. Round about n=25, on my machine, all other programs stop responding while the second one runs. You don't really want a compiler to make that kind of "pessimisation" to your program, which is why it's a deliberate decision to leave most CSE to the programmer. You can still write the second version, and suffer the consequences, but at least you know it's your own fault! John

2 2

getContents and lazy evaluation
by Tamas K Papp 06 Sep '06

06 Sep '06

Hi, I am newbie, reading the Gentle Introduction. Chapter 7 (Input/Output) says Pragmatically, it may seem that getContents must immediately read an entire file or channel, resulting in poor space and time performance under certain conditions. However, this is not the case. The key point is that getContents returns a "lazy" (i.e. non-strict) list of characters (recall that strings are just lists of characters in Haskell), whose elements are read "by demand" just like any other list. An implementation can be expected to implement this demand-driven behavior by reading one character at a time from the file as they are required by the computation. So what happens if I do contents <- getContents handle putStr (take 5 contents) -- assume that the implementation -- only reads a few chars -- delete the file in some way putStr (take 500 contents) -- but the file is not there now If an IO function is lazy, doesn't that break sequentiality? Sorry if the question is stupid. Thanks, Tamas

7 9