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.


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)


    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))

    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.

  • \$\begingroup\$ And what is the result of running that code? \$\endgroup\$
    – Olathe
    Jul 26, 2016 at 3:25

1 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
    toEncoding (c:[]) = Single c
    toEncoding group  = Multiple (length group) (head group)

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

main :: IO ()
main = do
    print $ decode $ encode "Mississippi"
  • \$\begingroup\$ Small remark, using nested parentheses: they are considered to be better than $ by some of the community, see Gabriel's post, as long as your code is intended to be readable by non-Haskell programmers. \$\endgroup\$
    – Zeta
    Jul 26, 2016 at 8:11
  • 1
    \$\begingroup\$ Also, toEncoding (c:[]) = is rather verbose, compared to toEncoding [c] =. \$\endgroup\$
    – Zeta
    Jul 26, 2016 at 8:13
  • \$\begingroup\$ My nested parentheses happen because I mostly treat like a very strange derivation of Lisp, so my initial programs usually look a lot more like a lisp-y language than haskell (so print decode... was actually (print (decode (encode "Mississippi")))), and I'm very concerned about using the composition and feeding (?) (I mean $) operators incorrectly, causing subtle bugs that the compiler doesn't say anything about (because it's error messages suck). Also @Zeta, I had no idea that [c] worked in this context, as it is too similar to foo :: [a] -> [a]. I still prefer (c:[]) for readability. \$\endgroup\$ Jul 26, 2016 at 21:06
  • \$\begingroup\$ Also, is it really necessary to provide a signature for main? \$\endgroup\$ Jul 27, 2016 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.