August 2003 - Haskell

Re: Last call generalised
by b.i.mills＠massey.ac.nz 30 Aug '03

30 Aug '03

"Marcin 'Qrczak' Kowalczyk" produced .... >> I brought up the same issue some time back about >>. That is >> in func = f x >> func, we have the problem that >> is a function >> so func is not a last call. > > It's an easy problem: although func is not a tail call, >> is a > tail call and >> itself in most monads enters its second argument > in a tail position. I would name it an indirect tail call. I'll take it for the moment that Marcin is not deliberately being obtuse and just emphasise what the word "problem" means. If I say to a primary school student that in arithmetic the problem is to work out such things as "what is 2+2" the student might respond with "that's not a problem, 2+2=4, even I know that". But, they missed the point they we were not saying that 2+2 was a difficult problem whose resolution was the aim of arithmetic, we are simply pointing out the nature of the problems that arithmetic is aimed at solving. To paraphrase my earlier comment, I start by taking it that the definition of "last call" is essentially when a function returns the return value from another function call. In this situation we can validly destroy the context of the caller, thus, for example, evaluating a tail recursive routine with constant resource usage, ceteris paribus. In something like fact n t = if n==0 then 1 else fact (n-1) (t*n) this is clearly the case. But in a traditional procedural code, we might say fact(n,t){if(!n) return 0; t=t*n; n=n-1; return fact(n,t);}. This is taken within the meaning of tail recursion, but a direct transliteration into Haskell means that the ; becomes >>=, which means that strictly the factorial is not a "last call". Nevertheless, the concept of last call optimisation still stands, due to the nature of the >>= operator. It stands here in a way that does not apply to fact(n){if(!n) return 1; return n * fact(n-1);}. (Of course other automated optimisations apply here, Marcin). > in a tail position. I would name it an indirect tail call. To quote Spock ... I believe I just said that, Doctor. Regards, Bruce. ps: If Marcin wants to play anymore semantic games I promise he can do so on his lonesome.

1 0

RE: Type class problem
by Simon Peyton-Jones 30 Aug '03

30 Aug '03

Brandon writes | An application of Mu should be showable if the functor maps showable types | to showable types, so the most natural way to define the instance seemed | to be | | instance (Show a => Show (f a)) => Show (Mu f) where | show (In x) = show x | | Of course that constraint didn't work Interesting. This point is coming up more often! You'll find another example of the usefulness of constraints like the one in your instance decl in "Derivable Type Classes" (towards the end). http://research.microsoft.com/~simonpj/Papers/derive.htm Valery Trifonov has a beautiful paper at the upcoming Haskell workshop 2003 that shows how to code around the lack of universally quantified constraints. I strongly suggest you take a look at it, but it doesn't seem to be online yet. | Constraint Stack Overflow: | Observable (N (Mu N)) | Observable (Mu N) | Observable (N (Mu N)) | Observable (Mu N) | ... | | I expected that that constraint solver would realize it could construct a | dictionary transformer with a type like Observer Nat -> Observer Nat and | take the fixed point to get an instance for Nat. I haven't looked at the | implementation, but it seems like it would be easy to add the constraint | we are trying to derive to the list of assumptions when trying to | construct all the anteceedents of an instance declaration. That's true, I believe, but a) it's a bit fragile (a sort of half-way house to solving the halting problem) b) at the moment dictionaries have the property that you can always evaluate them using call-by-value; if they could be recursively defined (as you suggest) that would no longer be the case Mind you, GHC doesn't currently take advantage of (b), so maybe it should be ignored. Adding the current goal as an axiom would not be difficult, but I don't have time to do it today! Is anyone else interested in such a feature? Oleg wrote > Well, it can if we write it in a bit different way: > > instance (Show (f (Mu f))) => Show (Mu f) where > show (In x) = show x > > instance Show (N (Mu N)) where > show Z = "Z" > show (S k) = "S "++show k That's very clever, Oleg; I hadn't thought of that. But again, it's fragile isn't it? You are dicing with non-termination if you have instance declarations where the stuff before the '=>' is more complicated than the stuff after the '=>'. A less carefully written instance for Show (N (Mu N)) would make the type checker loop. Simon

3 3

Last call generalised (was Re: tail recursion, (was Re: Need some help please))
by b.i.mills＠massey.ac.nz 29 Aug '03

29 Aug '03

Yo, > copyList (x:xs) = x : copyList xs > > is surely not tail-recursive in the traditional sense, but I think > that most Haskell programmers take it for granted that it runs in > constant stack space. Not sure how this is a continuation of the safetail problem, and there are others who know a lot more about the specific guts of GHC and HUGS, but in that vein, I've got a general comment on what I see as the principle going on here. I brought up the same issue some time back about >>. That is in func = f x >> func, we have the problem that >> is a function so func is not a last call. (David Bergman emphasised that it is better viewed as "last call" than "tail recursion). But if this was C, then the function is func = {f x ; func}, in which func is then the last call. But the Haskell version of this is func = do { f x ; func}, which is just syntactic sugar for the first option, so again, no "last call". Haskell compilers do have optimisations related to this, but I just want to make a generic comment. In procedural programming, the idea of the last call is that there is an operator ; that is often thought of as separating statements. I would argue that it is rather joining commands, with a transfer of state. That is in C, {cmdA ; cmdB ; } means do cmdA with the current machine state, and then cmdB, passing the resulting state from cmdA. Thus the Haskell interpretation of ; as >> or >>= in monad terms is really just a natural statement of what is going on. Viva Haskell! But the point is that this means that "last call" is actually relative to the composition operation. So, traditional procedural last call optimisation is just last-call-wrt-join, or something like that. Thus, the situation for optimisation is f x = joinOp(x, f (g x)) were joinOp has the characteristic that it does not really need to know what the second argument is in order to proceed with the first part of the computation. Eg, using >>=, we can finish with the LHS completely before going to the RHS, and likewise with copyList (x:xs) = x : copyList xs, we can deal with the (x :) completely, and never have to come back to it. Again, I expect my comments are unorthodox, but I certainly feel that there is a point here to be made. The situation for "last call" optimisation is a bit more general than simply that case of temporal-catenation of commands. It has much more to do with the logical relation between the arguments to a function. Regards, Bruce.

