Тип данных для конечных полей в Haskell?

Question

Я пытаюсь немного изучить Haskell, написав небольшой набор функций для вычислений над конечными полями (Галуа). Несколько лет назад я написал первую версию подобной библиотеки для системы компьютерной алгебры GNU Maxima ( см. Здесь) и подумал, что попробую то же самое с Haskell.

Тем не менее, я все путаюсь с типами данных. Для конечного поля вам понадобится базовое простое число q (характеристика поля) и многочлен p(x), который неприводим по модулю q. Если p(x) имеет степень n, то порядок поля равен q^n, и все его элементы являются полиномами (по модулю q) со степенью n-1 или меньше.

Мы можем представить многочлены в виде списков их коэффициентов, так что элементы поля являются просто списками (или векторами, если вы предпочитаете) элементов Z_q и длины n. Сложение выполняется по компонентам по модулю q, а умножение выполняется по модулю p(x).

Я рассчитываю, смогу ли я получить тип данных, и сложение будет отсортировано, остальное будет просто. Моя первая попытка такая:

import Data.List

data GF = GF {characteristic::Int
             ,power::Int
             ,poly::[Int]
             ,irreducible::[Int]
             } deriving(Eq, Show)

Элемент степени не нужен - он, в конце концов, просто на единицу меньше длины неприводимого полинома - но его удобнее иметь, а не вычислять.

Тогда у меня была функция сложения:

addGF :: GF -> GF -> GF
addGF x y = GF q n zp p
  where
    q = characteristic x
    n = power x
    zp = zipWith (\i j -> rem (i+j) q) xp yp
      where
        xp = poly x
        yp = poly y
    p = irreducible x

Это работает, но не элегантно, и я уверен, что очень "не-Хаскель-иш". Частично проблема в том, что я не знаю, как отделить определение (или тип) поля Галуа от его элементов.

Что мне нужно сделать, так это предоставить общий тип поля, а поверх него определить его элементы. В конце концов, есть вещи, которые я мог бы захотеть сделать с полем, которые не зависят от его элементов, такие как генерация нормального базиса, поиск примитивного элемента, генерация таблицы логарифмов для примитивного элемента, генерация случайных элементов и т. Д.

Поэтому я предполагаю, что мой вопрос таков: как определить универсальный тип поля Галуа таким образом, чтобы операции над его элементами были максимально естественными?

Я прочитал несколько страниц об определении типов данных, классов и т. Д., И я не сомневаюсь, что одна из них содержит решение моей проблемы. Но чем больше я читаю, тем больше смущаюсь. Все, чего я хочу, это чтобы кто-то мягко, но твердо указал мне правильное направление. Спасибо!

Answer 1

Я не думаю, что ваш GF тип уродлив или неверен. Основная проблема, которую я вижу, заключается в том, что addGF не гарантирует, что элементы действительно могут быть добавлены. Вместо этого вы можете сделать:

addGF :: GF -> GF -> Maybe GF
addGF x y -- the pipes below are called "guards", a multi-way `if` syntax
  | q == characteristic y && n == power y && p == irreducible y = Just $ GF q n zp p
  | otherwise = Nothing
  where
    q = characteristic x
    n = power x
    zp = zipWith (\i j -> rem (i+j) q) xp yp
      where
        xp = poly x
        yp = poly y
    p = irreducible x

Возможно, было бы более эргономично и полезно (но не принципиально другое решение) отделить понятие поля от его элементов, например так:

-- these names are probably not appropriate
data Field  
  = Field { characteristic::Int
          , power::Int
          , irreducible::[Int]
          } deriving(Eq, Show)

-- formerly `GF`:
data FieldElement
  = FieldElement 
          { field::Field
          , poly::[Int]
          } deriving(Eq, Show)

Тогда в охраннике выше, вам просто нужно сделать, например,

...
| field x == field y = Just $ ...

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

Если вы знаете, что будете работать с определенными полями с параметрами, известными во время компиляции, то вы можете позволить средству проверки типов принудительно применить инвариант в addGF для тебя. Один из способов будет выглядеть так:

-- see `Data.Proxy` for info about this idiom
class SomeField f where
   characteristic :: proxy f -> Int
   power :: proxy f -> Int
   irreducible :: proxy f -> [Int]

-- A field element is just the polynomial, tagged with its field using the `f` type parameter
-- you may want to not expose the internals of `GF` but instead expose a 
-- makeGF function which enforces whatever invariants should hold between the parameters
-- of a field and the polynomial of its element.
newtype GF f = GF { poly :: [Int] }

-- `addGF` is no longer partial; the type system enforces that both arguments are elements of the same field
addGF :: (SomeField f)=> GF f -> GF f -> GF f
addGF x@(GF xp) (GF yp) = GF $ zipWith (\i j -> rem (i+j) q) xp yp
  where q = characteristic x

Я упомянул "векторы" только потому, что они являются причиной проблемы, и различные подходы, которые у вас здесь открыты, такие же, как у вас с векторной арифметикой, в которой, например, могут быть добавлены только векторы одного измерения.

Answer 2

Это достаточно легко поднять characteristic а также power в систему типов в современном Haskell (GHC>=7,8), то есть

{-# LANGUAGE TypeOperators, DataKinds #-}
{-# LANGUAGE FlexibleContexts, TypeFamilies, UndecidableInstances #-}
{-# LANGUAGE StandaloneDeriving #-}

и выражаем, что коэффициенты полиномов происходят из конечной группы, размер которой является характеристикой:

import GHC.TypeLits
import Data.Modular

data GF χ -- characteristic
        n -- power
   = GF { irreducible :: [ℤ/χ]
        , poly :: [ℤ/χ]
        }

Это уже дает вам бесплатно, что любые добавления на полиномах будут по модулю χ,

Вы могли бы также выразить, что всегда есть n + 1 коэффициенты:

import qualified Data.Vector.Fixed as Fix
import qualified Data.Vector.Fixed.Boxed as Fix

data GF χ n
   = GF { irreducible :: Fix.Vec (n+1) (ℤ/χ)
        , poly :: Fix.Vec (n+1) (ℤ/χ)
        }
deriving instance (KnownNat χ, Fix.Arity (n+1)) => Show (GF χ n)

addGF :: (KnownNat χ, Fix.Arity (n+1))
           => GF χ n -> GF χ n -> GF χ n
addGF (GF irr xp) (GF irr' yp)
 | irr==irr'  = GF irr $ Fix.zipWith (+) xp yp
 | otherwise  = error "Cannot add elements of finite fields with different irreducible polynomials!"

main = print (GF irr (Fix.fromList [0,0,1]) `addGF` GF irr (Fix.fromList [0,1,1])
               :: GF 2 2)
 where irr = Fix.fromList [1,1,1]

Результат:

GF {irreducible = fromList [1,1,1], poly = fromList [0,1,0]}

Все еще уродливо, что мы должны проверять во время выполнения неприводимый многочлен. Хотя в принципе можно было бы поднять это и до уровня шрифта, я не уверен, что это действительно сработает; мы уже настаиваем на том, насколько хорошо Haskell может использоваться в качестве языка с зависимой типизацией. Возможно, было бы достаточно выбрать для каждой характеристики и степени только один раз неприводимый многочлен, который всегда будет использоваться?