Идрис векторов против связанных списков

Идрис делает какую-то оптимизацию под капотом векторов? Потому что, по внешнему виду, вектор Idris - это только связанный список с известным размером (известный во время компиляции). На самом деле, в общем, похоже, вы могли бы выразить следующую эквивалентность (я немного догадываюсь о синтаксисе):

Vector : Nat -> Type -> Type
Vector n t = (l: List t ** length l = n)

Таким образом, хотя это хорошо в смысле предотвращения ошибок диапазона, реальное преимущество векторов (в традиционном использовании термина) заключается в производительности; в частности, O (1) случайного доступа. Кажется, что вектор idris не поддержал бы это (как бы вы могли написать функцию индексирования для этой производительности?).

  • Предполагая, что под капотом (как это происходит с Nat) не происходит волшебство, чтобы перенастроить Vector s, существует ли тип данных с произвольным доступом в Idris?
  • Каким будет/есть такая вещь, определенная в системе алгебраического типа? Конечно, похоже, было бы невозможно определить его индуктивно.
  • Возможно ли в системе типа, подобной системе Idris, создать тип данных, который поддерживает O (1) случайный доступ, и знает о его длине, чтобы весь доступ был доказано действительным? (Haskell имеет векторы типа массива, но их конкретная реализация непрозрачна для среднего пользователя, включая меня).

Ответы

Ответ 1

Он не делает ничего, чтобы оптимизировать поиск в векторе (на момент написания этого ответа, по крайней мере).

Это не из-за каких-либо трудностей с этим, на самом деле, но более того, потому что я предпочел бы иметь какую-то общую структуру для написания такого рода оптимизации, кроме жесткого кодирования. По общему признанию, у нас уже есть жестко закодированная оптимизация для Nat, но я все же предпочел бы не добавлять нагрузки больше в ad-hoc.

В зависимости от того, на что вы на самом деле этого хотите, может быть, что экспериментальная система типа уникальности поможет, поскольку вы можете иметь низкоуровневую изменяемую вещь под капотом и по-прежнему иметь безопасный и эффективный доступ и обновление в чистом стиле на языке высокого уровня. Посмотрим...

Ответ 2

У Эдвина есть окончательные ответы на то, что в настоящее время делает Идрис. Однако если вы ищете что-то, что может быть естественным для оптимизации в постоянном поиске в некоторых случаях, следующий шаг может быть шагом в правильном направлении.

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

Fixpoint vector (n : nat) (A : Type) :=
  match n return Type with
    | 0 => unit
    | S n' => (A * vector n' A)%type
  end.
Definition nil {A} : vector 0 A := tt.
Definition cons {n} {A : Prop} (x : A) (xs : vector n A) : vector (S n) A
  := (x, xs).
Fixpoint get {n} {A : Prop} (m : nat) (default : A) (v : vector n A) {struct n} : A
  := match n as n return vector n A -> A with
       | 0 => fun _ => default
       | S n' => match m with
                   | 0 => fun v => fst v
                   | S m' => fun v => @get n' A m' default (snd v)
                 end
     end v.

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