generate a random number in Haskell

I have finally figured out how to generate a random number, but the compiler still complains on my code.

Code:

type Quot   = Integer

sign (p,q,g) (x,pub) d =
       do k <- randomRIO(1,q-1 :: Integer)
   ki <- kinv k q
   r <- g^k `mod` p
   s <- (160 + x*r)*ki mod q
   return (r,s)

kinv :: Integer -> Quot -> Integer
kinv k q =
   do (d,t,s) <- gcdE(q,k)
      return s

gcdE(a,0) = (a,1,0)
gcdE(a,b) = (d,t,s - q*t)
    where r = a `mod` b
         q = a `div` b
        (d,s,t) = gcdE(b,r)

Error message:

crypt.hs:24:7:
Couldn't match expected type `Integer' against inferred type `m a'
In a stmt of a 'do' expression: ki <- kinv k q
In the expression:
    do { k <- randomRIO (1, q - 1 :: Integer);
         ki <- kinv k q;
         r <- g ^ k `mod` p;
         s <- (160 + x * r) * ki mod q;
         .... }
In the definition of `sign':
    sign (p, q, g) (x, pub) d
           = do { k <- randomRIO (1, q - 1 :: Integer);
                  ki <- kinv k q;
                  r <- g ^ k `mod` p;
                  .... }

crypt.hs:37:10:
Couldn't match expected type `Integer'
       against inferred type `(Quot, Quot, b)'
In a stmt of a 'do' expression: (d, t, s) <- gcdE (q, k)
In the expression:
    do { (d, t, s) <- gcdE (q, k);
         return s }
In the definition of `kinv':
    kinv k q
           = do { (d, t, s) <- gcdE (q, k);
                  return s }

All I 开发者_开发技巧want is for the variable k to take a random integer value between 0 < k < q. I am not so good with Haskell so this has taken a while. Thanks.

Following is a fix, the thing is that a do construct is used to bind monadic values, and randomRIO(1,q-1) is of type IO a, and IO is a monad, however kniv k q is of type integer so it doesn't fit in with the other IO monad functions in the do construct. I urge you to read a monad tutorial.

sign (p,q,g) (x,pub) d = do
   k <- randomRIO(1,q-1)
   let ki =  kinv k q
   let r  =  mod ( g^k) p
   let s  = mod ((160 + x*r)*ki) q
   return (r,s)

kinv k q = s
   where (_,_,s) = gcdE(q,k)

gcdE(a,0) = (a,1,0)
gcdE(a,b) = (d,t,s - q*t)
    where r = a `mod` b
          q = a `div` b
          (d,s,t) = gcdE(b,r)

It should be noted that sign now is an IO function, so it can't be used in pure code. It is still possible to have pure functions depending on random generators, by encapsulating the seeded value and passing it along in a state monad. This way is described in Real World Haskell.

Since there's nothing monadic about kinv or gcdE, neither of them should contain any dos, <-s or returns.

Similarly you don't need to (and can't) use <- to get the result of kinv and gcdE. The same is true for any arithmetic operators. Just use let result = non-monadic operation, not result <- non-monadic operation.

sometimes it is a good idea to use monads sparingly, if you don't really need them in computations.

sign a@(_,q,_) (x,pub) d = sign' a x <$> randomRIO(1,q-1)

sign' (p,q,g) x k = (r,s)
  where r = mod (g ^ k) p
        s = mod ((160 + x * r) * kinv k q) q

kinv k q = let (_,_,s) = gcdE(q,k) in s

gcdE(a,0) = (a,1,0)
gcdE(a,b) = (d,t,s - q*t)
    where r = a `mod` b
          q = a `div` b
          (d,s,t) = gcdE(b,r)

So you can even test the sign' function more easily if something is weird...