как пройти древовидную структуру и изменить ее тип данных - PullRequest
Новая
       20

как пройти древовидную структуру и изменить ее тип данных

0 голосов
/ 08 февраля 2019

Я пытаюсь реализовать кодирование Хаффмана в haskell и использовать следующие две структуры данных: 

data Htree = Leaf Char | Branch Htree Htree deriving Show
data Wtree = L Integer Char | B Integer Wtree Wtree deriving Show

, где Wtree создается первым на основе частоты / веса каждого символа.После того, как Wtree создан, и мы знаем структуру дерева, мне больше не нужны веса каждого листа / ветви, поэтому я хочу преобразовать Wtree в Htree, но у меня возникают проблемы при решении этой проблемы. 

createHtree :: Wtree -> Htree
createHtree(L _ char) = Leaf char
createHtree(B _ w1 w2) = Branch createHtree(w1) createHtree(w2)

Это решение, которое я пробовал, но оно не скомпилируется

Ожидаемый результат, как я уже упоминал, - преобразование Wtree в Htree, которое требует только удаления целочисленной части Wtree.

1 Ответ

0 голосов
/ 08 февраля 2019

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

data HTree a = Leaf a Char | Branch a (HTree a) (HTree a)

Тогда ваше взвешенное деревоHTree Integer, а ваше невзвешенное дерево - HTree (), что означает, что вы не хотите хранить дополнительные данные в дереве.Таким образом, Haskell может ясно видеть, что ваши два типа тесно связаны - с кодом, который вы разместили в вопросе, они представляются двумя совершенно не связанными типами.Если вы дополнительно включите одно безобидное языковое расширение, вы можете использовать эту близкую связь, чтобы вообще не писать конверсию! 

{-# LANGUAGE DeriveFunctor #-}

import Data.Functor ((<$))

data HTree a = Leaf a Char
             | Branch a (HTree a) (HTree a)
             deriving Functor

stripLabels :: HTree a -> HTree ()
stripLabels = (() <$)

Обратите внимание, что теперь stripLabels настолько просто, что вам даже не нужночтобы определить его: вы можете просто вставить его на сайтах использования.

...