Search code examples
listfunctionhaskellshiftcaesar-cipher

Caesar Shift function in Haskell?

I have to write a shift function that searches an element's pair from a "table" (list). And if the element is not in the given list, it has to give a '#' az a result.

Examples:

shift [('b', 'g'), ('c', 'h'), ('a', 'f')] 'a' == 'f'
shift [('b', 'g'), ('c', 'h'), ('a', 'f')] 'b' == 'g'
shift [('b', 'g'), ('c', 'h'), ('a', 'f')] 'b' == 'g'
shift [('b', 'g'), ('c', 'h'), ('a', 'f')] 'x' == '#'

My code:

shift :: [(Char,Char)] -> Char -> Char
shift z c = [b |(a,b)<-z,a==c]!!0

It works, but not for the exceptions. I can't seem to make it work for elemnts that are not in the list. I have tried:

shift z c 
    | c `elem` z =[b |(a,b)<-z,a==c]!!0
    | otherwise ='#'

and a helper function:

isgood z c
    | c `elem` z = (shift z c)
    | otherwise = '#'

But they don't work. How to solve this?

Solution

  • There are lots of ways you can go about writing this, which all essentially do the same thing.

    One way is just a slight modification of one of your previous attempts, the one which "works, but not for the exceptions":

    shift :: [(Char,Char)] -> Char -> Char
shift z c = [b |(a,b)<-z,a==c]!!0

    The only problem with this, as I'm sure you've observed, is that the program crashes when you failed to find the character, rather than the function giving you '#' as desired. This is because (!! 0), like head (which it is equivalent to), fails with an ugly runtime error when applied to an empty list. So all you need to do is to check if the list is empty or not, and either take the first element or give the default answer. The neatest way to do this in my opinion is to pattern match in a case expression:

    shift :: [(Char,Char)] -> Char -> Char
shift z c = case [b |(a,b)<-z,a==c] of
    [] -> '#'
    (c:_) -> c

    But this concept of looking something up in a "lookup table" in the form of a list of pairs is so standard that the Haskell Prelude already has a function for it, called, naturally, lookup. It returns a Maybe type as a safe way of handling failure, and you can pattern match on the result in a similar way as in the previous version if you want:

    shift z c = case (lookup c z) of
    Nothing -> '#'
    Just c -> c

    and this can be further simplified using fromMaybe, another standard library function:

    shift z c = fromMaybe '#' (lookup c z)

    Two further points to finish:

    • using a list of pairs as a dictionary like data structure, while OK for simple cases, is not very efficient. It's better to use a specialised structure such as Map for this.
    • shift is a strange name for this function, since it needs a lookup table of arbitrary pairs. For a genuine Caesar shift cipher the table is implicit in the shift number, and you would want a function of type Int -> Char -> Char, which would be implemented rather differently.