Добавить для нумерованных списков типов с помощью TypeLits

Используя GHC.TypeLits, мы можем написать простой нумерованный список типа (или вектор).

> {-# LANGUAGE TypeOperators, KindSignatures, GADTs, DataKinds, ScopedTypeVariables #-}

> import GHC.TypeLits

> data Vec :: * -> Nat -> * where
>   VNil :: Vec e 0
>   (:-) :: e -> Vec e n -> Vec e (n+1)

Это каноническое векторное определение с TypeLits. Операция append, интуитивно, должна выглядеть следующим образом:

> vecAppend :: Vec e n -> Vec e m -> Vec e (n + m)
> vecAppend VNil vec = vec
> vecAppend (a :- as) vec = a :- vecAppend as vec

Но решатель GHC имеет проблемы с арифметикой:

Could not deduce (((n1 + m) + 1) ~ (n + m))
from the context (n ~ (n1 + 1))

Конечно, поскольку n1 + 1 ~ n, (n1 + m) + 1 ~ n1 + 1 + m ~ n + m, но решатель, похоже, не знает о коммутативности и ассоциативности + (функция типа вообще не коммутативна или ассоциативна!)

Я знаю, что это возможно, если я определяю тип Peano naturals типа уровня, но я хотел знать, есть ли способ сделать это с текущей реализацией типа в GHC (7.8.0 здесь.)

Поэтому я попытался помочь:

> vecAppend :: Vec e (n+1) -> Vec e m -> Vec e ((n + 1) + m)
> vecAppend VNil vec = vec
> vecAppend (a :- as) vec = a :- vecAppend as vec

Но это просто отвлекает проблему от правильного экземпляра переменных типа.

Could not deduce (((n1 + 1) + m) ~ ((n + m) + 1))
from the context ((n + 1) ~ (n1 + 1))
  bound by a pattern with constructor
             :- :: forall e (n :: Nat). e -> Vec e n -> Vec e (n + 1),
       in an equation for ‘vecAppend’
NB: ‘+’ is a type function, and may not be injective
Expected type: Vec l ((n + 1) + m)
  Actual type: Vec l ((n + m) + 1)
Relevant bindings include
  l :: Vec l m
  as :: Vec l n1
  vecAppend :: Vec l (n + 1) -> Vec l m -> Vec l ((n + 1) + m)

И еще два таких, как этот.

Итак, дайте им возможность.

> vecAppend ∷ ∀ e n m. Vec e (n+1) → Vec e m → Vec e (n + 1 + m)
> vecAppend VNil l = l
> vecAppend ((a :- (as ∷ Vec e n)) ∷ Vec e (n+1)) (l ∷ Vec e m) = a :- (vecAppend as l ∷ Vec e (n+m))

Увы,

Could not deduce (n1 ~ n)
from the context ((n + 1) ~ (n1 + 1))
  bound by a pattern with constructor
             :- :: forall e (n :: Nat). e -> Vec e n -> Vec e (n + 1),
           in an equation for ‘vecAppend’
  ‘n1’ is a rigid type variable bound by
       a pattern with constructor
         :- :: forall e (n :: Nat). e -> Vec e n -> Vec e (n + 1),
       in an equation for ‘vecAppend’
  ‘n’ is a rigid type variable bound by
      the type signature for
        vecAppend :: Vec e (n + 1) -> Vec e m -> Vec e ((n + 1) + m)
Expected type: Vec e n1
  Actual type: Vec e n
Relevant bindings include
  vecAppend :: Vec e (n + 1) -> Vec e m -> Vec e ((n + 1) + m)
In the pattern: as :: Vec e n
In the pattern: a :- (as :: Vec e n)
In the pattern: (a :- (as :: Vec e n)) :: Vec e (n + 1)

Есть ли способ сделать это с помощью текущего решателя и не прибегать к определению ваших собственных пиано-натов? Я предпочитаю внешний вид 3 до Succ (Succ (Succ Zero))) в моих сигнатурах типа.

РЕДАКТИРОВАТЬ. Поскольку кажется, что в настоящее время нет способа сделать это (до GHC 7.10), я перефразирую свой вопрос: может кто-нибудь показать мне, почему нет пути? Я, к сожалению, еще не посмотрел на решателей SMT, поэтому я не знаю, что в принципе возможно или нет.

Идея заключается в том, что я не очень разбираюсь в вычислениях на уровне уровня, и хочу научиться распознавать ситуации, когда я могу перефразировать мою проблему, чтобы она работала, и ситуации, когда я не могу (это настоящее (на данный момент) экземпляр последнего.)

Ответ 1

Конечно, есть способ. Это нехорошо, но есть способ. Вся цель размещения unsafeCoerce в языке - это тот случай, когда вы знаете, что что-то правильно набрано, но GHC не может понять это сам. Итак.. Там путь.

История должна значительно улучшиться в GHC 7.10. Текущие планы включают в себя решение SMT для работы с значениями Nat уровня типа.

Edit:

О. Что касается того, почему это легко с Peano naturals и сложно с литералами на уровне шрифта: с помощью Peano naturals, добавив один, применяется конструктор типа. GHC знает, что применение конструктора типа является инъективной операцией. Фактически, это один из ключевых моментов, лежащих в основе системы типа GHC. Поэтому, когда вы работаете с Peano naturals, вы работаете исключительно с конструкциями, которые GHC уже хорошо подходит для обработки.

В отличие от этого, GHC не знает проклятую вещь об арифметике. Он не знает, что (+1) является инъективной функцией на Nat. Поэтому он не знает, что он может получить m ~ n из (m + 1) ~ (n + 1). Он также не имеет представления об основных свойствах арифметики на Nat, как ассоциативные, дистрибутивные и коммутативные свойства. Идея интеграции решения SMT заключается в том, что решатели SMT неплохо работают с такими свойствами.

С GHC 7.8 вы можете, безболезненно, перевести литералы на уровне типа в Pano naturals, хотя:

{-# LANGUAGE DataKinds, TypeFamilies, TypeOperators, UndecidableInstances #-}

import GHC.TypeLits

data Z
data S a

type family P (n :: Nat) where
    P 0 = Z
    P n = S (P (n - 1))

Это использует новую функцию семейства закрытых типов, чтобы сделать функцию типа P для преобразования из литерала в представление Peano, как такового:

*Main> :t undefined :: P 5
undefined :: P 5 :: S (S (S (S (S Z))))