Geek Answers Handbook

How to write pattern matching in Ocaml, so it's easy to scale?

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

There is such an exercise:

Exercise 4.3 Suppose we have a cryptosystem based on the following substitution encryption, where each simple letter is encrypted in accordance with the following table.

Plain | ABCD -------------------- Encrypted | CADB

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

Write the check function, which is specified by the plaintext string s 1 and the ciphertext string s 2 , returns true if and only if s 2 is the ciphertext for s 1 . Your function should throw an exception if s 1 is not a plaintext string. You can refer to string operations on page 8. How does your code scale up as the alphabet grows? [italics]

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

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

Then I would like to request hints for a scaled solution, as indicated 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 coincidence 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 created the two because here http://www.quora.com/OCaml/What-is-the-syntax-for-nested-IF-statements-in-OCaml some say that if else not preferable.

This is essentially the first time I've written a not-that-simple function in my entire life. So, I really crave suggestions here.

For exmaple

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

Zoom

Exercise asks How does your code scale as the alphabet gets larger? . At the moment, I have no clue. In Java, I would say that I will have a map , and then for each char in s1 , I look at s2 for the corresponding char and see if this is a value on the map.

Any suggestions on this?

+4
source share
3 answers

The simplest solution is to simply encrypt the text and compare the result:

 let cipher_char = function | 'A' -> 'C' | 'B' -> 'A' | 'C' -> 'D' | 'D' -> 'B' | _ -> failwith "cipher_char" let cipher = String.map cipher_char let check_cipher s1 s2 = (cipher s1 = s2)

The cipher_char function cipher_char linearly with the size of the alphabet. To make it more compact and versatile, you can use a search table of some form, for example.

 (* Assume that only letters are needed *) let cipher_mapping = "CADB" let cipher_char c = try cipher_mapping.[Char.code c - Char.code 'A'] with Invalid_argument _ -> failwith "cipher_char"
+2
source

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 using tr. I.e.

  let comp c1 c2 x = try (c1 x) with _ -> (c2 x)
 let tr2 = comp tr (function | 'X' -> 'Y')
+5
source
  • How can I improve these solutions?

You abuse indentation, which makes the program more difficult to read. Eliminate unnecessary tabs and move the check to the outside 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 match if else?

It depends on the situation. If the pattern matching is superficial, as you demonstrate in the 2nd function ( match () with | () when len1 = len2 ), it brings no value compared to the simple if/else . If you match the pattern by values, this is better than if/else and potentially shorter when you use advanced constructs. For example, you can shorten a 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 the Or pattern for group patterns that have the same output and replace the unnecessary if/else block with && .

  • Am I designing rec or am I using rec correctly?
  • if this is correct (len1-1) right?

Your function looks beautiful. There is no better way than testing with multiple inputs at the top level of OCaml.

Zoom

The number of patterns is growing linearly with the size of the alphabet. This is a pretty nice IMO.

+3
source

More articles:


All Articles