В чем разница между конструкторами значений и кортежами?

Question

It's written что кортежи Haskell - это просто другой синтаксис для алгебраических типов данных. Аналогично, есть примеры переопределения конструкторов значений с кортежами.

Например, тип данных Дерева в Haskell может быть записан в виде

data Tree a = EmptyTree | Node a (Tree a) (Tree a) 

, которые могут быть преобразованы в «форме кортежа», как это:

data Tree a = EmptyTree | Node (a, Tree a, Tree a) 

В чем разница между Node конструктор значения в первом примере и фактический tuple во втором примере? то есть Node a (Tree a) (Tree a) против (a, Tree a, Tree a) (кроме только синтаксиса)?

Под капотом есть Node a (Tree a) (Tree a) только другой синтаксис для 3-х кортежей соответствующих типов в каждой позиции?

Я знаю, что вы можете частично применить конструктор значения, такие как Node 5, который будет иметь вид: (Node 5) :: Num a => Tree a -> Tree a -> Tree a

Вы вроде можно частично применить кортеж тоже используя (,,) как функцию ... но это Безразлично» т знать о потенциальных типах для оОН переплета записей, такие как:

Prelude> :t (,,) 5 
(,,) 5 :: Num a => b -> c -> (a, b, c) 

, если я не догадываюсь, вы явно объявить тип с ::.

Помимо синтаксических специальностей, подобных этому, а также этот последний пример охвата типов, существует материальная разница между тем, что фактически имеет свойство «конструктор значений» в Haskell, по сравнению с кортежем, используемым для хранения позиционных значений тех же типов аргументы конструктора значения?

Answer 1

Ну, конечно, действительно нет разницы, и на самом деле другие языки (OCaml, Elm) представляют тегированные объединения именно таким образом - т. Е. Теги над кортежами или записи первого класса (которых у Haskell не хватает). Я лично считаю это ошибкой дизайна в Haskell.

Есть некоторые практические различия, хотя:

1. Лень. Корзины Хаскелла ленивы, и вы не можете это изменить. Однако вы можете пометить конструктор полей, как строги: след

   data Tree a = EmptyTree | Node !a !(Tree a) !(Tree a) 
   

2. памяти и производительность. Обход промежуточных типов уменьшает площадь и повышает производительность. Вы можете прочитать об этом в this fine answer.

   Вы также можете отметить строгие поля с помощью the UNPACK pragma, чтобы еще больше уменьшить след. В качестве альтернативы вы можете использовать the -funbox-strict-fields compiler option. Что касается последнего, я просто предпочитаю его использовать по умолчанию во всех моих проектах. См., Например, the Hasql's Cabal file.

---

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

data Tree a = EmptyTree | Node a (Tree a) (Tree a) 

data Tree a = EmptyTree | Node {-# UNPACK #-} !(a, Tree a, Tree a) 

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

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

Answer 2

Они называются изоморфными, что означает «иметь ту же форму». Вы можете написать что-то вроде

data Option a = None | Some a 

И это изоморфна

data Maybe a = Nothing | Just a 

означает, что вы можете написать две функции

f :: Maybe a -> Option a 
g :: Option a -> Maybe a 

f . g == id == g . f Такое, что для всех возможных входов. Тогда можно сказать, что (,,) является конструктором данных изоморфными конструктору

data Triple a b c = Triple a b c 

Потому что вы можете написать

f :: (a, b, c) -> Triple a b c 
f (a, b, c) = Triple a b c 

g :: Triple a b c -> (a, b, c) 
g (Triple a b c) = (a, b, c) 

И Node как конструктор является частным случаем Triple, а именно Triple a (Tree a) (Tree a). На самом деле, вы могли бы даже пойти так далеко, чтобы сказать, что ваше определение Tree может быть написана как

newtype Tree' a = Tree' (Maybe (a, Tree' a, Tree' a)) 

newtype требуется, так как вы не можете иметь type псевдоним рекурсивным. Все, что вам нужно сделать, это сказать, что EmptyLeaf == Tree' Nothing и Node a l r = Tree' (Just (a, l, r)). Вы могли бы просто написать функции, которые конвертируют между ними.

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