Implementing instance of '^' operator

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Implementing instance of '^' operator

pmcilroy

 

As a ‘hello world’ example for type definitions, I like to define a numeric type that can handle the mod p multiplicative group, where p is prime. This requires:

·       Implementing interface functions

·       Defining non-trivial implementations, where constructor must be private, etc.

·       Invoking an abstract superclass concrete instance method from within the subclass method definition

The latter appears not to be possible in Haskell. Is this true?

Here’s the basic code, but I punted on x^n. It looks like I’d have to paste in the entire original definition of ‘^’.

data Modp a = Modp a a deriving (Eq, Show)

 

mkModp p n | isPrime p = Modp p (n `mod` p)

           | otherwise = error $ show p ++ " is not a prime"

 

instance Integral a => Num (Modp a) where

         (Modp q n) + (Modp p m) | p==q = Modp p $ (n+m) `mod` p

                                 | otherwise = error $ "unequal moduli"

         (Modp p n) * (Modp q m) | p==q = Modp p $ (n*m) `mod` p

                                 | otherwise = error $ "unequal moduli"

         negate (Modp p n) = Modp p (p-n)

         -- can't reuse base because ^ is impl. directly in prelude

{-       (Modp p x) ^ n | n <= p  = (Modp p x) `baseExp` n

                        | n1 == 0 = (Modp p x)

                        | n > p   =  x ^ n1

             where baseExp = ^ in Num

                   n1      = n `mod` p

-}

instance Integral a => Fractional (Modp a) where

         recip (Modp p n) = (Modp p n)^(p-2)

 

 

isPrime p = True -- stub


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Implementing instance of '^' operator

Harald Hanche-Olsen
-----Original Message-----
From: [hidden email] <[hidden email]>
Date: 3 January 2016 at 07:55:53

> As a ‘hello world’ example for type definitions, I like to define a numeric type that can  
> handle the mod p multiplicative group, where p is prime. This requires:
> • Implementing interface functions

[…]

I can’t help with the question you’re asking, but I have a minor nitpick: You want to have
negate (Modp p 0) = Modp p 0,
and not Modp p p as in your current implementation.

– Harald
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Implementing instance of '^' operator

Chaddaï Fouché
(^) is _not_ a method of Num, it is simply a function with a Num constraint. It will work on your new numbers as well as it would on any other that implements (*) correctly, you don't need to rewrite it.

By the way, your functions are dangerously partial, it would seem useful to put the prime into the type so that you can't add or multiply different Mod p. Of course this demands a bit more knowledge of Haskell type system than is likely in a beginner, but if you're motivated, I encourage you to look at numbers in type (see GHC.TypeLits maybe).

--
Jedaï

Le dim. 3 janv. 2016 à 14:07, Harald Hanche-Olsen <[hidden email]> a écrit :
-----Original Message-----
From: [hidden email] <[hidden email]>
Date: 3 January 2016 at 07:55:53

> As a ‘hello world’ example for type definitions, I like to define a numeric type that can
> handle the mod p multiplicative group, where p is prime. This requires:
> • Implementing interface functions

[…]

I can’t help with the question you’re asking, but I have a minor nitpick: You want to have
negate (Modp p 0) = Modp p 0,
and not Modp p p as in your current implementation.

– Harald
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners