- Haskell-Cafe - Haskell.org

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

Re: how do you debug programs?
by Johan Tibell 06 Sep '06

06 Sep '06

Note: I meant to send this to the whole list a couple of messages ago but accidentally I only sent it to Lennart, sorry Lennart! I know that Linus Torvalds doesn't find debuggers all that useful either and he hacks C [1]. 1. http://linuxmafia.com/faq/Kernel/linus-im-a-bastard-speech.html On 9/6/06, Lennart Augustsson <lennart(a)augustsson.net> wrote: > I've also used Visual Studio, and I wouldn't mind having something > like that for Haskell. But I have to agree with Jon, I think the > best way of debugging is to understand your code. I think people who > come from imperative programming come with a mind set that you > understand your code by stepping through it in the debugger. But I > find this paradigm much less useful for functional code. > > -- Lennart > > On Sep 6, 2006, at 06:22 , Neil Mitchell wrote: > > > Hi > > > >> But why should c and d exist at runtime? They're only used > >> once each, so the compiler is free to replace f with > >> > >> \a b -> (a+b)+ a*b > > > > Yes, and if the compiler is this clever, it should also be free to > > replace them back at debug time. > > > > > >> I've said this before, but I think it's worth repeating: in > >> most cases, if you need to debug your programme it's because > >> it's too complicated for you to understand, so the correct > >> thing to do is to simplify it and try again. > > > > That makes it impossible to ever improve - initially all programs are > > beyond you, and only by pushing the boundary do you get anywhere. As > > for me, I always write programs I can't understand, and that no one > > else can. Perhaps I understood it when I originally wrote it, perhaps > > not, but that was maybe over a year ago. > > > > It's been my experience that debugging is a serious weakness of > > Haskell - where even the poor mans printf debugging changes the > > semantics! And everyone comes up with arguments why there is no need > > to debug a functional language - that sounds more like excuses about > > why we can't build a good lazy debugger :) > > > > [Sorry for the slight rant, but I've used Visual Studio C++ so I know > > what a good debugger looks like, and how indispensable they are] > > > > Thanks > > > > Neil > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

1 0

does the compiler optimize repeated calls?
by Tamas K Papp 06 Sep '06

06 Sep '06

Hi, I have a question about coding and compilers. Suppose that a function is invoked with the same parameters inside another function declaration, eg -- this example does nothing particularly meaningless g a b c = let something1 = f a b something2 = externalsomething (f a b) 42 something3 = externalsomething2 (137 * (f a b)) in ... Does it help (performancewise) to have g a b c = let resultoff = f a b something2 = externalsomething resultoff 42 something3 = externalsomething2 (137 * resultoff) in ... 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? Thank you, Tamas PS: I realize that I am asking a lot of newbie questions, and I would like to thank everybody for their patience and elucidating replies.

11 15

installing modules
by Tamas K Papp 06 Sep '06

06 Sep '06

Hi, This is a newbie question. I found some modules on the internet that I would like to try (eg the Tim Docker's chart library [1], etc). Most of the code I see is in darcs repositories, I figured out how to get them, but I don't know how to install it _cleanly_. Cleanly means that it ends up in the "right" directory. How do people usually do that? I am using ghc6 on debian testing. Am I supposed to use the thing called "cabal"? Is it perhaps possible to create a debian package from sources that were packaged with this tool? Thank you, Tamas [1] http://dockerz.net/software/chart.html

2 1

[Parsec] No identEnd in ParsecToken?
by Stephane Bortzmeyer 06 Sep '06

06 Sep '06

I'm trying to use Parsec for a language which have identifiers where the '-' character is allowed only inside identifiers, not at the start or the end. ParsecToken has identStart to tell that the '-' is not allowed at the start but I find no equivalent identEnd? I tried also to express the same rule with ordinary combinators, without ParsecToken but this fails: identifier = do start <- letter rest <- many (alphaNum <|> char '-') end <- letter return ([start] ++ rest ++ [end]) <?> "characters authorized for identifiers" because the parser created by "many" is greedy: it consumes everything, including the final letter. Any idea?

5 6

Exercise in point free-style
by Julien Oster 06 Sep '06

06 Sep '06

Hello, I was just doing Exercise 7.1 of Hal Daumé's very good "Yet Another Haskell Tutorial". It consists of 5 short functions which are to be converted into point-free style (if possible). It's insightful and after some thinking I've been able to come up with solutions that make me understand things better. But I'm having problems with one of the functions: func3 f l = l ++ map f l Looks pretty clear and simple. However, I can't come up with a solution. Is it even possible to remove one of the variables, f or l? If so, how? Thanks, Julien

9 16