Haskell 中 Idris 的 Fin 的首选替代品是什么

Question

我想要一个可以包含值 0 到 n 的类型，其中 n 位于类型级别。

我正在尝试类似的东西：

import GHC.TypeLits
import Data.Proxy

newtype FiniteNat n = FiniteNat { toInteger :: Integer }

smartConstructFiniteNat :: (KnownNat n) => Proxy n -> Integer -> Maybe (FiniteNat (Proxy n))
smartConstructFiniteNat pn i 
  | 0 <= i && i < n = Just (FiniteNat i)
  | otherwise       = Nothing
  where n = natVal pn

这基本上是有效的，但不知何故并不令人满意。是否有 "standard" 解决方案，甚至是实现此目的的库？关于依赖类型的列表长度有很多大惊小怪，但我无法找到确切的东西。另外 - 我假设使用 GHC.TypeLits 是必要的，因为我的 n 可以取相当大的值，所以归纳定义可能会很慢。

Answer 1

您可以直接将 Idris 的 Fin 翻译成通常的 Haskell 各种依赖类型特征的混杂。

data Fin n where
    FZ :: Fin (S n)
    FS :: Fin n -> Fin (S n)

(!) :: Vec n a -> Fin n -> a
(x :> xs) ! FZ = x
(x :> xs) ! (FS f) = xs ! f

有了 TypeInType 你甚至可以拥有单身 Fins!

data Finny n (f :: Fin n) where
    FZy :: Finny (S n) FZ
    FSy :: Finny n f -> Finny (S n) (FS f)

这允许您伪造依赖于运行时东西的量化，例如，

type family Fin2Nat n (f :: Fin n) where
    Fin2Nat (S _) FZ = Z
    Fin2Nat (S n) (FS f) = S (Fin2Nat n f)

-- tighten the upper bound on a given Fin as far as possible
tighten :: Finny n f -> Fin (S (Fin2Nat n f))
tighten FZy = FZ
tighten (FSy f) = FS (tighten f)

但是，呃，必须在值和类型级别复制所有内容有点糟糕，写出所有类型的变量 (n) 会变得非常乏味。

如果你真的确定你需要 Fin 的高效运行时表示，你基本上可以做你在问题中所做的事情：将机器 Int 填充到 newtype并根据其大小使用幻影类型。但是责任在你，图书馆的实施者，确保 Int 符合界限！

newtype Fin n = Fin Int

-- fake up the constructors
fz :: Fin (S n)
fz = Fin 0
fs :: Fin n -> Fin (S n)
fs (Fin n) = Fin (n+1)

此版本缺少真正的 GADT 构造函数，因此您无法使用模式匹配来操纵类型相等性。您必须使用 unsafeCoerce 自行完成。您可以以 fold 的形式为客户提供一个类型安全的接口，但他们必须愿意以高阶风格编写所有代码，并且（因为 fold 是一种变形）它一次看一层以上变得更难了。

-- the unsafeCoerce calls assert that m ~ S n
fold :: (forall n. r n -> r (S n)) -> (forall n. r (S n)) -> Fin m -> r m
fold k z (Fin 0) = unsafeCoerce z
fold k z (Fin n) = unsafeCoerce $ k $ fold k z (Fin (n-1))

哦，你不能用 Fin 的这种表示进行类型级计算（就像我们上面对 Fin2Nat 所做的那样），因为类型级 Ints 不允许感应。

就其价值而言，Idris 的 Fin 与上面的 GADT 一样效率低下。文档包含 the following caveat:

It's probably not a good idea to use Fin for arithmetic, and they will be exceedingly inefficient at run time.

我听说 Idris 的未来版本能够发现“Nat with types”风格的数据类型（如 Fin）并自动擦除证明并将值打包到机器整数，但据我所知我们还没有。

Answer 2

rampion 模式同义词，我同意了，但要弄清楚如何正确地构造他们的签名并不是一件容易的事。因此我想我会写一个正确的答案来给出完整的代码。

首先，通常的样板文件：

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE Trustworthy #-}

module FakeFin (Nat (..), Fin (FZ, FS), FinView (..), viewFin) where
import Numeric.Natural
import Unsafe.Coerce

现在基本类型：

data Nat = Z | S Nat

-- Fin *must* be exported abstractly (or placed in an Unsafe
-- module). Users can use its constructor to implement
-- unsafeCoerce!
newtype Fin (n :: Nat) = Fin Natural
deriving instance Show (Fin n)

通过视图类型工作比直接工作要容易得多，所以让我们定义一个：

data FinView n where
  VZ :: FinView ('S n)
  VS :: !(Fin n) -> FinView ('S n)
deriving instance Show (FinView n)

重要的是要注意我们可以使用显式等式约束来定义 FinView，因为我们必须用这些术语来思考才能给出正确的模式签名：

data FinView n where
  VZ :: n ~ 'S m => FinView n
  VS :: n ~ 'S m => !(Fin m) -> FinView n

现实际查看功能：

viewFin :: Fin n -> FinView n
viewFin (Fin 0) = unsafeCoerce VZ
viewFin (Fin n) = unsafeCoerce (VS (Fin (n - 1)))

模式签名精确反映了 FinView 构造函数的签名。

pattern FZ :: () => n ~ 'S m => Fin n
pattern FZ <- (viewFin -> VZ) where
  FZ = Fin 0

pattern FS :: () => n ~ 'S m => Fin m -> Fin n
pattern FS m <- (viewFin -> VS m) where
  FS (Fin m) = Fin (1 + m)

-- Let GHC know that users need only match on `FZ` and `FS`.
-- This pragma only works for GHC 8.2 (and presumably future
-- versions).
{-# COMPLETE FZ, FS #-}

为了完整起见（因为写这个比我预期的要花费更多的精力），如果这个模块不小心导出了 Fin 数据构造函数，这里有一种写 unsafeCoerce 的方法。我想可能有更简单的方法。

import Data.Type.Equality

type family YahF n a b where
  YahF 'Z a _ = a
  YahF _ _ b = b

newtype Yah n a b = Yah (YahF n a b)

{-# NOINLINE finZBad #-}
finZBad :: 'Z :~: n -> Fin n -> a -> b
finZBad pf q =
  case q of
    FZ -> blah (trans pf Refl)
    FS _ -> blah (trans pf Refl)
  where
    blah :: forall a b m. 'Z :~: 'S m -> a -> b
    blah pf2 a = getB pf2 (Yah a)

    {-# NOINLINE getB #-}
    getB :: n :~: 'S m -> Yah n a b -> b
    getB Refl (Yah b) = b

myUnsafeCoerce :: a -> b
myUnsafeCoerce = finZBad Refl (Fin 0)

finZBad 是所有操作发生的地方，但它不会做任何远程不当的事情！如果有人真的给了我们一个 Fin 'Z 类型的非底值，那么就已经出了大问题。这里的显式类型相等证据是必要的，因为如果 GHC 看到代码需要 'Z ~ 'S m，它会直接拒绝它； GHC 并不真正喜欢约束中的假设推理。 NOINLINE 注释是必要的，因为 GHC 的简化器本身使用类型信息；处理它非常了解的事情的证据是不可能的，这会使它非常困惑，并产生极其武断的结果。所以我们阻止它并成功实现了邪恶的功能。

Haskell 中 Idris 的 Fin 的首选替代品是什么

What is the preferred alternative to Fin from Idris in Haskell

haskell

dependent-type

idris