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

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

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

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

Ответы

Ответ 1

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

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

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

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

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

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

Ответ 2

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

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