4

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

有一个这样的练习：

练习 4.3 假设我们有一个基于以下替换密码的密码系统，其中每个明文都根据下表进行加密。

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

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

编写一个函数check，给定一个明文字符串s 1和一个密文字符串s 2，true当且仅当s 2是s 1的密文时返回。如果s 1不是纯文本字符串，您的函数应该引发异常。您可能希望参考第 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 并查看它是否是地图中的值。

对此有何建议？

4

3 回答 3

5

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

让 tr = 函数
  | 'A' -> 'C'
  | 'B' -> 'A'
  | 'C' -> 'D'
  | 'D' -> 'B'
  | _ -> failwith "不是明文"

让检查 ~tr s1 s2 = (String.map tr s1) = s2

检查〜tr“坏”“ACD”

您可以通过使用 tr 组合来添加更多字母。IE

let comp c1 c2 x = try (c1 x) with _ -> (c2 x)
让 tr2 = comp tr (函数 | 'X' -> 'Y')
于 2013-01-15T18:02:43.590 回答
3
  • 我该如何改进这些解决方案？

您滥用缩进使程序更难阅读。消除不必要的选项卡并移至check外部范围以提高可读性：

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
  • 如果其他，我应该更喜欢匹配吗？

这取决于情况。如果您在第二个函数 ( ) 中演示的模式匹配是肤浅的，那么与简单的构造相比，match () with | () when len1 = len2它没有任何价值。如果您对值进行模式匹配，那么当您使用高级构造时if/else，它会比并且可能更短。if/else例如，您可以通过匹配元组来缩短函数：

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)

在这里，我们还使用 Or 模式对具有相同输出操作的模式进行分组，并将不必要的if/else块替换为&&。

  • 我是在设计记录还是正确使用记录？
  • 如果检查（len1-1）正确吗？

你的功能看起来不错。没有比在 OCaml 顶层测试一些输入更好的方法了。

缩放它

模式的数量随着字母的大小线性增长。这是相当不错的国际海事组织。

于 2013-01-15T17:59:43.943 回答
2

最简单的解决方案似乎只是加密文本并比较结果：

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)

该cipher_char函数随字母表的大小线性缩放。为了使它更紧凑和通用，您可以使用某种形式的查找表，例如

(* 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"
于 2013-01-15T18:21:40.070 回答