Насколько я знаю, в Haskell считается хорошим тоном выносить как можно больше информации в сигнатуры функций. Я сейчас пишу программу, строящую коды Хаффмана, и не могу придумать, как мне объявить структуру данных для соответствующего дерева.
Обычное дерево (которое data Tree a = Tree (Tree a) (Tree a) | Leaf a) мне не подходит по той причине, что как левое, так и правое поддеревья могут произвольно ветвиться дальше. Дерево же Хаффмана всегда ветвится, так сказать, в одном направлении (например, только вправо). В голову сразу же приходит вот такая штука:
data HuffmanTree a = HuffmanTree (Leaf a) (HuffmanTree a) | …
data Leaf a = Leaf a …
Троеточиями обозначены части, которые не получается придумать из-за наложенного ранее условия. Последний элемент дерева (находящийся на наибольшей глубине) должен иметь два листа, но в терминах описанной структуры это выразить не получится :( Можно было бы добавить в HuffmanTree ещё одно поле типа a, но оно не будет использоваться нигде, кроме последней ноды. Как быть?
P.S. В пакете huffman использовали обыкновенное (первое из приведённых здесь) бинарное дерево.
6 comments
recommend
bookmark
subscribe
data HuffmanTree a = HuffmanTree (Leaf a) (HuffmanTree a) | Leaf a
Хуле.
Not in scope: type constructor or class `Leaf'
А, блин, сорри.
data HuffmanTree a = HuffmanTree (Leaf a) (HuffmanTree a) | HuffmanTree (Leaf a) (Leaf a)
data Leaf a = ...
Нельзя создавать два type constructor'а с одинаковыми именами :(
Твой первый пример сделал меня думать, что я не умею объявлять типы данных, так что я погуглил haskellwiki data, почитал про Rose Tree и придумал вот что:
data HuffmanTree a = HuffmanTree a (HuffmanTree a) | Leaf a
Не очень красивый хак, конечно, но я считаю это решением проблемы. Спасибо, 0xd34df00d ;)
Печаль, я неправильно понял алгоритм и на самом деле мне нужно было самое настоящее бинарное дерево.