Geek Answers Handbook

Haskell's flaw about (Bits a) inferenced type error

I experiment with some math functions and come up with the following:

import Data.Bits

mulGF2n a b g = divModGF2n (mulGF2 a b) g
  where
    mulGF2 a b
      | a == zeroBits = zeroBits
      | otherwise     = xor (if testBit a 0 then b else zeroBits) (mulGF2 (shiftR a 1) (shiftL b 1))

divModGF2n a b = go a zeroBits
  where
    n      = log2 b
    log2 a = let x = shiftR a 1 in if x == zeroBits then 0 else 1 + log2 x
    go a q
      | r < 0     = (q, a)
      | otherwise = go (xor a (shiftL b r)) (q .|. bit r)
      where
        r = log2 a - n

These are Galois calculations, but they are not important. Notice that I did not consider type signatures.

GHCI tells me about the alleged types:

*Main> :t divModGF2n
divModGF2n :: (Bits t1, Bits t) => t -> t -> (t1, t)

*Main> :t mulGF2n
mulGF2n :: (Bits a, Bits t1, Bits t) => a -> t -> t -> (t1, t)

So far so good. I am trying to change a function mulGF2nso that instead of returning a type tuple (t1, t), it only returns the second element of the type t. I am changing the first line of the function:

mulGF2n a b g = divModGF2n (mulGF2 a b) g

at

mulGF2n a b g = snd $ divModGF2n (mulGF2 a b) g

Now GHCI gives me this error:

Could not deduce (Bits a0) arising from a use of ‘divModGF2n’
from the context (Bits a, Bits b)
  bound by the inferred type of
           mulGF2n :: (Bits a, Bits b) => a -> b -> b -> b
  at polydiv.hs:(12,1)-(16,100)
The type variable ‘a0’ is ambiguous
Note: there are several potential instances:
  instance Bits Bool -- Defined in ‘Data.Bits’
  instance Bits Int -- Defined in ‘Data.Bits’
  instance Bits Integer -- Defined in ‘Data.Bits’
  ...plus one other
In the first argument of ‘snd’, namely
  ‘(divModGF2n (mulGF2 a b) g)’
In the expression: snd (divModGF2n (mulGF2 a b) g)
In an equation for ‘mulGF2n’:
    mulGF2n a b g
      = snd (divModGF2n (mulGF2 a b) g)
      where
          mulGF2 a b
            | a == zeroBits = zeroBits
            | otherwise
            = xor
                (if testBit a 0 then b else zeroBits)
                (mulGF2 (shiftR a 1) (shiftL b 1))

The same thing happens if used instead mulGF2n a b g = let (q, r) = divModGF2n (mulGF2 a b) g in r. What is the reason that I believe the tuple, but not the second element of the tuple? This can help if I know that the type a0is mentioned in the error, but it only complains about the type, but does not tell me which one it refers to.

+4
3

, .

:

class C a where def :: (Int, a)

f :: (Eq a, C a) => Int -> (a, Bool)
f x = let (y,z) = def in (z, x==y)

: a ( C) a Bool. , , a. , , :

> instance C Char where def = (0, 'a')
> instance C ()   where def = (1, () ) 
> f 0 :: (Char,Bool)
('a', True)
> f 0 :: ((), Bool)
((), False)

:

> snd (f 0) :: Bool

: True, False , a f. , a, .

:

f :: (Eq a, C a) => Int -> (a, Bool)   -- OK
f 0 :: (Eq a, C a) => (a, Bool)        -- OK
snd (f 0) :: (Eq a, C a) => Bool       -- NOT OK

, a , , .

, a , .

snd (f 0 :: (Char, Bool)) :: Bool       -- OK


mulGF2n :: (Bits a, Bits t1, Bits t) => a -> t -> t -> (t1, t)

,

g :: (Bits a, Bits t1, Bits t) => a -> t -> t -> t
g a b c = snd $ mulGF2n a b c

t1 , . t1=t, :

g :: (Bits a, Bits t) => a -> t -> t -> t
g a b c = y `asTypeOf` x
     where (x,y) = mulGF2n a b c

asTypeOf Haskell , y x .

asTypeOf :: a -> a -> a
asTypeOf x y = x

, a -> b -> a, . , , .

( - ScopedTypeVariables, .)

+2

, , log2 divModGF2n . log2 .

log2 :: (Bits a, Num n) => a -> n
log2 a = let x = shiftR a 1 in if x == zeroBits then 0 else 1 + log2 x

divModGF2n

divModGF2n a b = go a zeroBits
  where
    n      = log2 b
    go a q
      | r < 0     = (q, a)
      | otherwise = go (xor a (shiftL b r)) (q .|. bit r)
      where
        r = log2 a - n

go, q , . zeroBits :: Bits a => a. q .|. bit r. bit :: Bits a => Int -> a (.|.) :: Bit a => a -> a -> a. q, , , (q, a). divModGF2n t1.

:t divModGF2n
divModGF2n :: (Bits t1, Bits t) => t -> t -> (t1, t)

, , .

modGF2n :: Bits a => a -> a -> a
modGF2n a b = let (q, r) = divModGF2n a b
              in r

.

Could not deduce (Bits a0) arising from a use of `divModGF2n'
from the context (Bits a)

, divModGF2n , , . modGF2n , . Bits , divModGF2n. .

, , divModGF2n . modGF2n, , Bits , , .

{-# LANGUAGE ScopedTypeVariables #-}

modGF2n :: Bits a => a -> a -> a
modGF2n a b = let (q :: Bool,r) = divModGF2n a b
              in r
+1

t1 mulGF2n , . GHC , , .

:

default ()

example :: (Num a, Num b) => (a, b)
example = (1, 2)

exampleFst :: Num a => a
exampleFst = fst example

( default (), GHC , Num. .)

, GHC , Num b example. , , , . , :

{-# LANGUAGE ScopedTypeVariables #-}
exampleFst :: forall a. Num a => a
exampleFst = fst (example :: (a, a))

ScopedTypeVariables GHC, , a , a exampleFst ( forall, ).

.

0

More articles:


All Articles