Деревья в Haskell

Question

Тем не менее изучение Haskell, и я не могу видеть разницу между

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

и

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

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

Answer 1

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

Answer 2

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

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

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

Answer 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 использует полевые лейбла и синоним типа.

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