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.
zipWith
, under the assumption that there are no spaces in the input. \$\endgroup\$