Encoding and decoding in Haskell -- 99 Problems exercise 13, 14

Question

I've been working on these solutions to the Haskell 99 questions, encoding and decoding series for a while now, so I figured I ought to present them to see how I screwed up the implementation.

Problems:

Encoding: Write a function which encodes a series of characters using run-length encoding and an algebraic data type such that the sequence "aaaabccaadeeee" outputs:

[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']

Decoding: Write a function which decodes a series of algebraic data types representing run-length encoding as a series of characters such that the sequence

[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']

outputs "aaaabccaadeeee".

Here is the code I used for the problems:

import Data.List

main = do
    print $ decode (encode "Mississippi")


data Encoding = Multiple Int Char | Single Char deriving (Show)

encode :: [Char] -> [Encoding]

encode chars= map toEncoding ( (countChars . group) chars)

    where


    countChars :: [String] -> [(Int, Char)]
    countChars strings = map countCharsHelper strings

    countCharsHelper :: String -> (Int, Char)
    countCharsHelper chars = (length chars, head chars)

    toEncoding :: (Int, Char) -> Encoding
    toEncoding (1, a) = Single a
    toEncoding (num, a) = Multiple num a

decode :: [Encoding] -> [Char]

decode encodings = foldl (++) "" (map replicateChars (map fromEncoding encodings))
    where


    fromEncoding :: Encoding -> (Int, Char)
    fromEncoding (Multiple num char) = (num, char)
    fromEncoding (Single char) = (1, char)

    replicateChars :: (Int, Char) -> [Char]
    replicateChars (num, char) = replicate num char

And the output is the expected output "Mississippi", while decode and encode testing correctly via GHCi.

Answer 1

The general idea, which is to use group and Data.List.group and replicate, is right. Your implementation is a bit verbose, though.

The top-level functions (encode, decode, and main) should have type signatures. You didn't write one for main :: IO (). The inner functions, though, don't need type signatures, since the compiler can infer their types.

Avoid nesting parentheses. All of your nested parentheses could be written with $ instead. For example:

print $ decode $ encode "Mississippi"

I don't think you need so many helper functions.

Both encode and decode could be written in point-free style.

Writing decode = foldl (++) "" (map replicateChars (map fromEncoding encodings)) is too complicated. concatMap would do the trick.

import Data.List (group)

data Encoding = Multiple Int Char | Single Char deriving (Show)

encode :: String -> [Encoding]
encode = map toEncoding . group
  where
    toEncoding (c:[]) = Single c
    toEncoding group  = Multiple (length group) (head group)

decode :: [Encoding] -> String
decode = concatMap fromEncoding
  where
    fromEncoding (Single char)       = [char]
    fromEncoding (Multiple num char) = replicate num char

main :: IO ()
main = do
    print $ decode $ encode "Mississippi"