Vigenere Cipher - Haskell Implementation

Question

I'm reading 'Haskell Programming from First Principles' book written by Christopher Allen and Julie Moronuki. As part of the exercises, I'm supposed to implement encryption and decryption functions for Vigenere cipher.

This is my implementation. I'm using recursion for every letter in the plain text.

shift :: (Int -> Int -> Int) -> Char -> Char -> Char
-- shift applies a arithmetic function to given characters
-- after converting it from ASCII value to Int
-- This can be used to Encrypt or Decrypt the character
shift f i k = let i' = ord i - 65
                  k' = ord k - 65
              in  chr $ ((f i' k') `mod` 26) + 65


crypt :: (Int -> Int -> Int) -> (String, Int) -> (String, Int) -> String -> String
-- crypt applies given artithmetic function and does Vigenere encryption/decryption.
-- This function moves forward on the string, encrypts the
-- current char using corresponding char in key. It maintains
-- current position of the string and key it is working on. When
-- it encounters space, it skips the en(de)cryption and doen't move forward
-- in the key. After encrypting the current char, it recursively calls
-- itself by passing next positions in string to be encrypted along with
-- position of key.
crypt cryptFunc (words', wpos) (key, kpos) cipherText
    | length words' <= wpos =  cipherText
    | otherwise =
        let c  = words' !! wpos
            c' = case c of 
                    ' ' -> ' '
                    _ -> shift cryptFunc c $  key !! kpos
            kpos' = case c of
                    ' ' -> kpos `mod` (length key)
                    _   -> (kpos + 1) `mod` (length key)
            in crypt cryptFunc (words', wpos + 1) (key, kpos') (cipherText ++ [c'])

encrypt :: [Char] -> [Char] -> [Char]
encrypt i k = crypt (+) (i, 0) (k, 0) []

decrypt :: [Char] -> [Char] -> [Char]
decrypt i k = crypt (-) (i, 0) (k, 0) []

-- input = "MEET AT DAWN"
-- key = "ALLY"
-- output = "MPPR AE OYWY"

Do you think the implementation is efficient and obvious way to do it? Please tell if there are any improvements I can do.

Answer 1

Do you think the implementation is efficient

No, sorry. You're heading in the right direction, but !! makes your algorithm \$\mathcal O(n^2)\$, and if it wasn't for !!, appending c' to the cipherText would also lead to \$\mathcal O(n^2)\$ due to ++. Or taking the length all the time. Well, basically any function that you use in each iteration that needs to (possibly) traverse the complete list makes your function non-efficient.

But let us start at the top. I suggest you to put your documentation before the type signature. That way, the type and the names are still close, which makes your function easier to understand if height is limited:

-- shift applies a arithmetic function to given characters
-- after converting it from ASCII value to Int
-- This can be used to Encrypt or Decrypt the character
shift :: (Int -> Int -> Int) -> Char -> Char -> Char
shift f i k = let i' = ord i - 65
                  k' = ord k - 65
              in  chr $ ((f i' k') `mod` 26) + 65

Next, you seem to use a very specific interpretation of Char as Int, namely the position in the alphabet. This is fine, but if you use - 65 and + 65 all the time, it's going to be hard to update it to a larger alphabet. A pair of additional functions and values can help:

toInt :: Char -> Int
toInt c = ord c - 65

fromInt :: Int -> Char
fromInt i = chr i + 65

alphabetSize :: Int
alphabetSize = 26

-- feel free to add your documentation here
shift :: (Int -> Int -> Int) -> Char -> Char -> Char
shift f i k = let i' = toInt i
                  k' = toInt k
              in  fromInt $ f i' k' `mod` alphabetSize

By the way, with on from Data.Function one could write

shift :: (Int -> Int -> Int) -> Char -> Char -> Char
shift f i k = let f' = f `on` toInt
              in  fromInt $ f i k `mod` alphabetSize

but that's just a remark (Exercise: try to guess on's type. How would a valid implementation look like?).

Next, we head over to crypt. Let us assume for a second that the key is longer than the text we want to encrypt. We want to encrypt each character on its own. So if we have a string, we can pattern match. We start with the easier case:

crypt' :: (Int -> Int -> Int) -> String -> String -> String
crypt' _ [] _ = []

If there's nothing to encrypt, there's nothing to return. Now, what should we do if there is at least one character? Well, we check whether it is a space. If it is a space, we add a space to our result and continue on the rest:

crypt' f (' ':ws) ks = ' ' : crypt f ws ks

A space goes in, a space goes out. We do not change the key. So now there is only one case missing: the one where we have a character that's not a space:

crypt' f (w:ws) (k:ks) = shift f w k : crypt f ws ks

A character goes in, a character from the key goes in, we use the function to shift and create the result, and then we continue on our other words and keys.

Here's crypt' at once:

crypt' :: (Int -> Int -> Int) -> String -> String -> String
crypt' _ []       _      = []
crypt' f (' ':ws) ks     = ' '         : crypt' f ws ks
crypt' f (w:ws)   (k:ks) = shift f w k : crypt' f ws ks

However, this does only work if the key is longer than the text. How do we write crypt, which may take a smaller key? We use cycle:

crypt :: (Int -> Int -> Int) -> String -> String -> String
crypt f w k = crypt' f w (cycle k)

That's not necessary by the way, you could have defined a function inside of crypt, check whether the "local" key is [] and then start over:

crypt f w k = go w k 
  where
    go ...

but that's left as another exercise.

Further remarks

Do you think the implementation is … [an] obvious way to do it?

It's an obvious way in imperative languages, which have a string as an array or similar data structure, since index-wise accessing is fast, and .push_back or other "append-single-character-at-end" functions are usually (amortized) constant.

So if you're coming from an imperative language, yes, that would be the obvious way to implement it there (well, aside from the recursiveness).

But in Haskell keep in mind that lists are, well, lists. If you want to access the 20th element, you have to skip the first 19. !! isn't a care-free operation like a vector access in several other operations. Neither is length. That's why it's usually a good idea to pattern match (or use higher-order-functions) and create the list with :.

Exercises

• Adjust encrypt and decrypt to crypt's new type.
• What is the type signature of cycle? Can you implement it yourself?
• (*) Instead of (Int -> Int -> Int), have crypt use (Char -> Char -> Char). (Why?)
• (*) Make it possible to use both upper and lower characters in your text.
• (*) Keep unsupported characters
• (**) Instead of (Char -> Char -> Char), have crypt use (a -> a -> a). (Is this possible? What do you have to change to make it possible? Why?)
• (***) Make it possible to encrypt/decrypt arbitrary alphabets, if given "nice" toInt and fromInt functions.