Какая предпочтительная альтернатива Фин из Идриса в Хаскелле

Ответ 1

Вы можете напрямую перевести Idris Fin в обычный Hashell-мишмар с характерными для него функциями.

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 вы можете даже иметь singleton Fin s!

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 и используйте тип phantom для его размер. Но бремя ответственности на вас, библиотекатор, чтобы убедиться, что 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))

О, и вы не можете выполнить вычисление уровня уровня (как это было сделано с Fin2Nat выше) с этим представлением Fin, потому что тип уровня Int не допускает индукции.

Для чего это стоит, Idris Fin столь же неэффективен, как и GADT выше. Документы содержат следующее предостережение:

Вероятно, не стоит использовать Fin для арифметики, и они будут чрезвычайно неэффективны во время выполнения.

Я слышал звуки о будущей версии Idris, которая могла бы определить "Nat с типами" -типы типов данных (например, Fin) и автоматически стирать доказательства и упаковывать значения в числовые числа машин, но как я знаю, мы еще не там.

Ответ 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 ( n)
  VS :: !(Fin n) -> FinView ( n)
deriving instance Show (FinView n)

Важно отметить, что мы могли бы определить FinView с использованием явных ограничений равенства, потому что нам нужно будет думать в этих терминах, чтобы дать правильные сигнатуры шаблонов:

data FinView n where
  VZ :: n ~  m => FinView n
  VS :: n ~  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 ~  m => Fin n
pattern FZ <- (viewFin -> VZ) where
  FZ = Fin 0

pattern FS :: () => n ~  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 #-}

Для полноты (потому что мне потребовалось больше усилий, чтобы написать это, чем я ожидал), здесь один из способов написать unsafeCoerce, если этот модуль случайно экспортирует конструктор данных Fin. Я полагаю, что есть, вероятно, более простые способы.

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 :~:  m -> a -> b
    blah pf2 a = getB pf2 (Yah a)

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

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

finZBad - это то, где происходит все действие, но он ничего не делает удаленно неправильно. Если кто-то действительно дает нам не-нижнее значение типа Fin 'Z, то что-то уже пошло ужасно неправильно. Явные доказательства равенства типов здесь необходимы, потому что если GHC увидит код, требующий 'Z ~ m, он просто отвергнет его из-под контроля; GHC действительно не любит гипотетические рассуждения в ограничениях. Аннотации NOINLINE необходимы, поскольку сам GHC-модуль упрощения использует информацию о типе; обработка доказательств того, что он знает очень хорошо, невозможно сбивает с толку, с чрезвычайно произвольными результатами. Поэтому мы блокируем его и успешно реализуем функцию "Зло".