Сложность реализации дерева Хаффмана в Хаскеле

Question

Я пытаюсь выучить Haskell, но это действительно сложно, и не так много онлайн-ресурсов. У меня, кажется, есть некоторое непонимание того, как должны выглядеть рекурсивные вызовы, и я был бы рад, если бы они указывали в правильном направлении. Я пытаюсь взять дерево и вернуть каждый листовой узел с символом, хранящимся там, а также путь, пройденный для его получения. (Таким образом, вход (Fork (Leaf x) (Leaf y)) будет иметь выходные данные [(x, [False]), (y, [True])]). Мой код выглядит так:

data htree a = Leaf a | Fork (htree a) (htree a) deriving (Show, Eq)

encode :: htree a -> [(a, [Bool])]
encode (Leaf a) = [(a, ????)]

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

Answer 1

Рассмотрим Fork. У него есть два поддерева, и у каждого из этих поддеревьев есть некоторая кодировка.

Допустим, что кодировка левого поддерева имеет вид:

[(x, pathToX), (y, pathToY)]

И, допустим, кодировка правого поддерева:

[(a, pathToA), (b, pathToB)]

Теперь, вы видите, какой должна быть кодировка всего форка? Должно быть так:

[(a, True : pathToA), (b, True : pathToB), (x, False : pathToX), (y, False : pathToY)]

Согласны ли вы с этим? Если нет, подумайте. Может быть, проработать несколько небольших примеров. Пока вы не согласитесь, что это так.

Видите, что я там делал? Я добавил False к каждому пути в левом поддереве, а затем добавил True к каждому пути в правом поддереве.

Давайте запишем это в синтаксисе Haskell:

encode (Fork left right) = prependToEach False (encode left) ++ prependToEach True (encode right)

Теперь вы, возможно, заметили, что я тут обманул: я использую функцию prependToEach, которой не существует. Ну, неважно, давайте определимся!

prependToEach x list = map (prepend x) list

Видите? Добавление элемента к каждому элементу списка - это просто сопоставление функции добавления одного элемента над списком.

Но, конечно, я снова обманул: такой функции, как prepend, пока нет. Так пусть будет один!

prepend x (a, path) = (a, x : path)

И вот, пожалуйста! Теперь осталось только определить базовый случай: каким должен быть путь Leaf? Что ж, согласно приведенному вами примеру, у каждого Leaf будет пустой путь, отражающий тот факт, что вам не нужно делать никаких ходов, чтобы добраться от этого листа к тому же листу:

encode (Leaf a) = [(a, [])]

А теперь, сложив все вместе:

encode :: HTree a -> [(a, [Bool])]
encode (Leaf a) = [(a, [])]
encode (Fork left right) = prependToEach False (encode left) ++ prependToEach True (encode right)
    where
    prependToEach x list = map (prepend x) list
    prepend x (a, path) = (a, x : path)

И теперь, когда мы понимаем, как это было построено и почему, мы можем немного сократить его, используя списочные представления (хотя я очень сильно рассматриваю этот шагнеобязательно):

encode :: HTree a -> [(a, [Bool])]
encode (Leaf a) = [(a, [])]
encode (Fork left right) = [(x, False : p) | (x, p) <- encode left] ++ [(x, True : p) | (x, p) <- encode right]

---

PS обратите внимание, что тип не может быть назван htree, потому что имена типов в Haskell должны быть заглавными. Вы можете заметить, что я переименовал его в HTree в моем последнем фрагменте.

Answer 2

Хороший ответ Федора , но стоит опасаться использования (++). Часто, если вы не работаете в кафе, это может привести к тому, что ваш код будет работать очень медленно для определенных входных данных, в этом случае несбалансированное дерево.

Причина в том, что (список из N элементов) ++ (список из 1 элемента) должен создать совершенно новый список с N + 1 элементами. Таким образом, добавление только нескольких элементов за один раз таким способом может быть медленным.

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

Вот пример encode функции с использованием этого метода:

data HTree a = Leaf a | Fork (HTree a) (HTree a) deriving (Show, Eq)

encode :: HTree a -> [(a, [Bool])]
encode tree = go [] tree [] where
  go :: [Bool] -> HTree a -> [(a, [Bool])] -> [(a, [Bool])]
  go path (Leaf leaf) = ((leaf, path):)
  go path (Fork left right) = go (False:path) left . go (True:path) right

Обратите внимание, что вам действительно не нужны сигнатуры типов, я просто включил их для ясности (и это, вероятно, хорошая практика), но удалил только 3 строки:

encode tree = go [] tree [] where
  go path (Leaf leaf) = ((leaf, path):)
  go path (Fork left right) = go (False:path) left . go (True:path) right

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