How to write a pattern match in Ocaml so it is easy to scale?

Question

I am learning Jason Hickey's Introduction to Objective Caml.

There is an exercise like this:

Exercise 4.3 Suppose we have a crypto-system based on the following substitution cipher, where each plain letter is encrypted according to the following table.

Plain     | A B C D
--------------------
Encrypted | C A D B

For example, the string BAD would be encrypted as ACB.

Write a function check that, given a plaintext string s₁ and a ciphertext string s₂, returns true if, and only if, s₂ is the ciphertext for s₁. Your function should raise an exception if s₁ is not a plaintext string. You may wish to refer to the string operations on page 8. How does your code scale as the alphabet gets larger? [emphasis added]

---

Basically, I wrote two functions with might-be-stupid-naive ways for this exercise.

I would like to ask for advice on my solutions first.

Then I would like to ask for hints for the scaled solution as highlighted in the exercise.

---

Using if else

let check_cipher_1 s1 s2 = 
    let len1 = String.length s1 in
        let len2 = String.length s2 in              
            if len1 = len2 then
                    let rec check pos =
                        if pos = -1 then
                            true
                        else
                            let sub1 = s1.[pos] in
                                let sub2 = s2.[pos] in
                                    match sub1 with
                                        | 'A' -> (match sub2 with
                                                    |'C' -> check (pos-1)
                                                    | _ -> false)
                                        | 'B' -> (match sub2 with
                                                    |'A' -> check (pos-1)
                                                    | _ -> false)
                                        | 'C' -> (match sub2 with
                                                    |'D' -> check (pos-1)
                                                    | _ -> false)
                                        | 'D' -> (match sub2 with
                                                    |'B' -> check (pos-1)
                                                    | _ -> false)
                                        | _ -> false;
                                            in
                                                check (len1-1)
            else
                false

Using pure match everywhere

let check_cipher_2 s1 s2 = 
    let len1 = String.length s1 in
        let len2 = String.length s2 in
            match () with
                | () when len1 = len2 -> 
                        let rec check pos =
                            match pos with
                                | -1 -> true
                                | _ -> 
                                    let sub1 = s1.[pos] in
                                        let sub2 = s2.[pos] in
                                            (*http://stackoverflow.com/questions/257605/ocaml-match-expression-inside-another-one*)
                                            match sub1 with
                                                | 'A' -> (match sub2 with
                                                            |'C' -> check (pos-1)
                                                            | _ -> false)
                                                | 'B' -> (match sub2 with
                                                            |'A' -> check (pos-1)
                                                            | _ -> false)
                                                | 'C' -> (match sub2 with
                                                            |'D' -> check (pos-1)
                                                            | _ -> false)
                                                | 'D' -> (match sub2 with
                                                            |'B' -> check (pos-1)
                                                            | _ -> false)
                                                | _ -> false
                                                    in
                                                        check (len1-1)
                | () -> false

Ok. The above two solutions are similar.

I produced these two, because in here http://www.quora.com/OCaml/What-is-the-syntax-for-nested-IF-statements-in-OCaml, some people say that if else is not prefered.

This is essentially the first time I ever wrote a not-that-simple function in my whole life. So I am really hungry for suggestions here.

For exmaple,

• how can I improve these solutions?
• should I prefer match over if else?
• Am I designing the rec or use the rec correctly?
• if that in check (len1-1) correct?

---

Scale it

The exercise asks How does your code scale as the alphabet gets larger?. I really don't have a clue for now. In Java, I would say I will have a map, then for each char in s1, I am looking s2 for the according char and to see whether it is the value in the map.

Any suggestions on this?

Answer 1

Here's a simple solution:

let tr = function
  | 'A' -> 'C'
  | 'B' -> 'A'
  | 'C' -> 'D'
  | 'D' -> 'B'
  | _ -> failwith "not a plaintext"

let check ~tr s1 s2 = (String.map tr s1) = s2

check ~tr "BAD" "ACD"

you can add more letters by composing with tr. I.e.

let comp c1 c2 x = try (c1 x) with _ -> (c2 x)
let tr2 = comp tr (function | 'X' -> 'Y')

Answer 2

• how can I improve these solutions?

You misuse indentation which makes the program much harder to read. Eliminating unnecessary tabs and move check to outer scope for readability:

let check_cipher_1 s1 s2 = 
    let rec check pos =
        if pos = -1 then
            true
        else
            let sub1 = s1.[pos] in
            let sub2 = s2.[pos] in
            match sub1 with
            | 'A' -> (match sub2 with
                      |'C' -> check (pos-1)
                      | _ -> false)
            | 'B' -> (match sub2 with
                      |'A' -> check (pos-1)
                      | _ -> false)
            | 'C' -> (match sub2 with
                      |'D' -> check (pos-1)
                      | _ -> false)
            | 'D' -> (match sub2 with
                      |'B' -> check (pos-1)
                      | _ -> false)
            | _ -> false in
    let len1 = String.length s1 in
    let len2 = String.length s2 in              
    if len1 = len2 then
            check (len1-1)
    else false

• should I prefer match over if else?

It depends on situations. If pattern matching is superficial as you demonstrate in the 2nd function (match () with | () when len1 = len2) then it brings no value compared to a simple if/else construct. If you pattern match on values, it is better than if/else and potentially shorter when you make use of advanced constructs. For example, you can shorten the function by matching on tuples:

let check_cipher_1 s1 s2 =  
    let rec check pos =
        if pos = -1 then
           true
        else
            match s1.[pos], s2.[pos] with
            | 'A', 'C' | 'B', 'A' 
            | 'C', 'D' | 'D', 'B' -> check (pos-1)
            | _ -> false in
    let len1 = String.length s1 in
    let len2 = String.length s2 in 
    len1 = len2 && check (len1 - 1)

Here we also use Or pattern to group patterns having the same output actions and replace an unnecessary if/else block by &&.

• Am I designing the rec or use the rec correctly?
• if that in check (len1-1) correct?

Your function looks nice. There's no better way than testing with a few inputs on OCaml top-level.

Scale it

The number of patterns grows linearly with the size of the alphabet. It's pretty nice IMO.