Caesar cipher in F#

I'm trying to broaden my horizon by learning functional programming (coming from OO, specficially C#). For this, I'm implementing some small problems to get a feeling for the language. One of my first is the Caesar cipher.

Formal problem statement:


Implement a Caesar cipher, both encoding and decoding.
The key is an integer from 1 to 25. This cipher rotates the letters of the alphabet (A to Z).
The encoding replaces each letter with the 1st to 25th next letter in the alphabet (wrapping Z to A).
So key 2 encrypts "HI" to "JK", but key 20 encrypts "HI" to "BC".
This simple "monoalphabetic substitution cipher" provides almost no security, because an attacker who has the encoded message
can either use frequency analysis to guess the key, or just try all 25 keys.

One change I did implement was that the shift is not constrained to 1 - 25, but can be any (positive) number. Note also that I'm okay with converting the input/output to upper case.

What I'm most interested in is whether what I wrote is idiomatic F# or if there are better (more functional) ways of doing things.

```
(*
Caesar cipher -
Implement a Caesar cipher, both encoding and decoding.
The key is an integer from 1 to 25. This cipher rotates the letters of the alphabet (A to Z).
The encoding replaces each letter with the 1st to 25th next letter in the alphabet (wrapping Z to A).
So key 2 encrypts "HI" to "JK", but key 20 encrypts "HI" to "BC".
This simple "monoalphabetic substitution cipher" provides almost no security, because an attacker who has the encoded message
can either use frequency analysis to guess the key, or just try all 25 keys.
*)

open System

let alphabet = [| 'A' .. 'Z' |]

let tryGetIndex c =
let idx = alphabet
|> Array.tryFindIndex (fun t -> t = (Char.ToUpper c))
(c, idx)

// own modulo operation because f# % doesn't work right for us if
// we're handling negative numbers
// f#: -3 % 26 -> -3
// 'ours': modulo -3 26

Disclaimer: I know almost no F#. But I know Haskell. So I think I should be able to give some insight. An F# expert can give you more, of course.

Re-use of functions

One thing that strikes me as odd is that you have two shift functions, encryptIdx and decryptIdx. Well, the number of shift functions isn't what I'm concerned with, to be honest, but the different requirements on the shift value.

Where decryptIdx can take any shift (even a negative one), encryptIdx will return a value out of [| 0 .. 25 |] if you supply a negative one due to the property of % you've displayed nicely in the comment. That's not immediately obvious for someone, so you should mention in the documentation/comments that encryptIdx may only use a non-negative shift.

However, the bigger problem is that both implementations can get out of sync. Let's say that at some point you decide to use another alphabet, e.g.

let alphabet2 = [| '0' .. 'z' |]

You change your encryptIdx, but you forget to change it in decryptIdx. Ouch. So instead, let us write one in terms of the other, or rather in terms of another function:

let shiftIdx shift idx = 
    let newIdx = idx + shift
    modulo newIdx alphabet.Length

let encryptIdx shift idx =
    shiftIdx shift idx

let decryptIdx shift idx = 
    shiftIdx (-shift) idx

Note that I've changed the order of arguments. Why? Because it enables us to use currying:

let encryptIdx shift =
    shiftIdx shift

let decryptIdx shift = 
    shiftIdx (-shift)

Combining functions

Either way, let us now look at getShifted. I'm kidding. getShifted is perfectly fine with your current combination of tryGetIndex returning a pair.[remark 1]

But operateCaesar could use a little polish. First of all, we can get rid of the shift > Seq.map g is the same as Seq.map (f >> g), so we have only one Seq.map call.[remark 2]

Before we leave that function, let us think about types. operation will be an int -> int. shift will be an int. And text will be a seq. The result will be a String. However, if we restrict text to be a String, we can use String.map instead of Seq.map and make the function easier again:

let operateCaesar operation shift text =
    text 
    |> String.map (tryGetIndex >> getShifted shift operation)

Now for a short test. Remember my remark about currying? That

let f bar baz = g magic bar baz

is the same as

let f = g magic

With that in mind, how can you rewrite operateCaesar above or the next two lines?

let encryptcaesar shift text = operateCaesar encryptIdx shift text
let decryptcaesar shift text = operateCaesar decryptIdx shift text

The solution will be in the code below, so make sure to think about it before you scroll further.

All in all, we end up with:

open System

let alphabet = [| 'A' .. 'Z' |]

let tryGetIndex c =
    let idx =   alphabet
                |> Array.tryFindIndex ((=) (Char.ToUpper c ))
    (c, idx)

let modulo n m = ((n % m) + m) % m

let shiftIdx shift idx = 
    let newIdx = idx + shift
    modulo newIdx alphabet.Length

let encryptIdx shift = shiftIdx shift
let decryptIdx shift = shiftIdx (-shift)

let getShifted shiftOperation shift charIdx =
    match charIdx with
    | _, Some idx -> alphabet.[shiftOperation shift idx]
    | c, None -> c

let operateCaesar operation shift = String.map (tryGetIndex >> getShifted operation shift)

let encryptcaesar = operateCaesar encryptIdx
let decryptcaesar = operateCaesar decryptIdx

I took the courtesy to change the order of arguments in getShifted so that it reflects the order of arguments in operateCaesar better.

Remarks on your original code in a nutshell

So what were my major critique points? Function re-use. encryptIdx and decryptIdx are well suited to be implemented in terms of each other.

Another approach

Let us change tryGetIndex slightly and make it true to its name:

let tryGetIndex c =
    alphabet
    |> Array.tryFindIndex ((=) (Char.ToUpper c))

It now returns an Option, so just the index. Now we need another function, fromIndex:

let fromIndex idx = alphabet.[idx]

Now we can write a combined variant of tryGetIndex >> getShifted:

let characterShift shiftFunc c =
    tryGetIndex c |> Option.fold (fun _ v -> fromIndex (shiftFunc v)) c

The Option.fold uses the given function if the Option is Some and returns the second argument otherwise. So we either had an index, shift it and return the corresponding character, or we didn't, and therefore return the original character. Note that shiftFunc here is a function that shifts the character accordingly, e.g. encryptIdx 10. That's all in the article linked above, though.

We end up with the following operateCaesar:

let operateCaesar op shift = 
    String.map (characterShift (op shift))

Remark 1: We will revisit that soon enough.

Remark 2: I sincerely hope that F#'s compiler does this optim

StackExchange Code Review Q#162169, answer score: 6