Доказательство m + (1 + n) == 1+ (m + n) в зависимом хаскеле

Question

Доказательство m + (1 + n) == 1+ (m + n) в зависимом хаскеле

Да, это возможно через AspectJ . Я объясню это с помощью некоторого фрагмента кода:

public Aspect
{
    Object around()call(* Foo.callTheMethod())
    {
        // do your work
        return proceed(); 
    }                       
}

6

dependent-type haskell

задан bergey 17 January 2019 в 15:25

1 ответ

Другие вопросы по тегам:

dependent-type haskell

Похожие вопросы:

score 0 · Answer 1

Ваше определение сложения не является общепринятым.

type family Add (m :: Nat) (n :: Nat) :: Nat where
  Add Zero n = n
  Add (Succ m) n = Add m (Succ n)

Это «хвостовая рекурсивная» добавка. Кажется, кажется, что должен быть способ доказать свои свойства, используя эту форму добавления, но я не могу понять это. До тех пор, с хвостовой рекурсией на уровне типа / свойства обычно работать гораздо сложнее, чем со стандартным видом:

type family Add (m :: Nat) (n :: Nat) :: Nat where
  Add Zero n = n
  Add (Succ m) n = Succ (Add m n)

Это последнее определение сложения делает ваш sum' проход без каких-либо убедительных все.

РЕДАКТИРОВАТЬ на самом деле это было легко, когда я увидел это правильно. Вот что я получил (импортировав Data.Type.Equality и включив LANGUAGE TypeOperators):

propSucc2 :: SNat m -> SNat n -> Add m (Succ n) :~: Succ (Add m n)
propSucc2 Zy _ = Refl
propSucc2 (Suc m) n = propSucc2 m (Suc n)

Хвосто-рекурсивное определение, хвост-рекурсивное доказательство. Затем, чтобы использовать его, вы используете gcastWith:

sum' (B m) (B n) = ...
        (Suc x, y) -> gcastWith (propSucc2 x y) 
                                (let B z = sum' (B x) (B y) in Suc z)

gcastWith просто берет равенство :~: и делает его доступным для средства проверки типов в рамках своего второго аргумента.

Кстати, если вы определили sum' в структуре, параллельной вашему семейству типов Add, то вам не нужны никакие леммы. Заставить вещи следовать параллельным структурам - хорошая техника, чтобы упростить задачу (это часть искусства зависимого программирования, поскольку не всегда очевидно, как):

sum' :: Bounded' (SNat m) -> Bounded' (SNat n) -> Bounded' (SNat (Add m n))
sum' (B Zy) (B n) = B n
sum' (B (Suc m)) (B n) = sum' (B m) (B (Suc n))