1
\$\begingroup\$

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.

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

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"
\$\endgroup\$
  • \$\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 '16 at 8:11
  • 1
    \$\begingroup\$ Also, toEncoding (c:[]) = is rather verbose, compared to toEncoding [c] =. \$\endgroup\$ – Zeta Jul 26 '16 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\$ – Eliza Brandt Jul 26 '16 at 21:06
  • \$\begingroup\$ Also, is it really necessary to provide a signature for main? \$\endgroup\$ – Eliza Brandt Jul 27 '16 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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