Деревья в Хаскелле

Продолжение обучения haskell, и я действительно не вижу разницы между

data Tree a = Leaf a | Branch [Tree a]

data Tree a = Leaf a | Branch (Tree a) (Tree a)

Что лучше всего по тебе? Каковы последствия этих двух способов написания?

Ответ 1

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

Ответ 2

Первое определяет дерево, в котором каждая ветвь может иметь произвольное множество поддеревьев (представленное как список деревьев), а последнее определяет дерево, в котором каждая ветвь имеет ровно два поддерева.

Другими словами, первое является общим деревом, а второе - двоичным деревом.

Итак, какой из них выбрать, зависит от того, хотите ли вы моделировать общее дерево или двоичное дерево.

Ответ 3

Я поставил это как ответ, а не комментарий, поэтому он имеет некоторое форматирование:

data Rose a = Branch a [Rose a]
  deriving (Show)


sample1 :: Rose Int
sample1 = Branch 1 [Branch 2 [], Branch 3 [Branch 5 []], Branch 4 []]

Это то же самое, что и библиотечный модуль Data.Tree, хотя Data.Tree использует метки полей и синоним типа.

Я видел как это дерево, так и ваше первое определение под названием "Розовые деревья", хотя они имеют несколько иные формы, поэтому терминология не кажется полностью точной. Моя интерпретация заключается в том, что это список "[Роза]", встроенный в единственный рекурсивный конструктор, который определяет его как дерево розы.