Re: [Haskell-cafe] How to write elegant Haskell programms?
I think that whole program flow thing is something you get used to. In true, pure functional programming (i.e. Haskell) program flow is a meaningless term, basically. Haskell is a declarative language, not an imperative one. You have to learn to give up that control and trust the runtime to Do The Right Thing. (In this regard it's similar to logic programming languages.) I think it's important/useful to point out that program flow in a pure functional language is really a matter of data dependency. The compiler is only free to arbitrarily order computations if there are no data dependencies. Furthermore, monads are not special in any way (they are after all just a useful set of combinators; e.g. http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html); they only wind up sequencing computations because they set up a data dependency between the two arguments of the bind operator. -Jeff And actually they don't even do that, always. A useful example in practice: then Gen monad in QuickCheck does *not* necessarily set up any data dependencies, so do in the Gen monad does not force sequencing. The fact that it's non-strict is what enables us to generate infinite random data-structures with it. John Hughes ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Debugging partial functions by the rules
From: Robert Dockins [EMAIL PROTECTED] It seems to me that every possible use of a partial function has some (possibly imagined) program invariant that prevents it from failing. Otherwise it is downright wrong. 'head', 'fromJust' and friends don't do anything to put that invariant in the program text. Well, not really. For example, I often write programs with command line arguments, that contain code of the form do ... [a,b] - getArgs ... Of course the pattern match is partial, but if itfails, then the standard error message is good enough. This applies to "throw away" code, of course, and if I decide to keep the code then I sooner or later extend it to fix the partiality and give a more sensible error message.But it's still an advantage to beABLE to write the more concise, but cruder version initially. This isn't a trivial point. We know that error handling codeis a majorpart ofsoftware cost--it can even dominate the cost of the "correct case" code (by a large factor).Erlang's "program for the correct case" strategy, coupled with good fault tolerance mechanisms, is one reason for its commercial success--the cost of including error handling code *everywhere* is avoided. Butthis means accepting that code *may*very well fail--the failure is just going to be handled somewhere else. Haskell (or at least GHC)has good exception handling mechanisms too. We should be prepared to use them, and "let it fail" when thingsgo wrong. The savings of doing so are too large to ignore. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] does the compiler optimize repeated calls?
On 9/6/06, Tamas K Papp [EMAIL PROTECTED] 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.html 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] does the compiler optimize repeated calls?
John Hughes wrote: 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! Thanks for the above example. I found it quite difficult to understand why the second is worse than the first for large n, but I think the reason is that you're using the second def in conjunction with (length). Therefore it is the *combination* of the cse'd (powerset) with (length) that is less efficient, because (length) just reads its input as a stream so there is no need for the whole of (powerset xs) to exist in memory thus the non cse'd version gives a faster (length . powerset). Yes... not just length, of course, but any function that consumes its input lazily, or perhaps I should say in one pass. For example, if you print out the result of powerset, then the print function makes only one pass over it, and the first version will run in linear space in n, while the second takes exponential. But then you'll be doing so much I/O that you won't be able to run the code for such large n in reasonable time--that's the reason I chose length in my example, it's a list consumer that isn't I/O-bound. Just to be explicit, the reason the second is worse is that the pointer to pxs from the expression map (x:) pxs prevents the garbage collector from recovering the space pxs occupies, while the pxs++ is being computed and consumed. So you end up computing all of pxs while the pxs++ is running, AND STORING THE RESULT, and then making a second pass over it with map (x:) pxs, during which pxs can be garbage collected as it is processed. In the first version, we compute powerset xs twice, but each time, every cell is constructed, then immediately processed and discarded, so every garbage collection reclaims almost all the allocated memory. Ideally it would be great if the compiler could make use of the context in which a function is being applied to produce optimized code across function boundaries. In the above example of (length . powerset), (length) has no interest in the contents of the powerset itself so could the compiler not fuse (length . powerset) into the following function: lengthPowerset [] = 1 lengthPowerset (x:xs) = 2 * lengthPowerset xs The compiler would need to analyse the definition of (++) and (map) to discover that length (x ++ y) === length x + length y length (map f y) === length y and with that knowledge I imagine the steps could be something like: lengthPowerset [] = length (powerset []) = length ([[]]) = 1 lengthPowerset (x:xs) = length (powerset xs ++ map (:x) (powerset xs)) = length (powerset xs) + length (map (:x) (powerset xs)) = length (powerset xs) + length (powerset xs) = lengthPowerset xs + lengthPowerset xs = 2 * lengthPowerset xs After getting the function (lengthPowerset) as above, I'd also expect the compiler to apply a transformation into a tail recursive function: lengthPowerset y = lengthPowerset' y 1 where lengthPowerset' [] i = i lengthPowerset' (_:xs) i = lengthPowerset' xs $! 2*i resulting in a tightly coded machine code loop to rival, or greatly exceed(!), the best efforts of C. In the meantime I tend to code in Haskell just expecting these kind of optimizations to be done (unless I'm writing a really time-critical piece of code that can't wait), knowing of course that they might not be done just at the moment but at least some time in the (hopefully not too distant) future... ;-) Regards, Brian. You know, I suspect you could get a lot of this to happen by programming GHC's optimiser using rewrite rules. But I'm going to leave it as an exercise for the reader (he he:-). For the compiler to do all this without guidance, would, I suspect, require much more theorem proving than it will be reasonable for compilers to do for a long. long time. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Exercise in point free-style
From: Julien Oster [EMAIL PROTECTED] Subject: [Haskell-cafe] Exercise in point free-style 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 Oh, YES!! Two ways to remove l: func3a f = uncurry ((.map f).(++)) . pair func3b f = uncurry (flip (++).map f) . pair And just to make sure they're right: propab new f l = func3 f l == new f l where types = f :: Int-Int quickCheck (propab func3a) quickCheck (propab func3b) If you don't mind swapping the arguments, then propc f l = func3 f l == func3c l f where types = f :: Int-Int func3c l = (l++) . (`map` l) With the arguments swapped, you can even remove both! propd f l = func3 f l == func3d l f where types = f :: Int - Int func3d = uncurry ((.(flip map)) . (.) . (++)) . pair MUCH clearer! The trick is to observe that l is duplicated, so you need to use a combinator that duplicates something. The only one available here is pair, which you then have to combine with uncurry. It would be nicer to have (f g) x = (f x,g x) available. ( is one of the arrow combinators). Then you could remove l by func3e f = uncurry (++) . (id map f) which is sort of readable, and remove both by func3f = (uncurry (++).) . (id ) . map John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] library sort
Am Samstag, 4. März 2006 21:30 schrieb Neil Mitchell: And a related question is: Which packages are searchable by Hoogle? The best answer to that is some. I intentionally excluded OpenGL and other graphics ones because they have a large interface and yet are not used by most people using Haskell. [...] Well, this a bold assumption IMHO, and I'm not particularly happy with that, as you can probably imagine. For my part, I would assume that Joe Programmer is much more likely to use some multimedia packages than TH or Data.Graph.* etc., but this is a bold assumption on *my* side... ... Well, this a bold assumption IMHO, and I'm not particularly happy with that, as you can probably imagine. I would also imagine that Joe Programmer is more likely to use wxHaskell or Gtk2Hs than those - however because those are outside the standard tree they don't make it in. I don't think much of TH made it in either (not becuase of deliberate exclusions, but because of technical limitations in the tool). When I surveyed Haskell users, I asked respondents to name the most important tools and libraries they use. (Caveat: respondents saw the list of tools and libraries already named, and could include these just by selecting them, so tools mentioned early in the survey were more likely to be named by subsequent respondents). Here are a few relevant entries, where the percentage is the proportion of respondents who named the tool: 29% Parsec 19% wxHaskell 16% QuickCheck 16% haddock 12% Monadic Parser Combinators 11% Gtk2Hs 9% hs-plugins 8% HaXml 7% Data.* 7% Monad foundation classes 6% Arrows 6% HOpenGL The list includes all libraries named by more than 5% of respondents. Sure enough, wxHaskell and Gtk2Hs are more popular, but 6% naming HOpenGL as among the most important libraries is quite respectable. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Library survey results
29% Parsec 19% wxHaskell 16% QuickCheck 16% haddock 12% Monadic Parser Combinators 11% Gtk2Hs 9% hs-plugins 8% HaXml 7% Data.* 7% Monad foundation classes 6% Arrows 6% HOpenGL The list includes all libraries named by more than 5% of respondents. Sure enough, wxHaskell and Gtk2Hs are more popular, but 6% naming HOpenGL as among the most important libraries is quite respectable. Well, I've never said that it is among the most important libraries, but OTOH I really much doubt that the way the survey was done delivers anything near reliable results. It heavily biases early entries, and I dare to speculate that the people taking part in the survey were probably not even near to a representative group, but a bunch of highly motivated, experienced non-Joe-Programmer kind of people who are actively participating on the mailing lists etc. It wasn't as bad as you think--over 580 replies, with less than a quarter of those from academics (there were actually more replies from people working in industry than from academics!). So I'd dispute that the survey tells us mostly about what the research community in particular wants. I'd guess the survey was pretty representative of KEEN Haskell users. It's a bit unclear who we mean by Joe Haskell-programmer anyway--I bet that, apart from students of course, the number of Haskell programmers who are using the language just because their boss tells them to can be counted on the fingers of one hand! I'd claim Joe Haskell programmer probably IS keen, highly motivated, experienced and active. In fact, the one group that is obviously underrepresented badly in my survey is just students--I got replies from just under 300, while another survey of teachers shows that at least 5-10,000 were taught Haskell last year. But maybe tools like hoogle SHOULD be aimed at the most active users? You're right that libraries mentioned earlier in the survey received more votes as a result, but since I have a record of all responses *in time order* I can see the difference, for each library, between pre- and post- first mention behaviour. HOpenGL was mentioned in the 7th response, wxHaskell in the first, and Gtk2Hs in the 17th, so they were in the previously mentioned category for almost the entire survey, and the effect you're talking about was not significant for a comparison between those three. Data.*, on the other hand, was first mentioned about half way through the survey, which indicates that around 12% of respondents selected it as among the most important libraries, when prompted to do so by seeing its name. However, the proportion who name Data.* spontaneously is below 2%--and that conclusion is statistically significant at the 99% level. 580 replies is enough to say statistically significant things (about the population the survey sampled, anyway). I feel quite inspired--when I have a spare moment, I'll analyse the results more carefully and see what one actually CAN say with a degree of certainty, taking into account when each library was first mentioned. Furthermore, some of the percentages above are extremely strange, e.g. how can people use huge GUI toolkits with 30% while staying largely away from something as fundamental as Data.*? I don't find it so strange, really. Data.* implements lots of useful standard datatypes, but you can import some of them in other ways (import Maybe for example), and in many cases it's not too hard to roll your own. OK, maybe with a worse result, but you're not *forced* to use Data.* -- so if you're used to using something else, there's no 100% compelling reason to change. Rolling your own wxHaskell or Gtk2Hs is prohibitively hard. So I'm not at all surprised that GUI toolkits rated much higher--people's natural conservatism gives them a big advantage, and even Haskell users can be conservative sometimes! Perhaps the most surprising thing here is that only 30% of keen Haskellers think a GUI is important! John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why is $ right associative instead ofleftassociative?
Quoting Paul Hudak [EMAIL PROTECTED]: Actually, one of the main reasons that we chose (:) is that that's what Miranda used. So, at the time at least, it was not entirely clear what the de facto universal inter-language standard was. Phil Wadler argued for the ML convention at the time, and wrote a document containing a fair amount of sample code to illustrate what it would look like. We noticed something surprising: instead of (x:xs) and the like, Phil had consistently written (x :: xs) -- note the extra spaces. Somehow, using the longer operator name led him to feel spaces were needed around it. That in turn made his lines longer, encouraged him to split definitions across lines, and so on. When I read the thing, I realised after a while that I was skipping all the code fragments -- because they just looked too big and complicated to take in during a quick reading. It was at least partly that experience that convinced us that using :: for cons would impose a small cost, but a real one, on readability. It may seem trivial, but the sum of many such decisions is significant. The story does illustrate the importance of actually trying out syntactic ideas and seeing how they play--one can be surprised by the result. I don't think Haskell Prime should be about changing the look and feel of the language. It's about consolidating the most important extensions into the standard, isn't it? Changes that break existing code should be very, very well motivated--if porting code to Haskell Prime is too difficult, people just won't do it. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why is $ right associative instead ofleftassociative?
Lennart Augustsson wrote: I now think :: for type signatures was a bad mistake. I don't use lists very much. They are not the right data structure for many things. So : is not as common as :: in my code. I checked a small sample of code, about 2 lines of Haskell. It has about 1000 uses of ':' and 2000 of '::'. Just for interest, I analysed some of my code. Obviously my style is quite different to yours--my type specialiser of 3,500 lines has 240 conses, and only 22 occurrences of '::'. I seem to be using '::' a bit more lately, though, which I suspect is due to using classes much more. I also checked the Agda source code, about 14,000 lines, with about 500 occurrences of cons and 640 of '::'. I think the only conclusion one can draw is that style varies. In my opinion all the special syntactic sugar for lists should go away. I don't think lists are special enough to motivate it. What, no list comprehensions?? I'd disagree--sequencing is special, and lists represent it directly. Don't forget, also, that lists are also much more prevalent in beginners' code--and nice notation for beginners helps get people started on Haskell. But this is not what Haskell' is about. It's supposed to be some modest extensions to Haskell. Not designing a new perfect language. Right! John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why is $ right associative instead ofleftassociative?
Cale Gibbard wrote: That said, I'd *really* like to see monad comprehensions come back, since they align better with the view that monads are container types, dual to the view that monads are computations, which is supported by the do-syntax. This view is actually much easier to teach (in my experience). Giving lists a little extra syntax is nice, but giving things unnecessarily restrictive types seems to be the point at which I'd consider it going too far. The trouble with monad comprehensions was that it became far too easy to write ambiguous programs, even when you thought you were just working with lists. Haskell overloading works really nicely *as long as there's a judicious mixture of overloaded and non-overloaded functions*, so that the overloading actually gets resolved somewhere. Overload too many things, and you end up having to insert type annotations in the middle of expressions instead, which really isn't nice. Lists are special, not least because they come very early in a Haskell course--or, in my case, in the first ever programming course my students have ever taken. Getting error messages about ambiguous overloading when they are still trying to understand what comprehension notation means (without even the concept of a for-loop to relate it to) is very destructive. And this is in the case where the code is otherwise type-correct--the kind of error message you would get by trying to append a number to a monad comprehension doesn't bear thinking about! The class system is already something of an obstacle in teaching, because you have to mention it in the context of arithmetic (even if you tell students always to write monomorphic type signatures, they still see classes mentioned in error messages). After all, that is surely why Helium doesn't have it. I find classes manageable for arithmetic, even if students do take some time to learn to distinguish between a class and a type (or a type and a value, for that matter!). But it's a relief that list programs, at least, have simple non-overloaded types. List functions provide an opportunity to introduce polymorphism in a simple context--it's much easier to understand why (++) should have the type [a] - [a] - [a], than to start talking about MonadPlus m = m a - m a - m a. There is a lot to learn in Haskell, especially in the type and class system. It's an advantage if you don't have to learn it all at once--if you can master lists and list comprehensions without exposure to monads (which are a much harder concept). We should never forget that beginners have somewhat different needs from expert programmers--and those needs are also important. If we want Haskell to be used for first programming courses (and it's a big advantage to catch 'em early), then there needs to be a learning path into the language that goes quite gently. Monomorphic lists help with that. We did consider more aggressive defaulting to address the ambiguity problems with monad comprehensions--defaulting Monad to lists, for example, or user-declared defaulting rules--but this introduces yet more complexity without really addressing the problem of keeping types simple for beginners, so the idea was abandoned. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Tutorial uploaded
-- Message: 1 Date: Wed, 21 Dec 2005 10:48:08 + From: Robin Green [EMAIL PROTECTED] Subject: Re: [Haskell-cafe] Re: Tutorial uploaded Beginners should start with non-monadic functions in order to later avoid IO in their functions whereever possible. Whilst localising IO to a small part of the program is generally a good idea, beginners should not be scared off by the thought that IO in Haskell is so hard it has to be covered on page 94. This is not the case. It should be introduced on page 1. If people want Haskell to be treated as a practical language, not just something for doing academic teaching and research with, it should be taught as a practical language - which means that things like IO and space/time usage come to the forefront. Couldn't agree more. I show my students IO in the first lecture of their first programming course in the first term of their first year. A few lectures later I discuss it in more detail, and tell to think of an IO a as instructions on a piece of paper to produce an a. My students have no difficulty understanding the difference between being given 500 crowns (a value), and being given my ATM card and code with instructions how to work an ATM! Haskell IO is mystifed far too often in my opinion--it needn't be hard at all. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Speed comparison?
Furthermore, the Haskell page says that ghc produces fast programs. So I would guess that Haskell is faster than Python, but not as fast as C. Would that be correct? Usually yes. In a sense. I think it's important to remember that what matters is performance of a whole application, not of highly tuned benchmark code, and in writing applications with good performance, then the quality of profiling tools, and (especially) the amount of time the programmer has available for tuning, can be far more important than the compiler. There have certainly been occasions where Haskell entries to the ICFP programming contest have beat OCaml or even C/C++ entries on performance, by a wide margin. Likewise Ericsson's ATM switch, which is controlled by a million lines plus of Erlang (running on a byte code interpreter!), performs better than all its competitors. Benchmarks give a very one-sided view, ignoring the large effect that ease of programming can have on the final system's performance. John Hughes ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Instances of constrained datatypes
This is a contrived example, but contains the essence of what I'd like to do. Suppose I have this datatype: data (Eq v) = EqList v = EqList [v] I'd like to make it an instance of Functor. However, fmap takes an arbitrary function of type a - b. I need an Eq constraint on a and b. Is there any way to do this without creating my own `EqFunctor' class with explicitly-kinded quantification: class (Eq a) = EqFunctor (f :: * - *) a where eqfmap:: (Eq b) = (a - b) - f a - f b Thanks. -Arjun I wrote a paper proposing an extension to allow this, published at the Haskell Workshop in 1999. Here's the link: http://www.cs.chalmers.se/~rjmh/Papers/restricted-datatypes.ps Getting the right dictionaries to the right place involves adding a concept of well-formed types, which perhaps is why it hasn't been taken up by the Simons... John Hughes ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Top 20 ``things'' to know in Haskell
Message: 9 Date: Mon, 7 Feb 2005 10:31:30 -0500 From: Jacques Carette [EMAIL PROTECTED] Subject: [Haskell-cafe] Top 20 ``things'' to know in Haskell To: haskell-cafe@haskell.org Message-ID: [EMAIL PROTECTED] Content-Type: text/plain; charset=us-ascii The recent post of Graham Klyne (below) reminds me that I have meant to ask: is there a ``top 20'' things a serious programmer should know when writing code in Haskell? Of course there is a lot of programming language theory that would be great to know, but I mean really down-to-earth things like the 2 items below (module Maybe, the 'maybe' function). The Haskell libraries are quite large, and it is unrealistic to try to get familiar with all of them right away. But getting a ``small'' list would be very useful - I think of this as step 2 after one learns to get comfortable with a language. I had done this (for Maple) for training new hires at Maplesoft, and I definitely noticed that they became more idiomatic programmers faster this way. Jacques PS: of course, this could already exist on haskell.org and/or the Wiki, but not in an 'obvious' enough place as I missed it... Beginners might find this useful: http://www.cs.chalmers.se/Cs/Grundutb/Kurser/d1pt/d1pta/ListDoc/ It's guide to finding the right list function which leads you to it by asking you what you are trying to achieve. john -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Graham Klyne Sent: February 7, 2005 10:09 AM To: Yuri D'Elia; haskell-cafe@haskell.org Subject: [Haskell-cafe] Re: [Haskell] [newbye] 'Just a' You might also be interested in the library function 'maybe': http://www.haskell.org/onlinereport/standard-prelude.html#$vmaybe or maybe (sic) Maybe.fromMaybe in: http://www.haskell.org/onlinereport/maybe.html #g -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Some random newbie questions
I seriously considered switching frlom Hugs to GHC for my introductory programming class this year, but in the end stayed with Hugs because of a single feature. I'm teaching beginning programmers, and for them at least, there is an overwhelming volume of names to learn -- what's that function? is a question they ask themselves often, as is what's that type?. I teach them that, whenever they see a name they don't recognise, they can find out more about it using the :i command. This is a simple trick to learn, that helps them understand points they've missed and catches misapprehensions. My students also see type classes very early. I'll bet yours will too. Even if one is very careful to restrict the examples in lectures so as to avoid them (which is a bind), as soon as students try out Hugs for themselves, they will make mistakes that generate error messages referring to type classes. No problem: the question what's that class? can ALSO be answered by :i. Now, at the beginning students have only a very rudimentary understanding of classes. A class is a collection of types to them, nothing more. In particular, the class definition itself is of little use to them, since it often contains a very subtly chosen collection of methods (just type :i Show, for example, which students do very early). What IS useful, right from the beginning, is the list of instances. What are Num types? Oh, integers and reals. What are Show types? Oh, pretty much everything. Particularly when debugging missing instance errors, this is just the information you need. Unfortunately, while Hugs prints the list of instances of a class in response to :i, GHCi does not. It only prints the class definition -- which, for my students, contains no useful information. For that reason alone, I stuck with Hugs last year. Of course, later in the course there is no problem in introducing GHC as well. Students coping well are happy to learn there is a compiler available too, while those who are struggling can stay with Hugs throughout the course. I demonstrated GHC in order to show them wxHaskell (which was very popular with the students), but I didn't REQUIRE them to use it. How about changing the behaviour of :i, Simon, so I can use GHCi throughout next year? John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Adding Ord constraint to instance Monad Set?
| Constraints on datatype declarations are a misfeature of Haskell, and | have no useful effect. | | Is this the final conclusion? Yes, it is, I believe. Constraints on data type declarations are a mis-feature. I tried to get them removed, but there was some argument that they could be made useful (see John Hughes's paper Restricted data types in Haskell, Haskell workshop 1999), and they stayed. Simon Made useful in a way that would solve the problem in this thread, I might add. The paper is at http://www.cs.chalmers.se/~rjmh/Papers/restricted-datatypes.ps for the curious. John ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Interpret haskell within haskell.
On Fri, 20 Dec 2002, Matt Hellige wrote: [Christopher Milton [EMAIL PROTECTED]] --- David Sankel [EMAIL PROTECTED] wrote: I was wondering if there is any project that aims to interpret haskell within haskell. [... snipped intro to ghci ...] If you have defined functions in myprog.hs: :load myprog.hs then the functions defined in the file are available, or else you'll get error message(s) about problems found parsing myprog.hs. I'm not sure this is quite what he's asking for. For many projects it is useful to be able to dynamically (and programatically) load and evaluate arbitrary chunks of code for one reason or another. Maybe this isn't quite what he was asking for either, but... When I want to do this kind of thing, I use hugs as a back-end. I write the expressions I want to evaluate, or whatever, to a file of hugs commands, and then run system hugs hugsinput hugsoutput then read and process the output (choose your favourite filenames, /tmp/... or whatever). It's not the world's fastest solution, but on the other hand hugs provides excellent reflection -- you can do much more than just evaluate expressions, you can ask hugs about types, class instances, etc etc. I've used this, for example, in an old prototype JavaDoc like tool which used Hugs to determine the types and other properties of documented names, and in a little script for use with QuickCheck, which finds all the property names defined in a set of modules, loads the modules into hugs, and tests the properties. You may think this is a very simple-minded approach, but I would defend it on several grounds: * it is VERY simple, and provides programmatic eval without any semantic problems whatsoever. * knowledge of the Haskell language is isolated where it belongs, in the hugs interpreter -- my tools only need to know how to work the hugs interface. As the language evolves, I can keep up just by installing a new version of hugs -- I have no parser and interpreter of my own to maintain. Easy and effective -- if a bit slow. John Hughes ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Writing a counter function
On Sun, 30 Jun 2002, Jon Cast wrote: Mark Carroll [EMAIL PROTECTED] wrote: On Sat, 29 Jun 2002, Samuel E. Moelius III wrote: (snip) Here's another not-exactly-what-you-wanted solution. :) (snip) Do any of the experimental extensions to Haskell allow a what-he-wanted solution? I couldn't arrange one in H98 without something having an infinitely-recursive type signature. That's because the problem requires an infinitely-recursive type. Consider Haskell: self-apply f = f f The *typing algorithm* (the thing that didn't complain in Lisp) proceeds roughly as follows: f is applied to at least one argument, so f must have type a - b. Therefore, f's argument (f) must have type a. So, we conclude: f :: a - b f :: a But f can only have one type, so we set its types equal: a = a - b This is clearly recursive, right? so I'm wondering if it could be at all sane for Haskell to allow such stuff Sure. All it has to do is: 1. Create its own newtype in response to such things as `self-apply' above. 2. Ensure that self-apply f = f f and self-apply' g = g g have the same type. I would *love* to hear ideas on how to do that, but it's difficult. It isn't particularly hard to implement this. Haskell typecheckers use unification to match types up; the only difference is that a graph unification algorithm would be needed instead. Such algorithms exist --- the only real difference is you have to remember what you're unifying to avoid falling into a loop when unifying graphs with cycles. The idea of adding this to Haskell has been proposed several times, but never implemented. And the reason for THAT is that it would make type errors significantly harder to understand. Consider f x y = if x==0 then y else f (x-1) (where I forgot the second parameter in the recursive call). We expect this to be a type error, and indeed it is --- BECAUSE recursive types are not allowed. If they were, this definition would be well-typed, with the type f :: Num a = a - bwhere b = b - b You wouldn't get an error message unless you tried to CALL f, and perhaps not even then. For example, f 1 2 :: Num b = b where b = b - b is well-typed! So you would probably eventually, somewhere else in the program, see an error message of the form ERROR - Illegal Haskell 98 class constraint in inferred type *** Type : Num b = b where b = b - b This is enough to scare most people off the idea. Think of all the times you've seen the error message unification would give infinite type It's not the most common kind of type error, but it does happen regularly, at least to me. In every such case, the type error would be deferred in the way I describe. If I remember rightly, OCaml allows type recursion of this sort, but restricts it to object types precisely to avoid these problems. John Hughes ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: problems figuring out what the type system is telling me
On Fri, 7 Jun 2002, Chris Moline wrote: ... two. i have also read what the hell are monads and monads for the working haskell programmer. i still do not get what i am doing wrong. getDepends :: String - [String] getDepends p = do handle - openFile (portsDir ++ p ++ /+CONTENTS) ReadMode fetchDepends handle to my brain this takes a string, concatenates it with portsDir and +/CONTENTS, and passes it to openfile. openFile then returns a handle and this handle and passes it to fetchDepends. getDepends will return whatever fetchDepends returns, assuming openFile succeeds. however ghc says Phoebe.hs:19: Couldn't match `[]' against `IO' Expected type: [t] Inferred type: IO Handle In the application `openFile (portsDir ++ (p ++ /+CONTENTS)) ReadMode' In a 'do' expression pattern binding: handle - openFile (portsDir ++ (p ++ /+CONTENTS)) ReadMode i do not know what this [t] is and i do not know why it is expected. my theory is it is being caused by something in fetchDepends. [t] is a list type: GHC is expecting the call of openFile to return a list (of t, but t is just a type variable so tells us nothing). Why is it expecting a list? BECAUSE OF YOUR TYPE SIGNATURE! You wrote a type signature specifying that getDepends (and fetchDepends, for that matter), returns a list. You should have given the result an IO type, since these functions do IO. I haven't checked, but probably the type of getDepends should be getDepends :: String - IO [String] rather than the type you wrote. So your mistake is just forgetting to include the monad in your type signature. Now, the error message you got maybe isn't the very clearest, but it is logical. Remember that the do syntax that you used in getDepends is OVERLOADED -- it can be used with any monad, not just with IO. In particular, it can be used with the list type, which is itself a monad. For example, we could, if we wished, define the ordinary list map function like this: map :: (a-b) - [a] - [b] map f xs = do x - xs return (f x) That's an example of using do with the list monad. Of course, since the do is working over lists, then when we write x - xs, the xs must also have a list type. We have to be consistent, and use the same monad throughout the do. This is just like when we use do to write an IO computation: in that case, when we write x - f y or whatever, the f y has to have an IO type. Now, in your code for getDepends, GHC sees your type signature and says Aha! This function returns a list. So the do in the body must be working over the list monad. In that case, when we see handle - openFile... then the openFile must have a list type. Oh dear, it's type isn't a list, it's IO! Better complain that [] (the name of the list type, not the empty list) doesn't match IO! Hence the error message you got. And now to a thorny and controversial question: should one write type signatures, or not? In particular, what advice should one give less experienced Haskell programmers? In this case, your CODE is probably quite correct. If you hadn't written the type signatures, then GHC would just have inferred the correct types and everything would have worked. Good advice for you might be to leave type signatures out, compile your code, and then look at the types that functions actually get (using ghci). You can always paste the types back into your code, and this way, they will be correct. On the other hand, if you omit type signatures, then when you DO get a type error it will be in terms of type variables and classes, rather than types such as Int or String which you would probably be expecting. There is a trade off here. One way to approach it is to write type signatures, but when a definition doesn't type check, remove the signature on that one and see whether it then typechecks. If so, the definition is right, but your type signature is wrong. Use ghci to find out the correct type signature, and insert it. You also mentioned layout problems when you used if in a do. I'm assuming you tried writing something like do if ... then ... else ... ... If you write this, then because the else appears in the same column as the if, it's taken to be the start of a new element in the do -- with a syntax error as the result. You just have to indent the else further than the if. I use an indentation like this: do ... if ... then ... else ... ... which lets GHC see that the entire if-then-else makes up just one element in the enclosing do. This is a classic gotcha of the layout rule: the first layout is quite natural, but you just can't write it. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Lazy Parsing
There's a combinator which Phil Wadler called guarantee which makes a parser lazy -- guarantee p succeeds at once, with a result which will be produced, when demanded, by p. Many parsing libraries include it under one name or another... John ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Monad composition
Andre W B Furtado wrote: Well, it's also possible to interchange data between these two monads by: unsafeIOToST :: IO a - ST s a stToIO :: ST s a - IO a Can anyone tell the possible problems related to unsafeIOToST? ^^ Probably in the same manner as with unsafePerformIO: it can break referential transparency. Indeed, unsafePerformIO m = runST (unsafeIOToST m) so they're just as unsafe as each other. John Hughes ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Monad composition
The easiest way to combine State and IO is using a monad transformer. There are some lecture notes which you might find useful at http://www.md.chalmers.se/~rjmh/Combinators/Monads/index.htm which refer to a library module http://www.md.chalmers.se/~rjmh/Combinators/MonadTransformers.hs Using this library you just build the type type StateIO s a = State s IO a which is a monad with operations readState, writeState, and lift :: IO a - StateIO s a John ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Counting recursive calls
Hi all, got some questions on recursive functions. I got a simple recursive function (f3) In *some* situations I'll want to know how many recursive calls did it make. I came up with two simple implementations to do that (f1) and (f2) f [] w = (w,0) f (x:xs) w = (nextw, steps+1) where (nextw, steps) = f xs (g x w) f2 [] k w = (w,k) f2 (x:xs) k w = f2 xs (k+1) (g x w) f3 [] w = w f3 (x:xs) w = f3 xs (g x w) ... Anyway like I said I don't *always* want to know the n. of steps, so I could chose either to: - use 2 different functions, one when I want the n. of steps (f or f2) another one when I don't need it (f3) - use just one function (f or f2) if I don't need the n. of steps, use fst. The second choice seemed to make more sense to me. Lazy evaluation should do the trick, and the n. of steps would not have to be evaluated, so efficiency-wise it would be the same as calling f3. Oh oh --- lazy evaluation isn't what you want here! Certainly it will avoid *computing* the number of steps, but it will do so by building up a gigantic unevaluated closure of the form (0+1)+1)+1)+1)+1)+1)+1)+1)+1). So you'll be using memory linear in the running time -- not good. Moreover, when you finally come to evaluate that closure, you'll need a *huge* stack to do it on. ... [2] Any tips on which function(s) should I choose, or any way to make them more efficient. Most efficient will be to force strict evaluation of the count. In GHC you can do that by using an unboxed integer. - (**) would I get a different behavior if I had compiled the program. I've had some problems when trying to compile and use getCPUTime. Some stack overflows for big values of w, and for smaller values 0 in the execution time... I'll try to figure out what I'm doing wrong here... What did I say about the stack? If you compile your code, and especially if you use an unboxed integer as I suggest, then the cost for counting steps should be very low. In particular, it will certainly be cheaper to *compute* k+1 (single unboxed addition) than to build a suspension for it (memory allocation). You might get a different result in the interpreter, because of all the interpretation overhead, but in compiled code there should be no question about it. John ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Hashtable ADT
As I understand from the concepts of Functional Programming, it is not possible to implement a Hashtable ADT in Haskell language, where one can insert, and access values in O(1) complexity. It has to be implemented with an external language. I don't know if it can be done in standard Haskell 98, but it can certainly be done using extensions provided by most or all implementations (IORef, IOArray). There is no need of using an external language, although it will not fit well the functional style. Better is to use the ST monad (which provides creation, reading, and writing of arrays and references in constant time). Side-effects in the ST monad can be encapsulated using runST :: (forall s. ST s a) - a You give it a computation using updateable state as an argument, a state thread, and it gives you the result as a pure value. The forall s is a typing trick which prevents an encapsulated state thread from referring to references belonging to a different state thread. Using this you can, for example, create a function share :: Hashable a = [a] - [a] which takes a list of hashable values, and returns an equal list, in which equal values are always represented by the same pointer. Internally, there's a hash table which lets you map each element of the input to a unique representative. You could compose share with a lexical analyser, for example, to share all the copies of the same identifier. Encapsulated stateful operations like this fit very nicely with the functional style! Take a look at State in Haskell, John Launchbury and Simon Peyton Jones, http://www.cse.ogi.edu/~jl/Papers/stateThreads.ps which explains all of this at length. John Hughes ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: let/where
The point of where is that it scopes over guards and multiple equations as well as right hand sides. f x | xsquared 1000 = xsquared | otherwise = 0 where xsquared = x*x For the same reason, it has to be restricted to appear at the top level of a right hand side. Of course, we also need a construct to bind local variables inside an expression -- hence let, which therefore cannot scope over guards. Two kinds of scope, two binding constructions. We could have got away with one, if we had thrown out guards and relied just on if-then-else to test conditions instead. But guards are very expressive: some programs would have been a lot harder to write without them. Typical examples are when we just want to pick out one case in the first equation of a function, before lots of pattern matching: f x y | simplecase x y = simpleanswer f p1 p2 = ... f p3 p4 = ... ... There's no neat way to write this with if-then-else: you need to split f into two functions f x y = if simplecase x y then simpleanswer else f' x y f' p1 p2 = ... ... That's the reason Haskell has two binding constructions. John Hughes ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: How to force evaluation entirely?
Simon PJ says: Did you try "seq"? x `seq` y should evalute x to WHNF before returning y. If x is a pair you may need to say seqPair x `seq` y where seqPair (a,b) = a `seq` b in order to force the components. Simon There's an easier way to force structures hyperstrictly. To force x to be evaluated to normal form before computing y, write (x==x) `seq` y This depends on all the types occurring in x being Eq types, and also on the implementation of == being hyperstrict when its result is true. This holds for all derived instances, and for most programmer defined ones too. After all, if x==x holds for any non-total x, then x==y must hold for some pair of different values x and y, which we normally try to avoid! I sometimes write if x==x then y else error "I am the pope!" but the seq form is nicer! John Hughes | -Original Message- | From: Michael Marte [mailto:[EMAIL PROTECTED]] | | | | I am trying to process a huge bunch of large XML files in order | to extract some data. For each XML file, a small summary (6 integers) | is created which is kept until writing a HTML page displaying the | results. | | The ghc-compiled program behaves as expected: It opens one | XML file after | the other but does not read a lot. After some 50 files, it | bails out due | to lack of heap storage. | | To overcome the problem, I tried to force the program to | compute summaries | immediately after reading the corresponding XML file. I tried | some eager | application ($!), some irrefutable pattern, and some | strictness flags, but | I did not succeed.
