Haskell путаница (биты а) inferenced типа ошибка

Question

Я экспериментировал с некоторыми математическими функциями и придумал следующее:

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 

Они вычисление поля Галуа, но то, что они не являются важный. Заметьте, что я не указывал подписи типов.

GHCI говорит мне следующее о предполагаемых типов:

*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) 

До сих пор так хорошо. Я пытаюсь изменить функцию mulGF2n, так что вместо возврата кортежа типа (t1, t) он возвращает только второй элемент типа t. Я изменяю первую строку функция от:

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

к:

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

Теперь GHCI дает мне эту ошибку:

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)) 

То же самое происходит, если я использую вместо mulGF2n a b g = let (q, r) = divModGF2n (mulGF2 a b) g in r. В чем причина того, что я верю кортеж, но не второй элемент кортежа? Это могло бы помочь, если бы я знал, что относится к типу a0, но он только жалуется на тип, но не говорит мне, к какому из них относится.

Answer 1

Я объясню проблему, используя более простой пример.

Рассмотрим это:

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) и 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 предусмотрена в Prelude Haskell только с целью создания типов y и x равны. Его определение просто следующий

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

Обратите внимание, что выше, может иметь более общий тип a -> b -> a, но она определяется с выше stricted типа. Это делается специально, поэтому компилятору сообщают, что оба аргумента имеют один и тот же тип.

(Другой распространенный способ сделать это позволяет продлить ScopedTypeVariables, но это немного слишком для этого простого случая.)

Answer 2

Переменная 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, когда это расширение включено).

Аналогичный подход может быть использован для решения вашей ошибки типа.

Answer 3

Чтобы посмотреть, что происходит, сначала мы отделим 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). Вот почему есть дополнительная переменная типа t1 в подписи для divModGF2n.

: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