преобразование из буквального натурального
периментирую с зависимыми типами в Haskell и обнаружил следующее вбумага пакета «синглтоны»:
replicate2 :: forall n a. SingI n => a -> Vec a n
replicate2 a = case (sing :: Sing n) of
SZero -> VNil
SSucc _ -> VCons a (replicate2 a)
Поэтому я попытался реализовать это сам, просто чтобы почувствовать, как это работает:
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
import Data.Singletons
import Data.Singletons.Prelude
import Data.Singletons.TypeLits
data V :: Nat -> * -> * where
Nil :: V 0 a
(:>) :: a -> V n a -> V (n :+ 1) a
infixr 5 :>
replicateV :: SingI n => a -> V n a
replicateV = replicateV' sing
where replicateV' :: Sing n -> a -> V n a
replicateV' sn a = case sn of
SNat -> undefined -- what can I do with this?
Теперь проблема в том, чтоSing
экземпляр дляNat
не имеетSZero
или жеSSucc
, Существует только один конструктор с именемSNat
.
> :info Sing
data instance Sing n where
SNat :: KnownNat n => Sing n
Это отличается от других синглетонов, которые позволяют сопоставление, таких какSTrue
а такжеSFalse
, например, в следующем (бесполезном) примере:
data Foo :: Bool -> * -> * where
T :: a -> Foo True a
F :: a -> Foo False a
foo :: forall a b. SingI b => a -> Foo b a
foo a = case (sing :: Sing b) of
STrue -> T a
SFalse -> F a
Вы можете использоватьfromSing
чтобы получить базовый тип, но это, конечно, позволяет GHC проверять тип выходного вектора:
-- does not typecheck
replicateV2 :: SingI n => a -> V n a
replicateV2 = replicateV' sing
where replicateV' :: Sing n -> a -> V n a
replicateV' sn a = case fromSing sn of
0 -> Nil
n -> a :> replicateV2 a
Итак, мой вопрос: как реализоватьreplicateV
?
РЕДАКТИРОВАТЬ
Ответ, данный Эриско, объясняет, почему мой подход к деконструкцииSNat
не работает. Но даже сtype-natural
библиотека, я не могу реализоватьreplicateV
дляV
тип данныхиспользуя встроенный в GHCNat
типы.
Например, следующий код компилируется:
replicateV :: SingI n => a -> V n a
replicateV = replicateV' sing
where replicateV' :: Sing n -> a -> V n a
replicateV' sn a = case TN.sToPeano sn of
TN.SZ -> undefined
(TN.SS sn') -> undefined
Но это, кажется, не дает достаточно информации компилятору, чтобы сделать выводn
является0
или нет. Например, следующее выдает ошибку компилятора:
replicateV :: SingI n => a -> V n a
replicateV = replicateV' sing
where replicateV' :: Sing n -> a -> V n a
replicateV' sn a = case TN.sToPeano sn of
TN.SZ -> Nil
(TN.SS sn') -> undefined
Это дает следующую ошибку:
src/Vec.hs:25:28: error:
• Could not deduce: n1 ~ 0
from the context: TN.ToPeano n1 ~ 'TN.Z
bound by a pattern with constructor:
TN.SZ :: forall (z0 :: TN.Nat). z0 ~ 'TN.Z => Sing z0,
in a case alternative
at src/Vec.hs:25:13-17
‘n1’ is a rigid type variable bound by
the type signature for:
replicateV' :: forall (n1 :: Nat) a1. Sing n1 -> a1 -> V n1 a1
at src/Vec.hs:23:24
Expected type: V n1 a1
Actual type: V 0 a1
• In the expression: Nil
In a case alternative: TN.SZ -> Nil
In the expression:
case TN.sToPeano sn of {
TN.SZ -> Nil
(TN.SS sn') -> undefined }
• Relevant bindings include
sn :: Sing n1 (bound at src/Vec.hs:24:21)
replicateV' :: Sing n1 -> a1 -> V n1 a1 (bound at src/Vec.hs:24:9)
Итак, моя первоначальная проблема все еще остается, я все еще не могу сделать что-нибудь полезное сSNat
.