通过 Nat-kinds 递归

Question

这个问题是对下面问题的 sequel。先参考一下：

现在是创建 Group Symmetric 实例的时候了。经过一些野蛮的数学运算后，我得出了一个原则上可行但实际上行不通的实例：

sIndex :: forall n. KnownNat n => Symmetric n -> Integer -> Integer
sIndex xs m = sIndex_ xs (m `mod` n)
  where
    n = toInteger (natVal (Proxy :: Proxy n))
    sIndex_ :: Symmetric m -> Integer -> Integer
    sIndex_ S1 _ = 0
    sIndex_ (x :. _) 0 = cIndex x
    sIndex_ (x :. xs) m = let
        i = cIndex x + sIndex_ xs (m-1)
        in if i < n then i else i - n

instance KnownNat n => Semigroup (Symmetric n) where
    x <> y = go [] n where
        n = toInteger (natVal (Proxy :: Proxy n))
        go :: forall m. [(Integer,Integer)] -> Integer -> Symmetric m
        go j m
            | 0 == m = S1
            | otherwise = let
                i = sIndex y (sIndex x (n-m))
                ix = foldr f i j
                in cyclic ix :. go ((ix,m) :j) (m-1)
        f (j,m) i = (i - j) `mod` m - 1

Semigroup 实例中的 go 函数应该通过 Symmetric n、Symmetric (n-1) 等递归构建结果，直到 Symmetric 1。但是 GHC 不知道该怎么做并输出以下错误消息：

Group_Symmetric.hs:89:24: error:
    • Couldn't match type ‘m’ with ‘1’
      ‘m’ is a rigid type variable bound by
        the type signature for:
          go :: forall (m :: Nat).
                [(Integer, Integer)] -> Integer -> Symmetric m
        at Group_Symmetric.hs:87:9-69
      Expected type: Symmetric m
        Actual type: Symmetric 1

那么解决方法是什么？ go 是否可以 return Symmetric m 的任何实例（m 从 1 到 n）？

Answer 1

go 和 f 的细微变化解决了问题：

instance KnownNat n => Semigroup (Symmetric n) where
    x <> y = go y [] n where
        n = toInteger (natVal (Proxy :: Proxy n))
        go :: forall m. Symmetric m -> [(Integer,Integer)] -> Integer -> Symmetric m
        go S1 _ _ = S1
        go (_ :. xs) j m = let
            i = sIndex y (sIndex x (n-m))
            ix = foldr f i j
            in Cyclic ix :. go xs ((ix,m) :j) (m-1)
        f (j,m) i = let
            ix = (i - j) `mod` m - 1
            in if 0 <= ix then ix else ix + m

关键思想是引入一个虚拟参数。另请注意，使用 Cyclic 而不是 cyclic。

不幸的是，事实证明我做错了一些数学题。待更正。

编辑： 这是更正后的 sIndex，它完成了实例：

sIndex :: forall n. KnownNat n => Symmetric n -> Integer -> Integer
sIndex xs m = let
    n = toInteger (natVal (Proxy :: Proxy n))
    in sIndex_ xs (m `mod` n) n
  where
    sIndex_ :: Symmetric m -> Integer -> Integer -> Integer
    sIndex_ S1 _ _ = 0
    sIndex_ (x :. _) 0 _ = cIndex x
    sIndex_ (x :. xs) m n = let
        i = cIndex x + sIndex_ xs (m-1) (n-1) + 1
        in if n <= i then i - n else i

通过 Nat-kinds 递归

Recursion through Nat-kinds

math

recursion

haskell

gadt

data-kinds