Описание тега dependent-type

Зависимые типы - это типы, которые зависят от значений. Очень немногие языки поддерживают их - примеры включают Agda, ATS, Coq, Epigram, Scala (по типам, зависящим от пути, близкий вариант) и Idris, который стремится создавать качественный собственный код системного уровня.
1 ответ

Идрис: арифметика для ограниченного двойника

Я новичок в Идрисе. Мне нужно создать данные, описывающие ограниченное число. Итак, я сделал такие данные с помощью такого конструктора: data BoundedDouble : (a, b : Double) -> Type where MkBoundedDouble : (x : Double) -> {auto p : a <= x &…
31 май '16 в 22:09
2 ответа

Динамическое построение значений с помощью GADT с использованием типов данных

Почему сложнее построить значения с помощью типов данных, а сопоставить их с шаблонами сравнительно легко? {-# LANGUAGE KindSignatures , GADTs , DataKinds , Rank2Types #-} data Nat = Zero | Succ Nat data Direction = Center | Up | Down | UpDown deriv…
04 май '14 в 00:39
1 ответ

Агда: Вектор Членство в Stdlib? (А как научить стдлиб вообще)

Я имею дело со строками в Агде, и у меня есть их вектор. Мне нужно проверить, встречается ли данная строка в векторе (как часть проверки, является ли переменная свободной или связанной в выражении, в теории PL, которую я делаю wprk). Я все еще пытаю…
1 ответ

Получение обычного списка из списка типов

Я нашел способ конвертировать Nat в Integer с помощью Proxy а также natVal как вы можете видеть в коде ниже: {-# LANGUAGE DataKinds #-} {-# LANGUAGE ScopedTypeVariables #-} module Main where import Data.Proxy (Proxy) import Data.Monoid ((<>)) …
15 окт '17 в 02:29
1 ответ

Ограничивающие типы в конструкторе GADT

У меня простой ADT data Concept a = Entity a | Role a | Relation a | Resource a | Sub (Concept a) Теперь я хочу создать GADT, используя этот ADT, который будет ограничивать сигнатуру типа его конструкторов. Этот код не будет работать, но я хочу сдел…
2 ответа

Почему нельзя сделать вывод, что 0+n=n в этой зависимо типизированной программе?

Я начинаю использовать Coq, и я хотел бы определить некоторые типизированные программы. Учтите следующее: Inductive natlist : nat -> Type := | natnil : natlist 0 | natcons : forall k, nat -> natlist k -> natlist (S k). Fixpoint natappend (n…
14 мар '16 в 13:40
2 ответа

Как определить частично упорядоченные множества в Lean?

Я хочу доказать эту теорему в доказательстве теоремы Лин. Во-первых, мне нужно определить такие вещи, как частично упорядоченные множества, чтобы я мог определить infimum / supremum. Как это делается в Lean? В учебнике упоминаются сетоиды, которые я…
27 мар '16 в 18:48
1 ответ

Обновление "Бумаги синглетонов". Как я могу реализовать тип данных AChar с помощью библиотеки синглтонов

Благодаря Benjamin Hodgson я начал реализовывать безопасный для типов SQL-интерфейс, начатый в этом вопросе о стековом потоке. Как мне посоветовали, я начал читать синглтон. Я считаю, что видеть работающий код очень помогает, и пытался увидеть, как …
21 ноя '16 в 20:16
1 ответ

Застрял на простом доказательстве равенства

Я пытаюсь реализовать некоторые матричные операции и доказательства вокруг них в Агде. Код включает в себя что-то около следующих определений: open import Algebra open import Data.Nat hiding (_+_ ; _*_) open import Data.Vec open import Relation.Bina…
03 сен '16 в 00:34
2 ответа

Как определить оператора деления в Агде?

Я хочу разделить два натуральных числа. Я сделал функцию, как это _/_ : N -> N -> frac m / one = m / one (suc m) / n = ?? I dont know what to write here. Пожалуйста помоги.
18 фев '15 в 10:54
1 ответ

Размер индексируемых изменяемых массивов в Haskell

В Haskell можно писать функции по индексируемому списку размеров, которые гарантируют, что мы никогда не выйдем за пределы. Возможная реализация: data Nat = Zero | Succ Nat deriving (Eq, Ord, Show) infixr 5 :- data Vec (n :: Nat) a where Nil :: Vec …
10 янв '16 в 21:29
1 ответ

Доказательство (не совсем) неактуальность, когда при разрушении равенства

У меня есть зависимый тип, который моделирует конечный путь в переходной системе. Система перехода имеет функцию R что дает утверждение о том, есть ли грань между государствами s а также s' с этикеткой a, Тип конечного пути: Inductive FinPathTail (s…
05 фев '19 в 22:44
1 ответ

Доказательство конкатенации языка ассоциативно в Агде

Я новичок в языке Agda, и я работаю над формальными языками, используя Agda. У меня есть некоторые проблемы, когда доказательство объединения языков является ассоциативным. Доказательство будет выделено желтым цветом, так как Agda не смогла найти сл…
1 ответ

Отражение неоднородных продвигаемых типов обратно в значения композиционно

Я играл с -XDataKinds в последнее время, и хотел бы взять продвинутую структуру структуры с семействами типов и вернуть ее обратно к уровню ценности. Я считаю, что это возможно, потому что композиционные компоненты очень просты, а терминальные выраж…
2 ответа

Подпись типа "половина" в Idris

Я довольно новичок в Идрисе и пытаюсь уловить основные понятия и синтаксис. Даже если это может показаться бессмысленным, я пытаюсь определить half функция, которая наполовину естественная. Я хочу придумать что-то вроде: half : (n : Nat) -> (k : …
30 ноя '16 в 22:30
1 ответ

Сопоставление с двумя значениями индуктивного типа по одному и тому же индексу

Почему следующее не проверяет тип (coq-8.5pl3)? Сопоставление с образцом, кажется, забывает, что u а также v имеют тот же тип. Inductive X : Type -> Type := | XId : forall a, X a -> X a | XUnit : X unit. Fixpoint f {a : Type} (x : X a) (y : X …
12 июн '17 в 21:20
4 ответа

Что такое зависимая типизация?

Может кто-нибудь объяснить мне зависимую типизацию? У меня мало опыта работы с Haskell, Cayenne, Epigram или другими функциональными языками, поэтому чем проще использовать термины, тем больше я буду признателен за это!
18 фев '12 в 04:58
1 ответ

Представление индуктивных типов

Я реализовал лямбда-исчисление с зависимой типизацией в духе этой статьи: http://www.andres-loeh.de/LambdaPi/LambdaPi.pdf Исчисление, работает, и я экспериментировал с ним и расширил несколько вещей: много вселенных, жестко закодированная индукция а…
12 мар '14 в 02:28
4 ответа

Почему бы не быть зависимым типом?

Я видел несколько источников, повторяющих мнение, что "Haskell постепенно становится типизированным языком". Предполагается, что с появлением все большего количества языковых расширений Haskell движется в этом общем направлении, но пока не существуе…
18 окт '12 в 18:48
1 ответ

Распределенность субстрата

Предположим, у меня есть транзитивное отношение ~с двумя эндомапами f а также g, Если предположить, f а также g согласен везде и f a ~ f b ~ f cтогда есть два способа показать g a ~ g c: преобразовать каждый f в g с помощью данного равенства затем п…
18 янв '16 в 01:34