Как хранить дерево во время рекурсии? (Расшифровка Хаффмана) - PullRequest
Новая
       18

Как хранить дерево во время рекурсии? (Расшифровка Хаффмана)

2 голосов
/ 12 февраля 2020

Я пытаюсь выучить Haskell. Я пытаюсь реализовать Дерево Хаффмана. Параметры моей функции декодирования (в основном, «подпись»): 

decode :: HTree -> [Int] -> [Char]

Итак, учитывая дерево и список чисел, я хочу вернуть декодированное сообщение. Предположим, a = 01, b = 1, c = 001, d = 000.

Я знаю, как это сделать, когда я могу использовать два дерева для декодирования. то есть: 

decode :: HTree -> HTree -> [Int] -> [Char]

Вкратце, оставьте первое дерево в качестве исходного дерева и сделайте другое дерево go влево или вправо на основе следующего числа в [Int] (если это 0, go слева, если это 1, go справа). Повторяйте это, пока не будет достигнут лист, а затем добавьте лист в список [Char] и продолжайте использовать рекурсию. Однако я пытаюсь сделать это только с одним деревом, т.е. Есть ли способ сделать это в haskell?

1 Ответ

2 голосов
/ 12 февраля 2020

Просто напишите рекурсивную вспомогательную функцию, которая имеет доступ к исходному дереву: 

decode :: HTree -> [Int] -> [Char]
decode orig = go orig
  where go :: HTree -> [Int] -> [Char]
        go curr = -- use both orig and curr here
...