Не смог вывести SingI предшественника Nat

Question

Я пытаюсь написать weaken функция для конечных множеств целых чисел. Я использую singletons пакет. Я определил и продвинул функции сложения, вычитания и предшественника, а также доказал некоторые уравнения для них, чтобы помочь при проверке типов. Но ошибка, которую я получаю, совершенно не связана со всем этим.

weaken :: forall n m k . (SingI n, SingI m, SingI k, (Minus m n) ~ NatJust k) => Fin n -> Fin m
weaken ZF =  gcastWith (apply Refl $ plus_minus sm sn sk) ZF
  where sn = sing :: SNat n
        sm = sing :: SNat m
        sk = sing :: SNat k
weaken (SF n) = gcastWith (apply Refl $ succ_pred sm) (SF (weaken n))
  where sn = sing :: SNat n
        sm = sing :: SNat m
        sk = sing :: SNat k

Я получаю ошибку при рекурсивном вызове weaken (SF (weaken n)) и является следующим: Could not deduce (SingI n1), где n1 правильно предположить, чтобы быть предшественником уровня типа n, Я мог бы добавить SingI (Pred n) ограничение, но это просто перемещает проблему на один уровень вниз (GHC теперь говорит, что не может вывести эквивалент (SingI (Pred (Pred n)))).

Как я могу убедить GHC, что SingI (Pred n) следует из SingI n (и почему не singletons пакет уже этим занимается)?

Answer 1

GHC.TypeLitsчто в конечном итоге дает нам тип уровня неотрицательныйInteger-s не экспортирует функции, которые позволили бы нам выполнять одноэлементные операции времени выполнения. Например, учитываяKnownNat aа также KnownNat b, нет стандартной функции для производства KnownNat (a + b) во время выполнения.

singletonsрешает это путем реализации синглтона Nat операции небезопасны.

singletons Функция вычитания выдает ошибку для отрицательных результатов (и не усекает до 0, как хотелось бы), поэтому мы не можем использовать это для pred и должны реализовать это сами

{-# language TypeApplications #-} -- plus all the usual exts

import Data.Singletons.Prelude
import Data.Singletons.TypeLits
import Unsafe.Coerce

type family Pred (n :: Nat) :: Nat where
  Pred 0 = 0
  Pred n = n :- 1

sPred :: Sing n -> Sing (Pred n)
sPred sn = case fromSing sn of
  0 -> unsafeCoerce (sing @_ @0)
  n -> case toSing @Nat (n - 1) of
    SomeSing sn -> unsafeCoerce sn

Ты можешь использовать sPred получить Sing (Pred n), затем withSingI или же singInstance превратить это в SingI (Pred n),

Тем не менее, вы, вероятно, не должны использовать SingI в weaken, Цель SingI заключается в автоматическом подключении одноэлементных параметров в контекстах, где вы их не используете ни для чего, кроме пересылки их другим функциям. Вместо этого просто используйте Singи вы можете избежать sing и введите шум аннотации. По моему опыту Sing предпочтительнее SingI примерно в 90% времени для singletons программирование.