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.

• Olathe: And what is the result of running that code?

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"

• Zeta: 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.
• Zeta: Also, toEncoding (c:[]) = is rather verbose, compared to toEncoding [c] =.
• Eliza Brandt: 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.
• Eliza Brandt: Also, is it really necessary to provide a signature for main?