将 Ord 实例添加到 'singleton' 包生成的自然资源
Adding an Ord instance to 'singleton' package generated naturals
我正在使用由 singletons 包生成的非常简单的类型级自然数。我现在正在尝试向它们添加一个 Ord 实例。
{-# LANGUAGE MultiParamTypeClasses, TemplateHaskell, KindSignatures, DataKinds, ScopedTypeVariables, GADTs, TypeFamilies, FlexibleInstances, TypeOperators, UndecidableInstances, InstanceSigs #-}
module Functions where
import Data.Singletons
import Data.Singletons.TH
import Data.Singletons.Prelude
import Data.Promotion.Prelude
singletons [d|
data Nat = Z | S Nat
deriving Eq
instance Ord Nat where
(<=) Z _ = True
(<=) (S _) Z = False
(<=) (S n) (S m) = n <= m
|]
我一个接一个地遇到错误。最新的是：
src/Functions.hs:10:1:
Couldn't match kind ‘Nat’ with ‘*’
When matching types
n0 :: Nat
t1 :: *
Expected type: Sing t1
Actual type: Sing n0
Relevant bindings include
n_a9na :: Sing n0 (bound at src/Functions.hs:10:1)
lambda :: Sing n0 -> Sing m0 -> Sing (Apply (Apply (:<=$) t00) t10)
(bound at src/Functions.hs:10:1)
In the second argument of ‘applySing’, namely ‘n_a9na’
In the first argument of ‘applySing’, namely
‘applySing (singFun2 (Proxy :: Proxy (:<=$)) (%:<=)) n_a9na’
src/Functions.hs:10:1:
Could not deduce (SOrd 'KProxy) arising from a use of ‘%:<=’
from the context (t00 ~ 'S n)
bound by a pattern with constructor
SS :: forall (z_a9mg :: Nat) (n_a9mh :: Nat).
(z_a9mg ~ 'S n_a9mh) =>
Sing n_a9mh -> Sing z_a9mg,
in an equation for ‘%:<=’
at src/Functions.hs:(10,1)-(18,15)
or from (t10 ~ 'S n1)
bound by a pattern with constructor
SS :: forall (z_a9mg :: Nat) (n_a9mh :: Nat).
(z_a9mg ~ 'S n_a9mh) =>
Sing n_a9mh -> Sing z_a9mg,
in an equation for ‘%:<=’
at src/Functions.hs:(10,1)-(18,15)
or from (t00 ~ Apply SSym0 n0, t10 ~ Apply SSym0 m0)
bound by the type signature for
lambda_a9n9 :: (t00 ~ Apply SSym0 n0, t10 ~ Apply SSym0 m0) =>
Sing n0 -> Sing m0 -> Sing (Apply (Apply (:<=$) t00) t10)
at src/Functions.hs:(10,1)-(18,15)
In the second argument of ‘singFun2’, namely ‘(%:<=)’
In the first argument of ‘applySing’, namely
‘singFun2 (Proxy :: Proxy (:<=$)) (%:<=)’
In the first argument of ‘applySing’, namely
‘applySing (singFun2 (Proxy :: Proxy (:<=$)) (%:<=)) n_a9na’
有谁知道正确的做法是什么？
我不确定为什么会失败。我同样对实施 compare 时遇到的类似失败感到困惑，而对尝试（看似简单）
时遇到的失败更感到困惑
singletons [d| data Nat = Z | S Nat deriving (Eq,Ord) |]
我的猜测是 Ord 中的某些内容已关闭...但是，这有效。稍后我会试着看看 singleton 的胆量。
singletons [d|
data Nat = Z | S Nat
deriving (Eq)
instance Ord Nat where
compare = compare'
compare' :: Nat -> Nat -> Ordering
compare' Z Z = EQ
compare' (S _) Z = GT
compare' Z (S _) = LT
compare' (S n) (S m) = compare' n m
|]
顺便说一下，我这里使用的是 GHC 8.0。
编辑
在 singletons 中四处寻找之后，我找到了问题的真正根源（并且被多少类型级别的黑客攻击所震撼）。使用 GHC 中的 -ddump-splices 我能够生成实际的 Haskell 代码（对于您问题中的初始代码）。有问题的部分是
instance PEq (Proxy :: Proxy Nat_a7Vb) where
type (:==) (a_a8Rs :: Nat_a7Vb) (b_a8Rt :: Nat_a7Vb) = Equals_1627424016_a8Rr a_a8Rs b_a8Rt
和
instance POrd (Proxy :: Proxy Nat_a7Vb) where
type (:<=) (a_aa9e :: Nat_a7Vb) (a_aa9f :: Nat_a7Vb) = Apply (Apply TFHelper_1627428966Sym0 a_aa9e) a_aa9f
编译生成的代码，我收到了关于这两个的稍微更有用的错误消息
Expecting one more argument to ‘Proxy’
Expected kind ‘Proxy Nat_a7Vb’, but ‘Proxy’ has kind ‘k0 -> *’
属于PEq和POrd中的(Proxy :: Proxy Nat_a7Vb)类。没有 -XPolyKinds 就无法编译。检查了 singletons 的回购协议，实际上它告诉您需要启用 -XTypeInType，这又会启用 -XPolyKinds.
所以，没有错误，你只需要添加 PolyKinds 或 TypeInType （我推荐后者，因为这是软件包推荐的......）到你的 LANGUAGE 使一切正常工作的编译指示。
使用提升的布尔关系 comfortable。布尔运算会抹掉您有兴趣学习的信息，让您在想要对测试结果做任何事情时陷入困境。就说不吧，孩子们。
有更好的方法。 “n 是 less-than-or-equal 到 m”是一个 命题 可以 证明 和 information-rich 证据。证明一个数字小于另一个数字的一种方法是给出它们的差异（单例表示）：
data LE n m where
LE :: Natty z -> LE n (n :+ z)
我们可以想出一个程序来测试给定的数字是否小于另一个。 le 尝试从 m 中减去 n，并且失败并且 returns Nothing 或产生它们的差异，作为 Natty，以及证明减法是正确的，打包在 LE 构造函数中。
le :: Natty n -> Natty m -> Maybe (LE n m)
le Zy m = Just (LE m)
le (Sy n) (Sy m) = fmap (\(LE z) -> LE z) (le n m)
le _ _ = Nothing
这个想法可以推广给我们"strongly-typed compare"。比较两个数字时，您会发现它们相等，或者一个小于另一个。 （Either (LE n m) (LE m n) 也能完成这项工作，但这个版本稍微更精确一些。）
data Compare n m where
LT :: Natty z -> Compare n (n :+ S z)
EQ :: Compare n n
GT :: Natty z -> Compare (m :+ S z) m
compare :: Natty n -> Natty m -> Compare n m
compare Zy Zy = EQ
compare Zy (Sy m) = LT m
compare (Sy n) Zy = GT n
compare (Sy n) (Sy m) = case compare n m of
LT z -> LT z
EQ -> EQ
GT z -> GT z
（我从 Hasochism 中提取了这个。）
请注意，与 le 不同，compare 是总数。它会总是 给你一个结果：每个数字要么小于、等于或大于其他数字。我们的目标是编写一个程序来测试两个数字中哪个更小，但我们也发现自己要证明数字是 totally ordered，并编写一个 type-safe 减法例程，所有这些都在同一个函数中。
另一种查看 compare 的方法是 查看 自然数对。当你比较两个数字时，你会知道哪个数字少了多少，从而完善了你对数字本身的了解。 Agda 的 dot-patterns 很好地支持了这种细化的概念：
compare : (n m : Nat) -> Compare n m
compare zero zero = eq
compare zero (suc m) = lt m
compare (suc n) zero = gt n
compare (suc n) (suc m) with compare n m
-- see how matching on `lt` refines `m` to `n + suc z`
compare (suc n) (suc .(n + suc z)) | lt z = lt z
compare (suc m) (suc .m) | eq = eq
-- likewise matching on `gt` refines `n` to `m + suc z`
compare (suc .(m + suc z)) (suc m) | gt z = gt z
无论如何，我不能直接说出你的 singletons 错误的来源，但是 Ord 很难处理单例值的一个原因是它假设你正在比较相同类型的值：
class Ord a where
compare :: a -> a -> Ordering
当您比较两个单例时，它们通常不会具有相同的类型！这就是单身人士的全部要点：他们的类型直接反映了他们的价值。如果您有两个 Natty n 值（它们的 n 匹配），则比较它们没有多大意义，因为您已经知道它们是相等的；如果它们不相等，则无法比较它们！
在 simply-typed 世界中设计的 类 和 Ord 一样，在 dependently-typed 程序中不一定那么有用，这是非常合理的。如果您使用依赖类型，正确的做法是不要滥用旧工具。迎接这个安全的新世界，information-rich张开双臂编程！
我正在使用由 singletons 包生成的非常简单的类型级自然数。我现在正在尝试向它们添加一个 Ord 实例。
{-# LANGUAGE MultiParamTypeClasses, TemplateHaskell, KindSignatures, DataKinds, ScopedTypeVariables, GADTs, TypeFamilies, FlexibleInstances, TypeOperators, UndecidableInstances, InstanceSigs #-}
module Functions where
import Data.Singletons
import Data.Singletons.TH
import Data.Singletons.Prelude
import Data.Promotion.Prelude
singletons [d|
data Nat = Z | S Nat
deriving Eq
instance Ord Nat where
(<=) Z _ = True
(<=) (S _) Z = False
(<=) (S n) (S m) = n <= m
|]
我一个接一个地遇到错误。最新的是：
src/Functions.hs:10:1:
Couldn't match kind ‘Nat’ with ‘*’
When matching types
n0 :: Nat
t1 :: *
Expected type: Sing t1
Actual type: Sing n0
Relevant bindings include
n_a9na :: Sing n0 (bound at src/Functions.hs:10:1)
lambda :: Sing n0 -> Sing m0 -> Sing (Apply (Apply (:<=$) t00) t10)
(bound at src/Functions.hs:10:1)
In the second argument of ‘applySing’, namely ‘n_a9na’
In the first argument of ‘applySing’, namely
‘applySing (singFun2 (Proxy :: Proxy (:<=$)) (%:<=)) n_a9na’
src/Functions.hs:10:1:
Could not deduce (SOrd 'KProxy) arising from a use of ‘%:<=’
from the context (t00 ~ 'S n)
bound by a pattern with constructor
SS :: forall (z_a9mg :: Nat) (n_a9mh :: Nat).
(z_a9mg ~ 'S n_a9mh) =>
Sing n_a9mh -> Sing z_a9mg,
in an equation for ‘%:<=’
at src/Functions.hs:(10,1)-(18,15)
or from (t10 ~ 'S n1)
bound by a pattern with constructor
SS :: forall (z_a9mg :: Nat) (n_a9mh :: Nat).
(z_a9mg ~ 'S n_a9mh) =>
Sing n_a9mh -> Sing z_a9mg,
in an equation for ‘%:<=’
at src/Functions.hs:(10,1)-(18,15)
or from (t00 ~ Apply SSym0 n0, t10 ~ Apply SSym0 m0)
bound by the type signature for
lambda_a9n9 :: (t00 ~ Apply SSym0 n0, t10 ~ Apply SSym0 m0) =>
Sing n0 -> Sing m0 -> Sing (Apply (Apply (:<=$) t00) t10)
at src/Functions.hs:(10,1)-(18,15)
In the second argument of ‘singFun2’, namely ‘(%:<=)’
In the first argument of ‘applySing’, namely
‘singFun2 (Proxy :: Proxy (:<=$)) (%:<=)’
In the first argument of ‘applySing’, namely
‘applySing (singFun2 (Proxy :: Proxy (:<=$)) (%:<=)) n_a9na’
有谁知道正确的做法是什么？
我不确定为什么会失败。我同样对实施 compare 时遇到的类似失败感到困惑，而对尝试（看似简单）
singletons [d| data Nat = Z | S Nat deriving (Eq,Ord) |]
我的猜测是 Ord 中的某些内容已关闭...但是，这有效。稍后我会试着看看 singleton 的胆量。
singletons [d|
data Nat = Z | S Nat
deriving (Eq)
instance Ord Nat where
compare = compare'
compare' :: Nat -> Nat -> Ordering
compare' Z Z = EQ
compare' (S _) Z = GT
compare' Z (S _) = LT
compare' (S n) (S m) = compare' n m
|]
顺便说一下，我这里使用的是 GHC 8.0。
编辑
在 singletons 中四处寻找之后，我找到了问题的真正根源（并且被多少类型级别的黑客攻击所震撼）。使用 GHC 中的 -ddump-splices 我能够生成实际的 Haskell 代码（对于您问题中的初始代码）。有问题的部分是
instance PEq (Proxy :: Proxy Nat_a7Vb) where
type (:==) (a_a8Rs :: Nat_a7Vb) (b_a8Rt :: Nat_a7Vb) = Equals_1627424016_a8Rr a_a8Rs b_a8Rt
和
instance POrd (Proxy :: Proxy Nat_a7Vb) where
type (:<=) (a_aa9e :: Nat_a7Vb) (a_aa9f :: Nat_a7Vb) = Apply (Apply TFHelper_1627428966Sym0 a_aa9e) a_aa9f
编译生成的代码，我收到了关于这两个的稍微更有用的错误消息
Expecting one more argument to ‘Proxy’
Expected kind ‘Proxy Nat_a7Vb’, but ‘Proxy’ has kind ‘k0 -> *’
属于PEq和POrd中的(Proxy :: Proxy Nat_a7Vb)类。没有 -XPolyKinds 就无法编译。检查了 singletons 的回购协议，实际上它告诉您需要启用 -XTypeInType，这又会启用 -XPolyKinds.
所以，没有错误，你只需要添加 PolyKinds 或 TypeInType （我推荐后者，因为这是软件包推荐的......）到你的 LANGUAGE 使一切正常工作的编译指示。
使用提升的布尔关系
有更好的方法。 “n 是 less-than-or-equal 到 m”是一个 命题 可以 证明 和 information-rich 证据。证明一个数字小于另一个数字的一种方法是给出它们的差异（单例表示）：
data LE n m where
LE :: Natty z -> LE n (n :+ z)
我们可以想出一个程序来测试给定的数字是否小于另一个。 le 尝试从 m 中减去 n，并且失败并且 returns Nothing 或产生它们的差异，作为 Natty，以及证明减法是正确的，打包在 LE 构造函数中。
le :: Natty n -> Natty m -> Maybe (LE n m)
le Zy m = Just (LE m)
le (Sy n) (Sy m) = fmap (\(LE z) -> LE z) (le n m)
le _ _ = Nothing
这个想法可以推广给我们"strongly-typed compare"。比较两个数字时，您会发现它们相等，或者一个小于另一个。 （Either (LE n m) (LE m n) 也能完成这项工作，但这个版本稍微更精确一些。）
data Compare n m where
LT :: Natty z -> Compare n (n :+ S z)
EQ :: Compare n n
GT :: Natty z -> Compare (m :+ S z) m
compare :: Natty n -> Natty m -> Compare n m
compare Zy Zy = EQ
compare Zy (Sy m) = LT m
compare (Sy n) Zy = GT n
compare (Sy n) (Sy m) = case compare n m of
LT z -> LT z
EQ -> EQ
GT z -> GT z
（我从 Hasochism 中提取了这个。）
请注意，与 le 不同，compare 是总数。它会总是 给你一个结果：每个数字要么小于、等于或大于其他数字。我们的目标是编写一个程序来测试两个数字中哪个更小，但我们也发现自己要证明数字是 totally ordered，并编写一个 type-safe 减法例程，所有这些都在同一个函数中。
另一种查看 compare 的方法是 查看 自然数对。当你比较两个数字时，你会知道哪个数字少了多少，从而完善了你对数字本身的了解。 Agda 的 dot-patterns 很好地支持了这种细化的概念：
compare : (n m : Nat) -> Compare n m
compare zero zero = eq
compare zero (suc m) = lt m
compare (suc n) zero = gt n
compare (suc n) (suc m) with compare n m
-- see how matching on `lt` refines `m` to `n + suc z`
compare (suc n) (suc .(n + suc z)) | lt z = lt z
compare (suc m) (suc .m) | eq = eq
-- likewise matching on `gt` refines `n` to `m + suc z`
compare (suc .(m + suc z)) (suc m) | gt z = gt z
无论如何，我不能直接说出你的 singletons 错误的来源，但是 Ord 很难处理单例值的一个原因是它假设你正在比较相同类型的值：
class Ord a where
compare :: a -> a -> Ordering
当您比较两个单例时，它们通常不会具有相同的类型！这就是单身人士的全部要点：他们的类型直接反映了他们的价值。如果您有两个 Natty n 值（它们的 n 匹配），则比较它们没有多大意义，因为您已经知道它们是相等的；如果它们不相等，则无法比较它们！
在 simply-typed 世界中设计的 类 和 Ord 一样，在 dependently-typed 程序中不一定那么有用，这是非常合理的。如果您使用依赖类型，正确的做法是不要滥用旧工具。迎接这个安全的新世界，information-rich张开双臂编程！