So a first comment on this. I spoke too soon, ghc clearly has a bug here.
It shouldn't reorder those matches against literals like that.
I suggest you report that bug, because, as you say, it violates the H98 report.
But I don't think that bug at all affects the function you had in your
original email.
-- Lennart
On Thu, Mar 26, 2009 at 5:39 PM, Claus Reinke <claus.rei...@talk21.com> wrote:
> Sorry to be the odd man out - perhaps an example will help to
> clarify my reading of the language definition.
>
>> I find this "reordering" discussion somewhat nonsensical.
>> Haskell specifies top-to-botton, left-to-right matching.
>> This specifies exactly which tests that have to be made and in what order,
>> and ghc does exactly those and in the correct order.
>>
>> One can have a perception that when there are multiple arms in a case
>> decided by a single test, then the first arm should somehow be reached
>> quicker than the second one etc But that is something that the Haskell
>> standard has never promised, nor has any compiler ever promised this.
>
> When you say "test", which can decide multiple arms in a case, do you
> mean that, say 'null e' being 'True' implies that matching '[]' against 'e'
> will succeed while matching '_:_' against 'e' will fail? Because that kind
> of test is not what the Haskell'98 report talks about. It talks about
> individual matches of expressions against alternatives, and it does
> specify precisely in what order these are to be performed, hence
> which pattern is reached first:
>
> A case expression is evaluated by pattern matching the expression e
> against the individual alternatives. The alternatives are tried
> sequentially, from top to bottom.
>
> Patterns are matched against values. Attempting to match a pattern can
> have one of three results: it may fail; it may succeed, returning a binding
> for each variable in the pattern; or it may diverge (i.e. return _|_).
> Pattern matching proceeds from left to right, ..
>
> Nothing abstract about that. So for a function application 'f e', where
>
> f [] = True
> f (_:_) = False
>
> the Haskell'98 report specifies that 'e' is first matched against '[]', then
> (if that fails) against (_:_). So the first pattern is reached/tried before
> the second. Of course, we can make use of the fact that these two
> matches are complementary, so we only need one "test" to decide,
> and if there are further '[]' patterns after the first, we don't have to
> match them again, but that is all in the realm of optimization, not language
> definition.
> The definition explicitly provides room for such optimization, but it still
> requires conformance to the rules set out in the definition, which include:
>
> case e of {p1->e1;p2->e2} = case e of {p1->e1;_->case e of
> {p2->e2;_->error "No match"}}
>
> GHC violates that rule, as we can demonstrate:
>
> newtype N = N Int deriving (Show,Eq)
> instance Num N where
> fromInteger 0 = error "0"
> fromInteger 1 = N 0
> fromInteger _ = N 1
> f x = case x of
> 1 -> False
> 0 -> True
> g x = case x of
> 1 -> False
> _ -> case x of
> 0 -> True
> _ -> error "No match"
> main = do
> print $ g (N 0)
> print $ f (N 0)
>
> -- ghc
> $ ghc -w -e main PMOrderSpec.hs
> False
> <interactive>: 0
>
> -- hugs
> Main> main
> False
> False
>
> One can presumably construct similar examples using 'Data.String.IsString',
> or using pattern guards, so just fixing the special case of 'Num' is not
> going
> to help, but this example seems firmly within Haskell'98.
>
>> And to me such a perception is counter-intuitive; Haskell is about
>> specifying functions abstractly so order should only matter when it's
>> a matter of semantics.
>
> Any semantics should conform to the language definition, right?
>
>> On the other hand, adding some kind of pragma that indicates the
>> likelyhood of a branch seems quite sensible to me.
>
> Which doesn't mean that I wouldn't try such a pragma, if it existed.
> I'm just having difficulties understanding this universal resistance to
> what seems one of the few unambiguously defined parts of Haskell'98;-)
>
> Claus
>
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
