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

Он написал, что кортежи 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, по сравнению с кортежем, используемым для хранения позиционных значений тех же типов, аргументы конструктора значения?

Ответ 1

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

Существуют некоторые практические различия:

Лень
. Корзины Haskell ленивы, и вы не можете это изменить. Однако вы можете пометить поля конструктора как строгие:
```
data Tree a = EmptyTree | Node !a !(Tree a) !(Tree a)
```
Объем памяти и производительность. Обход промежуточных типов уменьшает площадь и повышает производительность. Вы можете больше узнать об этом в этом прекрасном ответе.

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

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

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

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

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

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

Ответ 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)). Вы могли бы просто написать функции, которые конвертируют между ними.

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