如何在Ocaml中编写模式匹配以便于扩展？

Question

我正在学习Jason Hickey的Objective Caml简介.

有这样的练习:

练习4.3假设我们有一个基于以下替换密码的加密系统,其中每个普通字母都根据下表加密.

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

例如,字符串BAD将被加密为ACB.

编写一个函数check,给定一个明文字符串s ₁和一个密文字符串s ₂,true当且仅当s ₂是s ₁的密文时才返回.如果s ₁不是明文字符串,则您的函数应引发异常.您可能希望参考第8页的字符串操作.当字母表变大时,您的代码如何缩放？[强调补充]

---

基本上,我用might-be-stupid-naive这个练习的方法编写了两个函数.

我想首先就我的解决方案征求意见.

然后,我想询问练习中突出显示的缩放解决方案的提示.

---

使用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

到处使用纯匹配

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

好.以上两种解决方案类似.

我制作了这两个,因为在这里http://www.quora.com/OCaml/What-is-the-syntax-for-nested-IF-statements-in-OCaml,有些人说这if else不是首选.

这基本上是not-that-simple我一生中第一次写一个函数.所以我真的很想在这里提出建议.

例如,

• 我该如何改进这些解决方案？
• 我宁愿match过if else？
• 我正在设计rec或use the rec正确吗？
• 如果那是in check (len1-1)正确的？

---

缩放它

练习要求How does your code scale as the alphabet gets larger?.我现在真的没有线索.在Java中,我会说我会有一个map,然后对于每个char s1,我正在寻找s2相应的char并查看它是否是地图中的值.

有什么建议吗？

Answer 1

这是一个简单的解决方案:

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"

你可以通过与tr合成来添加更多的字母.即

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