Получение GHC для принятия подписи типа с помощью арифметики KnownNat

Я пытался реализовать китайскую теорему об остатках для конкретном случае всего двух уравнений с использованием данных . Модульный пакет. Идея состоит в том, что я могу указать каждое уравнение только с одним модульным числом (x = a (mod m), используя число a (mod m)). Вот моя реализация.

{-# LANGUAGE DataKinds, ScopedTypeVariables, TypeOperators #-}

import GHC.TypeLits
import Data.Proxy (Proxy (..))
import Data.Modular

crt :: forall k1 k2 i. (KnownNat k1, KnownNat k2, Integral i) => i `Mod` k1 -> i `Mod` k2 -> i `Mod` (k1 * k2)
crt a1 a2 = toMod $ (unMod a1)*n2*(unMod n2') + (unMod a2)*n1*(unMod n1')
  where n1 = getModulus a1 :: i
        n2 = getModulus a2 :: i
        n2' = inv $ (toMod n2 :: i `Mod` k1)
        n1' = inv $ (toMod n1 :: i `Mod` k2)

        getModulus :: forall n i j. (Integral i, Integral j, KnownNat n) => i `Mod` n -> j
        getModulus x = fromInteger $ natVal (Proxy :: Proxy n)

Я получаю следующую ошибку: Could not deduce (KnownNat (k1 * k2)) arising from a use of ‘toMod’. Однако разве GHC не должен выполнять арифметические действия для KnownNat (k1 * k2)? Кроме того, по какой-то странной причине, похоже, если бы у меня был конструктор для типа Mod вместо функции toMod, все бы работало. Я тоже не понимаю, как это должно иметь значение...

Я ищу любое исправление, чтобы помочь скомпилировать, включая любые расширения. Однако я хотел бы не создавать свою собственную версию Data.Modular, если это возможно. (Я думаю, что я мог бы сделать эту работу неэлегантной и неуклюжей, используя конструктор Mod напрямую).


person Alec    schedule 03.06.2015    source источник
comment
GHC 7.8 на самом деле не может выполнять какие-либо арифметические операции вообще, его Nat в значительной степени такие же тупые (потому что такие же общие), как и любые другие типы. Я думаю, что только 7.12 сможет сделать все это именно так, как вам хотелось бы. (Но я думаю, что есть какой-то плагин, который работает даже в 7.8.)   -  person leftaroundabout    schedule 03.06.2015
comment
@leftaroundabout: это плагин.   -  person András Kovács    schedule 03.06.2015
comment
@leftaroundabout У меня сейчас 7.10, если это поможет. Раньше у меня работала простая арифметика с Nats, за исключением этого особого случая.   -  person Alec    schedule 03.06.2015


Ответы (1)


Дешевый, дрянной способ сделать эту компиляцию состоит в том, чтобы добавить FlexibleContexts, а затем добавить KnownNat (k1 * k2) в контекст crt. Как только я это сделал, я мог бы успешно вызвать это в ghci:

> crt (3 :: Mod Integer 5) (5 :: Mod Integer 7)
33

Получайте удовольствие от того, как выразить Coprime k1 k2 как ограничение... ;-)

person Daniel Wagner    schedule 03.06.2015
comment
Я ничего не знаю о FlexibleContexts, но я посмотрю, а потом вернусь и приму этот ответ. Надеюсь, к тому времени я полностью оценю вашу последнюю шутку. :-) - person Alec; 04.06.2015
comment
@Alec Алек О, последняя строка не имеет ничего общего с гибкими контекстами. Это просто признание того, что программирование на уровне типов — печально известная трата времени. - person Daniel Wagner; 04.06.2015
comment
Ха-ха, да, я понял, просто хотел посмотреть, как мало FlexibleContexts даст мне, но да. Большое спасибо за это решение! Я понятия не имею, как ты это придумал. - person Alec; 04.06.2015
comment
@Alec Как я это придумал, на самом деле довольно просто: я просто следил за ошибками. Ошибка говорит, что невозможно доказать ограничение, поэтому я дал ограничение как аксиому; следующая ошибка говорила, что ограничение недействительно, если вы не включите FlexibleContexts, поэтому я включил его. На самом деле GHC проделал всю тяжелую работу. - person Daniel Wagner; 04.06.2015