Почему (a, b, c, d) не сахар для (a, (b, (c, (d,()))))?

Question

Понятно, что любой n-кортеж может быть представлен связкой вложенных 2-кортежей. Так почему же они не то же самое в Haskell? Разве это что-то сломает?

Выполнение этих эквивалентов типов значительно упростит функции записи на кортежах. Например, вместо определения zip, zip2, zip3 и т. Д. Вы можете определить только одну функцию zip, которая будет работать для всех кортежей.

Конечно, вы можете работа с вложенными 2-кортежами, но это некрасиво и нет никакого канонического пути для выполнения вложенности (т.е. должны ли мы гнездо влево или вправо?).

Answer 1

Тип (a,b,c,d) имеет различный профиль производительности от (a,(b,(c,(d,())))). Как правило, индексирование в n-кортеж принимает O(1), а индексирование в «hlist» из n вложенных кортежей принимает O(n).

Тем не менее, вы должны проверить классические работы Олега на HLists. Использование HLists требует обширного и несколько отрывочного использования программирования уровня. Многие люди считают это неприемлемым, и он не был доступен в раннем Haskell. Возможно, лучший способ, чтобы представить HList сегодня с GADTs и DataKinds

data HList ls where 
    Nil :: HList '[] 
    Cons :: x -> HList xs -> HList (x ': xs) 

Это даст каноническое вложение, и позволяет писать функции, которые работают для всех экземпляров этого типа. Вы можете реализовать свой многопользовательский способ zipWith, используя те же методы, что и в printf. Более интересная головоломка состоит в том, чтобы сгенерировать соответствующие линзы для этого типа (подсказка: использовать типы типов naturals и типы семейств для индексации).

Я рассмотрел возможность создания библиотеки HList, которая использовала массивы и unsafeCoerce под капотом, чтобы получить кортеж как производительность, придерживаясь общего интерфейса. Я этого не делал, но это не должно быть слишком сложно.

EDIT: чем больше я думаю об этом, тем более склонным я должен что-то взломать, когда у меня есть время. Повторяющаяся проблема копирования Андреаса Росберга упоминается, вероятно, может быть устранена с использованием потокового синтеза или аналогичных методов.

Answer 2

Основная проблема с этим в Haskell заключается в том, что вложенный кортеж допускает дополнительные значения из-за лени. Например, тип (a,(b,()) населен всеми (x,_|_) или (x,(y,_|_)), что не относится к плоским кортежам. Существование этих значений не только семантически неудобно, но и затрудняет оптимизацию кортежей.

На строгом языке, однако, ваше предложение действительно является возможностью. Но он все еще вводит ошибку производительности: реализации все равно хотели бы сгладить кортежи. Следовательно, в тех случаях, когда вы фактически строите или деконструируете их индуктивно, им придется много повторять копирование. Когда вы используете действительно большие кортежи, это может быть проблемой.