Six more Haskell report 1.1 typos/errors
Original-Via: uk.ac.nsf; Wed, 6 Nov 91 14:43:35 GMT
Original-Sender: [EMAIL PROTECTED]
1. On p. 57, middle of figure 8 it says:
x `mod` y = if signum x == -(signum y) ...
it should be:
x `mod` y = if signum r == -signum y ...
^
(as it is on p. 86), i.e. substitute x to r in the test part.
2. And on p. 81 add as the first clause of the definition of gcd:
gcd 0 0 = error "gcd{Prelude}: gcd 0 0 is undefined."
3. P. 22, Semantics of n+k patterns:
case e0 of {x+k -> e; _ -> e';}
= if e0 >= k then let x = e0-k in e else e'
What if x occurs in e0? I know what it says on p. 21, but I don't
like it, since this 'let' has the same syntax as the ordinary recursive
let.
4. Still p. 22, Semantics of (K x1 ... xn) patterns;
I'm (now :-) surprised to find that xj (j e; _ -> e';}
= case e1 of {x1 -> ... case en of {xn -> e}...}
I understand that the two last cases ((k) and (l)) are supposed to be
'dynamic' in nature (i.e. e1...en should be closures), rather than
syntactic, but read to the letter...
5. And, if I continue to read to the letter, an expression like
case y of {K x1 ... xn -> e; _ -> e';}
where y is a variable (or is an expression of another form than
K' e1 ... em), has no semantics!
6. Case (f), in the semantics for case-expressions, loops! It needs a
restriction saying that at least one of p1...pn is not a variable.
/kent k
Re: Efficient derived orderings
Original-Via: uk.ac.ox.prg; Wed, 6 Nov 91 09:30:57 GMT [EMAIL PROTECTED] writes: | There were two small bugs in the solution of Mark Jones: No, I think they were Ok (after my slight correction). But I can see why it might look confusing at first -- we naturally tend to think of functional composition f . g as meaning "first apply g and then apply f to the result". But you're forgetting about lazy evaluation! What actually happens when we attempt to compare trees (u :^: v) and (x :^: y) (applied to some ``comparison continuation'', o) is described by: (comp u x . comp v y) o = comp u x (comp v y o) So the comparison between u and x *is* done first and the comparison between v and y will only take place in the special case where u==x. | This keeps the traversal order and stops evaluation when the first | non-EQ has been found. Which is exactly the behaviour I've just described. Your approach is equivalent to mine, but I prefer to use the standard functional composition (.) instead of introducing a new operator (@). Putting it another way, my approach uses lazy evaluation where yours requires explicit conditionals. Hope that sorts things out! Mark
Re: n+k patterns
Original-Via: uk.ac.ox.prg; Wed, 6 Nov 91 11:44:16 GMT
> | Kent Karlsson asks:
> | | Which semantics did you use?
> |
> | The following seemed sensible to me (Your first choice in each case):
>
> [ ... my attempt at a semantics for c*p and p+k patterns ... ]
>
>I had hoped not, since then a match can fail and fail the entier program,
> even if a "later" patterns really matches, since in the above the "next"
> pattern is not tested upon such a fail.
I have been persuaded and would go along with Kent's proposed semantics
for c*p and p+k patterns if these were introduced into the language.
Specifically:
| case e0 of {p+k -> e; _ -> e'}
| either = if e0 >= k then case e0-k of {p -> e; _ -> e'} else e'
| or = case e0-k of {p -> e; _ -> e'}
But let's not use the second option here ... I'm a firm believer that (p+k)
patterns should match only positive values.
Note also that this includes the current semantics for Haskell n+k patterns
as a special case (writing p as a variable which is guaranteed to match and
simplifying the case expr on the rhs).
| case e0 of {c*p -> e; _ -> e'}
| either = if e0 >= 0 then case e0 `divRem` c of (p, 0) -> e; _ -> e'} else e'| or
|= case e0 `divRem` c of (p, 0) -> e; _ -> e'}
The choice here isn't so clear. Should c*p patterns match only positive
values (for uniformity with with p+k patterns, although there is no real
need for the restriction in this case), or should we allow them to match
arbitrary multiples of c? Perhaps someone with lots of examples of the
use of c*p+k patterns could comment on which would be best? Tony?
Thanks to Kent for straightening this out.
Mark
Re: n+k patterns
Original-Via: uk.ac.st-and.cs; Wed, 6 Nov 91 14:54:59 GMT
> > | Kent Karlsson asks:
> > | | Which semantics did you use?
> > |
> > | The following seemed sensible to me (Your first choice in each case):
> >
> > [ ... my attempt at a semantics for c*p and p+k patterns ... ]
> >
> >I had hoped not, since then a match can fail and fail the entier program,
> > even if a "later" patterns really matches, since in the above the "next"
> > pattern is not tested upon such a fail.
>
> I have been persuaded and would go along with Kent's proposed semantics
> for c*p and p+k patterns if these were introduced into the language.
> Specifically:
>
> | case e0 of {p+k -> e; _ -> e'}
> | either = if e0 >= k then case e0-k of {p -> e; _ -> e'} else e'
> | or = case e0-k of {p -> e; _ -> e'}
>
> But let's not use the second option here ... I'm a firm believer that (p+k)
> patterns should match only positive values.
>
> Note also that this includes the current semantics for Haskell n+k patterns
> as a special case (writing p as a variable which is guaranteed to match and
> simplifying the case expr on the rhs).
>
> | case e0 of {c*p -> e; _ -> e'}
> | either = if e0 >= 0 then case e0 `divRem` c of (p, 0) -> e; _ -> e'} else e'| or
> = case e0 `divRem` c of (p, 0) -> e; _ -> e'}
>
> The choice here isn't so clear. Should c*p patterns match only positive
> values (for uniformity with with p+k patterns, although there is no real
> need for the restriction in this case), or should we allow them to match
> arbitrary multiples of c? Perhaps someone with lots of examples of the
> use of c*p+k patterns could comment on which would be best? Tony?
>
> Thanks to Kent for straightening this out.
>
> Mark
>
I would be very much in favour of missing out the >= test in both n+k and
c*n+k. As Mark says there is no need for a restriction in the latter case.
In the former, the restriction is only there because of a wish to model
the Natural Numbers, a data type which is NOT native to Haskell.
Tony
Re: n+k patterns
Original-Via: uk.ac.nsf; Wed, 6 Nov 91 20:00:39 GMT
Original-Sender: [EMAIL PROTECTED]
> I would be very much in favour of missing out the >= test in both n+k and
> c*n+k. As Mark says there is no need for a restriction in the latter case.
> In the former, the restriction is only there because of a wish to model
> the Natural Numbers, a data type which is NOT native to Haskell.
>
> Tony
May I then propose yet another (sorry :-) arithmetic pattern: -n;
that matches only negative numbers:
case e0 of {-x -> e; _ -> e';}
= if e0 < 0 then case -(e0) of {x -> e; _ -> e';} else e'
E.g.
abs (-n) = n
abs n = n
x ^ (-n) = error "x^(-n) is undefined."
x ^0= 1
x ^1= x
x ^ (2*n+1) = x*xn*xn where xn = x^n
x ^ (2*n) =xn*xn where xn = x^n
x ^^ (-n) = 1/(x^n)
x ^^ n = x^n
/kent k
