Ограничения типа для размерности векторов в F # и Haskell (зависимые типы)

Question

Я новичок в F # и Haskell и реализую проект, чтобы определить, на каком языке я бы предпочел уделять больше времени.

У меня есть множество ситуаций, когда я ожидаю, что заданный численный тип задает размеры на основе параметров, заданных функции верхнего уровня (т. Е. Во время выполнения). Например, в этом фрагменте кода F #, у меня есть

type DataStreamItem = LinearAlgebra.Vector<float32> 

type Ball = 
    {R : float32; 
    X : DataStreamItem} 

и я ожидаю, все экземпляры типа DataStreamItem иметь D размеры.

Мой вопрос в интересах разработки алгоритмов и отладки поскольку такие формы-mismatche жуков может быть головная боль придавить, но должно быть не проблема, когда алгоритм вверх и работает:

Есть ли способ в F # или Haskell, чтобы ограничить DataStreamItem и/или Ball иметь размеры D? Или мне нужно прибегать к сопоставлению шаблонов при каждом расчете?

Если это так, есть ли хорошие, легкие парадигмы, чтобы поймать такие нарушения ограничений, как только они появятся (и которые можно удалить, когда производительность критическая)?

Edit:

Чтобы уточнить, в каком смысле D ограничиваемый:

D определяется таким образом, что если вы выразили алгоритм функции main(DataStream) как вычисление графика, все промежуточные расчеты будет зависеть от размера D для исполнения main(DataStream). Простейший пример, который я могу думать будет дот-продукт M с DataStreamItem: размерность DataStream будет определять создание параметров размерности M

Другой Edit:

Через неделю, я считаю, следующий блог с изложением именно то, что я искал в зависимых типов в Haskell:

https://blog.jle.im/entry/practical-dependent-types-in-haskell-1.html

And A nother: В этом номере reddit содержится некоторое обсуждение зависимых типов в Haskell и содержится ссылка на довольно интересный номер dissertation proposal Р. Эйзенберга.

Answer 1

система

Ни в Haskell не F # типа достаточно богата, чтобы (непосредственно) выражают заявления своего рода «N вложенных экземпляров рекурсивного типа T, где N находится между 2 и 6» или "строку символов в точности 6 длинный ". Не в этих точных терминах, по крайней мере.

Я имею в виду, что вы всегда можете выразить такой тип длинной 6 длинной, как type String6 = String6 of char*char*char*char*char*char или какой-либо вариант такого рода (чего технически должно быть достаточно для вашего конкретного примера с векторами, если вы не сообщите нам все пример), но вы не можете сказать что-то вроде type String6 = s:string{s.Length=6} и, что более важно, вы не можете определить функции вида concat: String<n> -> String<m> -> String<n+m>, где n и m представляют длины строк.

Но вы не первый человек, задающий этот вопрос. Это направление исследований существует и называется «dependent types», и я могу выразить суть его в целом как «с более высокими операциями более высокого порядка по типам» (в отличие от простого соединения и пересечения, у нас есть языки ML) - обратите внимание, как в приведенном выше примере я параметризую тип String с номером, а не другим типом, а затем выполняю арифметику по этому номеру.

Прототипы наиболее известных языков (что я знаю) в этом направлении Agda, Idris, F* и Coq (на самом деле не в полной мере сделки AFAIK). Проверьте их, но будьте осторожны: это своего рода край завтрашнего дня, и я бы не советовал начинать большой проект на основе этих языков.

(редактирование: по-видимому, вы can do certain tricks in Haskell имитировать зависимые типы, но это не очень удобно, и вы должны включить UndecidableInstances)

В качестве альтернативы, вы могли бы пойти с более слабым раствором делает проверки во время выполнения. Общий смысл: оберните ваши типы векторов в простой оболочке, не позволяйте прямому его созданию, но вместо этого предоставляйте функции-конструкторы и создавайте эти функции-конструкторы для требуемого свойства (т. Е. Длины). Что-то вроде:

type Stream4 = private Stream4 of DataStreamItem 
    with 
     static member create (item: DataStreamItem) = 
     if item.Length = 4 then Some (Stream4 item) 
     else None 

     // Alternatively: 
     if item.Length <> 4 then failwith "Expected a 4-long vector." 
     item 

Вот более полное объяснение подхода Скотта Wlaschin: constrained strings.

Answer 2

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

В Haskell это уже давно можно сделать; один способ, который я считаю довольно опрятным, чтобы аннотировать массивы с помощью стандартного типа фиксированной длины желаемой длины:

newtype FixVect v s = FixVect { getFixVect :: VU.Vector s } 

Для обеспечения правильной длины, вы только обеспечивают (полиморфный) умные конструкторы что построить из фиксированной длины – совершенно безопасно, хотя фактического номера измерения нигде не упоминается!

class VectorSpace v => FiniteDimensional v where 
    asFixVect :: v -> FixVect v (Scalar v) 

instance FiniteDimensional Float where 
    asFixVect s = FixVect $ VU.singleton s 
instance (FiniteDimensional a, FiniteDimensional b, Scalar a ~ Scalar b)  => FiniteDimensional (a,b) where 
    asFixVect (a,b) = case (asFixVect a, asFixVect b) of 
     (FixVect av, FixVect bv) -> FixVect $ av<>bv 

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

Независимо от того, этот подход на самом деле широко не используется.Возможно, единственное постоянное измерение на самом деле слишком ограничивает большинство релевантных операций, и если вам нужно разворачивать кортежи часто, это слишком малоэффективно. Другим подходом, который взлетает в эти дни, является фактическое пометка векторов с номерами уровня. Такие числа стали доступны в удобной форме с внедрением данных в GHC-7.4. До сих пор они все еще довольно громоздки и не подходят для правильной арифметики, но предстоящий 8,0 значительно улучшит многие аспекты этого зависимого программирования в Haskell.

Библиотека, которая предлагает эффективные массивы с индексированием по длине, - linear.