Pattern matching on numbers?
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 (==)? Should whatever technique is used be extended to other typeclasses too? -- ryan
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.
On Tue, Nov 18, 2008 at 6:56 PM, Henning Thielemann
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'.
As I understand it, the use of (==) in numeric pattern matching is why
Num requires Eq.
--
Dave Menendez
Yes, fromInteger and == is used for pattern matching on numbers.
However, on GHC you can use -XNoImplicitPrelude to make it use whatever
fromInteger and == that's in scope (without any Num or Eq).
Eg. if == is a method of MyEq class and fromInteger is a method of
MyNum, and MyNum doesn't inherit MyEq, then the type of this function
f 0 = ""
f x = 'e' : f (x-1)
Will be inferred as (MyEq a, MyNum a) => a -> String
/Tobias
-----Original Message-----
From: haskell-cafe-bounces@haskell.org
[mailto:haskell-cafe-bounces@haskell.org] On Behalf Of David Menendez
Sent: den 19 november 2008 01:00
To: Henning Thielemann
Cc: Haskell Cafe
Subject: Re: [Haskell-cafe] Pattern matching on numbers?
On Tue, Nov 18, 2008 at 6:56 PM, Henning Thielemann
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'.
As I understand it, the use of (==) in numeric pattern matching is why
Num requires Eq.
--
Dave Menendez
participants (4)
-
David Menendez -
Henning Thielemann -
Ryan Ingram -
Tobias Bexelius