Дерево или нет (понимание типа Haskell)

Question

В «Нежном введении в Haskell» у нас есть такое объявление типа Tree:

data Tree a = Leaf a | Branch (Tree a) (Tree a)
     deriving (Eq,Ord,Show,Read)

Давайте сделаем несколько значений этого типа:

a1 = Leaf 1
a2 = Leaf 2
a3 = Leaf 3
a4 = a1 `Branch` a2
a5 = a2 `Branch` a3
a6 = a4 `Branch` a5

в ghci:

*Main> :t a6
a6 :: Tree Integer

Но a6 вовсе не Дерево, см .:

      a6
     / \
   a4   a5
  / \  /  \
a1   a2    a3

На этом графике есть цикл! Что случилось? Является ли определение типа дерева правильным? Или, может быть, я не могу уловить какую-то ошибку в понимании этого примера ...

Answer 1

Мы должны различать значение выражения и его представление в памяти.

Например, оба эти выражения имеют одинаковое значение :

e1 = ("Hello", "Hello")
e2 = let s = "Hello" in (s, s)

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

Реализация на Haskell (например, GHC) может представлять эти значения в памяти любым способом, который не нарушает семантику. Например:

1. Может дважды сохранить строку "Hello" в памяти, а затем использовать пару указателей (p1, p2).
2. Он может сохранить строку "Hello" один раз в памяти, а затем использовать пару указателей (p, p).

Обратите внимание, что теоретически оба представления могут использоваться для любого из выражений e1,e2 выше. На практике GHC будет использовать первое для e2, а второе для e1, но это не важно.

На ваших деревьях возникает та же проблема. Значение вашего a6 - это дерево. GHC, вероятно, представляет это дерево как DAG, не являющийся деревом (то есть DAG, который, если преобразован в неориентированный граф, имеет цикл), но это не имеет значения, это всего лишь деталь реализации. Важным аспектом является то, что такое представление учитывает семантику дерева.

Тогда можно задаться вопросом, почему представление DAG является правильным, если значение является деревом. Это верно, потому что в Haskell мы не можем сравнивать базовые «ссылки» p, используемые GHC. Если бы у нас была функция comparePtr :: a -> a -> Bool, которая сравнивает такие ссылки, мы могли бы различать e1 и e2, используя comparePtr (fst e) (snd e) для e между e1, e2. Это ужасно нарушило бы правильность реализации. В Хаскеле, однако, этого нет.

(Технически, есть функция unsafe, которая делает это, но функции unsafe никогда не должны использоваться в "нормальном" коде. Мы обычно притворяемся, что они не существуют.)

Answer 2

Короткий ответ заключается в том, что концептуально, a2 "является" Tree a, а не ссылкой на Tree a. В этом смысле a6 действительно выглядит как

          a6
       /      \
     a4        a5
    /   \    /    \
  a1   a2   a2    a3

то есть в дереве есть две "копии" a2.

На практике, поскольку все значения являются неизменяемыми, реализация может использовать одну и ту же память для представления как правого дочернего элемента a4, так и левого дочернего элемента a5, но эти два узла остаются различными на уровне абстракции. представлен типом Tree a.

Для того, чтобы на самом деле иметь цикл, необходимо иметь представление о возможности достижения a4 и a5 с a2, и этот тип не обеспечивает представление для любого такого потомка родительские ссылки, что делает невозможным определить, являются ли левый дочерний элемент a4 и правый дочерний элемент a5 тем же узлом , что и , или двумя разными узлами, которые выглядят абсолютно одинаково. Для этого типа данных различие просто не существует.