Haskell：如何为依赖于参数的东西编写一个“Monoid”实例

Question

我正在为大学开发一个小型图书馆，该图书馆在 cyclic group 中进行整数计算；像这样的东西：

(3 (% 11)) + (10 (% 11))
--> (2 (% 11))

'Integers (% n)' 以 '0 (% n)' 作为恒等元在加法下明显形成幺半群。然而，加法只有在被加的两个操作数的模相同时才有意义：a (% n) + b (% n) 有意义，而 a (% n) + b (% m) 没有。

有什么方法可以用 Haskell 的类型系统强制执行此操作吗？ mempty 身份元素当然也是如此：如何构造 0 (% n)？ n 能否以某种方式保留在类型系统中？

或者像这样的结构需要使用依赖类型吗？

Answer 1

扩展我的评论，这是第一次尝试。模数由类型强制执行，而不是代表的规范选择：这只是通过计算完成的，因此需要一个抽象障碍。有界数的类型也可用，但它们需要更多的工作。

输入，{-# LANGUAGE KitchenSink #-}。我的意思是（实际上还不错）

{-# LANGUAGE DataKinds, GADTs, KindSignatures, FlexibleInstances #-}

让我们开始吧。

首先，我条件反射地介绍一下随机自然数：

data Nat = Z | S Nat              -- type-level numbers
data Natty :: Nat -> * where      -- value-level representation of Nat
  Zy :: Natty Z
  Sy :: Natty n -> Natty (S n)
class NATTY n where               -- value-level representability
  natty :: Natty n
instance NATTY Z where
  natty = Zy
instance NATTY n => NATTY (S n) where
  natty = Sy natty

在我看来，这就是您想要声明一个数据类型然后允许其他类型依赖于它的值时所做的事情。 Richard Eisenberg 的 "singletons" 库自动构建。

（如果这个例子继续使用数字来索引向量，一些人指出 () 的向量也可以作为 Nat 的单例。他们在技术上是正确的，当然, 但被误导了。当我们认为 Natty 和 NATTY 是系统地从 Nat 生成的时，它们是我们可以根据需要利用或不利用的权利，而不是额外的证明。这个例子不涉及向量，引入向量只是为了 Nat 的单例是有悖常理的。）

我手动滚动了一堆转换函数和 Show 个实例，这样我们就可以看到我们在做什么，而不是其他任何东西。

int :: Nat -> Integer
int Z = 0
int (S n) = 1 + int n

instance Show Nat where
  show = show . int

nat :: Natty n -> Nat
nat Zy = Z
nat (Sy n) = S (nat n)

instance Show (Natty n) where
  show = show . nat

现在我们可以宣布 Mod。

data Mod :: Nat -> * where
  (:%) :: Integer -> Natty n -> Mod (S n)

类型携带模数。这些值带有等价的非规范化代表 class，但我们最好弄清楚如何对其进行规范化。一元数除法是我小时候学的一项奇特的运动。

remainder :: Natty n   -- predecessor of modulus
          -> Integer   -- any representative
          -> Integer   -- canonical representative
  -- if candidate negative, add the modulus
remainder n x | x < 0 = remainder n (int (nat (Sy n)) + x)
  -- otherwise get dividing
remainder n x = go (Sy n) x x where
  go :: Natty m  -- divisor countdown (initially the modulus)
     -> Integer  -- our current guess at the representative
     -> Integer  -- dividend countdown
     -> Integer  -- the canonical representative
    -- when we run out of dividend the guessed representative is canonical
  go _      c 0 = c
    -- when we run out of divisor but not dividend,
    --   the current dividend countdown is a better guess at the rep,
    --   but perhaps still too big, so start again, counting down
    --   from the modulus (conveniently still in scope)
  go Zy     _ y = go (Sy n) y y
    -- otherwise, decrement both countdowns
  go (Sy m) c y = go m c (y - 1)

现在我们可以做一个智能构造器了。

rep :: NATTY n                 -- we pluck the modulus rep from thin air
    => Integer -> Mod (S n)    -- when we see the modulus we want
rep x = remainder n x :% n where n = natty

然后 Monoid 实例很简单：

instance NATTY n => Monoid (Mod (S n)) where
  mempty                    = rep 0
  mappend (x :% _) (y :% _) = rep (x + y)

我也加入了一些其他东西：

instance Show (Mod n) where
  show (x :% n) = concat ["(", show (remainder n x), " :% ", show (Sy n), ")"]
instance Eq (Mod n) where
  (x :% n) == (y :% _) = remainder n x == remainder n y

稍微方便一下...

type Four = S (S (S (S Z)))

我们得到

> foldMap rep [1..5] :: Mod Four
(3 :% 4)

所以是的，你确实需要依赖类型，但是 Haskell 依赖类型就足够了。

Answer 2

这与@pigworker 给出的答案相同，但以一种不那么痛苦（更高效、更好的语法）的方式编写。

{-# LANGUAGE DataKinds, KindSignatures, ScopedTypeVariables #-}
module Mod(Mod) where
import Data.Proxy
import GHC.TypeLits

data Mod (n :: Nat) = Mod Integer

instance (KnownNat n) => Show (Mod n) where
    showsPrec p (Mod i) = showParen (p > 0) $
      showsPrec 0 i . showString " :% " . showsPrec 0 (natVal (Proxy :: Proxy n))

instance Eq (Mod n) where
    Mod x == Mod y = x == y

instance forall n . (KnownNat n) => Num (Mod n) where
    Mod x + Mod y = Mod $ (x + y) `mod` natVal (Proxy :: Proxy n)
    Mod x - Mod y = Mod $ (x - y) `mod` natVal (Proxy :: Proxy n)
    Mod x * Mod y = Mod $ (x * y) `mod` natVal (Proxy :: Proxy n)
    fromInteger i = Mod $ i `mod` natVal (Proxy :: Proxy n)
    abs x = x
    signum x = if x == 0 then 0 else 1

instance (KnownNat n) => Monoid (Mod n) where
    mempty = 0
    mappend = (+)

instance Ord (Mod n) where
    Mod x `compare` Mod y = x `compare` y

instance (KnownNat n) => Real (Mod n) where
    toRational (Mod n) = toRational n

instance (KnownNat n) => Enum (Mod n) where
    fromEnum = fromIntegral
    toEnum = fromIntegral

instance (KnownNat n) => Integral (Mod n) where
    quotRem (Mod x) (Mod y) = (Mod q, Mod r) where (q, r) = quotRem x y
    toInteger (Mod i) = i

然后我们得到

> foldMap fromInteger [1..5] :: Mod 4
3 :% 4
> toInteger (88 * 23 :: Mod 17)
1
> (3 :: Mod 4) == 7
True

该模块还说明了我在您关于 Eq 的问题的评论中提出的观点。在 Mod 模块之外你不能欺骗和使用表示。

Answer 3

除了前面的答案之外，您可能对 modular-arithmetic 包感兴趣，该包将其实现为具有非常好的语法的库。

>>> import Data.Modular
>>> 10 * 11 :: ℤ/7
5

Haskell：如何为依赖于参数的东西编写一个“Monoid”实例

Haskell: How to write a `Monoid` instance for something that depends on parameters

haskell

monoids

dependent-type