Haskell - Huffman Декодирование без дерева

Question

Итак, для задания, которое мне было предоставлено, у меня было три функции для завершения: для извлечения HCodeMap из каждого листового узла данного дерева для кодирования строки в список битов, и декодировать эту строку бит обратно в строку.

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

Это формат функции, а затем некоторые из типов мы снабжаются:

decode :: [Bit] -> HCodeMap -> Maybe String 

data Bit = Zero | One deriving (Show, Eq) 
type HCodeMap = [(Char, [Bit])] 

Первоначально я пытался создать свою собственную функцию поиска, которая будет поменять значения HCodeMap, а затем для поиска первых n бит из списка битов, которые мы даем.

Я буду использовать пример, чтобы продемонстрировать, если я не сделал себе очень ясно:

[Бит] заданы: [один, ноль, один, один, ноль]

HCodeMap мы даем: [('c', [Zero]), ('a', [One, Zero]), ('b', [One, One])]

Я планировал взять первый бит, мы получаем из списка, являющегося одним, а затем для поиска через HCodeMap-тестирование, чтобы убедиться, что он был равен любому из [бит].

Здесь я бы включил функцию обратного поиска, так как я мог искать список бит внутри HCodeMap, поскольку я не могу искать по букве. Это было по линии:

поиска (биты мы приведены здесь) (каждый кортеж HCodeMap) $ Карта замены кода

В этом случае мы видим, что один не соответствует ни одному из HCodeMap кортежи, поэтому я затем тестирую One, Zero. Это соответствует «a», поэтому я добавляю «a» к строке, а затем продолжаю со следующего [Бит], который мы передаем, будучи снова одним.

и т. Д. И т. Д. Это продолжается, и мы остаемся со строкой «abc».

Я действительно борется с тем, как на самом деле положить это в функцию.

Надеюсь, я не сделал это слишком запутанным, спасибо за любую помощь заранее!

Answer 1

Попробуйте последовательно разобрать все коды, а затем повторить после успешного матча. Повторяйте, пока нет ввода.

import Control.Monad 

data Bit = Zero | One deriving (Show, Eq) 
type HCodeMap = [(Char, [Bit])] 

decode :: [Bit] -> HCodeMap -> Maybe String 
decode bits codes = process bits where 

    -- if the code matches the input, return the corresponding 
    -- Char value along with the rest of of the input 
    match :: (Char, [Bit]) -> [Bit] -> Maybe (Char, [Bit]) 
    match (v, xs) ys = go xs ys where 
    go (x:xs) (y:ys) | x == y = go xs ys 
    go []  ys    = Just (v, ys) 
    go _  _    = Nothing 

    -- match and consume until there's no more input, or fail if there is no match. 
    -- note that msum takes the first Just from a list of Maybe-s, 
    -- or returns Nothing if there isn't any 
    process :: [Bit] -> Maybe String 
    process [] = Just [] 
    process xs = do 
    (v, xs) <- msum $ map (`match` xs) codes 
    (v:) `fmap` process xs 

Для тех, кто не знаком с msum, вот его реализация специализируется на Maybe:

msum :: [Maybe a] -> Maybe a 
msum (Just a:xs) = Just a 
msum (Nothing:xs) = msum xs 
msum []   = Nothing