Exhaustive Pattern-Matching
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
hello, Steffen Mazanek wrote:
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 i believe in general this is undecidable, as one can have arbitrary decisions in guards. of course in practise this is probably not much of a problem, so the compiler could (and often does) give useful warnings. so at the end of the day the usefulness of an algorithm to detect incomplete patterns depends on what you want to do with it.
bye iavor -- ================================================== | Iavor S. Diatchki, Ph.D. student | | Department of Computer Science and Engineering | | School of OGI at OHSU | | http://www.cse.ogi.edu/~diatchki | ==================================================
Thank you all for your help. I will try this ghc-flag. It is interesting as well, that in contrast to Haskell Standard ML ensures, that pattern-matches are exhaustive and irredundant. Ciao, Steffen
On Thursday, Aug 28, 2003, at 08:47 Europe/Amsterdam, Steffen Mazanek wrote:
Thank you all for your help. I will try this ghc-flag. It is interesting as well, that in contrast to Haskell Standard ML ensures, that pattern-matches are exhaustive and irredundant.
SML has the same limitations w.r.t. guards as Haskell; Haskell compilers can and do check exhaustiveness, but not redundancy because matches are tried sequentially. I believe SML matching is also sequential. If there is a difference between the two, it must have to do with laziness. Regards, Frank
Dnia czw 28. sierpnia 2003 16:37, Frank Atanassow napisał:
SML has the same limitations w.r.t. guards as Haskell; Haskell compilers can and do check exhaustiveness, but not redundancy because matches are tried sequentially. I believe SML matching is also sequential. If there is a difference between the two, it must have to do with laziness.
SML doesn't have guards at all. Most Haskell matches are correctly flagged as non-exhaustive or redundant if you use "otherwise" instead of relying on some guards themselves being exhaustive (which the compiler can't check). -- __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/
participants (4)
-
Frank Atanassow -
Iavor Diatchki -
Marcin 'Qrczak' Kowalczyk -
Steffen Mazanek