2 1

Exhaustive Pattern-Matching
by Steffen Mazanek 29 Aug '03

29 Aug '03

Hello, I have a question about pattern-matching. In the Haskell-report it is not postulated, that pattern matching has to be exhaustive. Would it be possible at all to implement an algorithm, which checks Haskell-style patterns for exhaustiveness? What kinds of complication can be expected? Maybe you have some pointers to other resources about this topic. Thank you, Steffen

4 4

RE: unsafeInterleaveIO ordering
by Hal Daume 29 Aug '03

29 Aug '03

> In your example it's more or less guaranteed that putting "b" > and "c" will > never happen, because the result of the combinated IO action > isn't demanded. well yes, it was a bad example. i got another answer basically saying that threading could screw it up (i'm not using thread) as could, perhaps, speculative evaluation, which is somewhat unfortunate, but i can live with it. - hal

1 0

RE: Exhaustive Pattern-Matching
by Simon Marlow 29 Aug '03

29 Aug '03

> I have a question about pattern-matching. In the Haskell-report it is > not postulated, that > pattern matching has to be exhaustive. Would it be possible at all to > implement an > algorithm, which checks Haskell-style patterns for > exhaustiveness? What > kinds of > complication can be expected? Maybe you have some pointers to other > resources about > this topic. GHC tries to do so, but sometimes gets it wrong. See the -fwarn-incomplete-patterns flag. We'd appreciate it if someone could overhaul this code - it's been on the wish list for a long time. Cheers, Simon

2 1

Haskell-report, chapter 3 - Expressions
by Steffen Mazanek 28 Aug '03

28 Aug '03

Hello, I do not completely understand the first part of chapter 3 of the Haskell-report. Concretely I am stumbling about the notation of nonterminals indexed by their precedence level. This should be a number ranging from 0 to 9. But what about this exp^{10} production rule? I would be very appreciated if someone could explain this part in some more detail. I am trying to introduce a new language construct into this grammar and I want to insert it at the right place :-) Ciao, Steffen

1 0

Need some help please
by Rajiv Patel 28 Aug '03

28 Aug '03

Hi, I need to define a function called safetail; it's like tail except that this one maps the empty list to the empty list. It has to be defined using the following: 1. a conditional expression 2. guarded equation 3. pattern matching It's probably quite simple, but I am struggling on this, so help would be appreciated. Thanks Raj

3 2

Interval arithmetic
by Jonas Ritter 28 Aug '03

28 Aug '03

Hi all, I am interested in interval arithmetic. Does anyone know something about haskell implementations in this domain? It would be nice to have a datatype Interval with the elementary operations {+,-,*,/}, where >+ :: Intervall -> Intervall -> Intervall >(a,b) + (c,d) = (a+c,b+d) >- :: Intervall -> Intervall -> Intervall >(a,b) - (c,d) = (a-d,b-c) etc. Bye Jonas

3 2

RE: Need some help please.
by Hal Daume 27 Aug '03

27 Aug '03

There's a small problem with this solution, namely that it requires you to have an Eq instance for the elements in the list. You can fix this by using 'null' from the Prelude. -- Hal Daume III | hdaume(a)isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume > -----Original Message----- > From: haskell-admin(a)haskell.org > [mailto:haskell-admin@haskell.org] On Behalf Of b.i.mills(a)massey.ac.nz > Sent: Wednesday, August 27, 2003 1:57 PM > To: haskell(a)haskell.org > Subject: Re: Need some help please. > > > What is Nick Name doing? Trolling? > > I don't approve of people getting homework done on this emailing > list, you learn more from doing, but baiting newbies is worse. > You want to give them the idea that Haskell is complex and abtruse? > > > I need to define a function called safetail; it's like tail > > except that this one maps the empty list to the empty list. > > It has to be defined using the following: > > Ok, so logicaly, we are saying that we want (safeTail x) to be > (tail x) if x is not [], but for x==[] (normally an error) we > want (safeTail []) == []. Just write this down in Haskell ... > > safeCond x = if x==[] then [] > else tail x > > Guards are just another way of producing conditional expressions > > safeGuard x | x==[] = [] > | True = tail x > > And pattern matching likewise, for this simple example > > safePat [] = [] > safePat x = tail x > > If you want to test the result ... > > tester 0 safe = [(safe [])] > tester n safe = (safe [1 .. n]) : (tester (n-1) safe) > > call it as (tester 10 safePat) for example, to get a list > of some of the outputs from the safePat routine. > > Regards, > > Bruce. > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell >

1 0