[Haskell-cafe] Pattern matching on numbers?
lemming at henning-thielemann.de
Tue Nov 18 18:56:27 EST 2008
On Tue, 18 Nov 2008, Ryan Ingram wrote:
> How does this work?
>> fac n = case n of
>> 0 -> 1
>> _ -> n * fac (n-1)
> ghci> :t fac
> fac :: (Num t) => t -> t
> The first line of "fac" pattern matches on 0. So how does this work
> over any value of the Num typeclass? I know that the "1" on the rhs
> of fac are replaced with (fromInteger 1), but what about numeric
> literals in patterns? Does it turn into a call to (==)?
As far as I know, yes. It is even possible to trap into an error on
pattern matching this way if fromInteger generates an 'undefined'.
> Should whatever technique is used be extended to other typeclasses too?
It is unusual to do pattern matching on fractions, you mostly need it for
recursion on natural numbers. Thus I think the cleanest solution would be
to treat natural numbers like strict Peano numbers
data PeanoStrict = Zero | Succ !PeanoStrict
but with an efficient implementation using GMP integers, maybe using
'views', if they were part of Haskell language. Then you can implement:
fac :: Integer -> Integer
fac Zero = 1
fac n1@(Succ n) = n1 * fac n
I would then give up pattern matching on any numeric type.
More information about the Haskell-Cafe