2020/08/11

ようやくL99問題が残り1/3になった

意外な効果

「OCamlのL99問題をCommon Lispで書いてみる」ことで、OCamlとCommon Lispを同時に勉強するという無謀な方法をしばらく地道に続けている私ですが、素人発想ながら、意外と効果があるのではないかと最近思っています。

まずOCamlのコードを以前より読みやすく感じるようになりました。OCamlのコードは再帰が多めなので、再帰の苦手な私にとってはなかなか読みにくいものでした。しかし、ここ最近慣れたのか、以前より苦手意識がなくなり、コードを追うことができるようになりました。もちろん複雑なものはまだまだ時間がかかりますが。

そしてCommon Lispのほうでは使えるようになったものが徐々に増えてきています。書く際も以前よりスピードが上がりました。

あと1/3なので、何とかコンプリートできるように頑張ろうかと思います。

L99-68

現在L99-68まで終わりました。68問目では二分木の探索についての前順と中順の知識が必要でした。

私はこのあたりの知識がなかったので、とりあえず前順・中順・後順について調べました。

再帰の処理を追う時と同様、ここでも最小構成で考えると分かりやすかったです。

まず前順または行きがけ順、preorderと呼ばれている探索方法では、根を調べてからそこについている部分木を調べます。例えば以下のような二分木がある場合


   A
 ／ ＼
B     C

まず根であるA、次にB、Cという順で探索します。A-B-C

次に中順、または通りがけ順、inorderと呼ばれている探索方法では、片方の部分木->根->もう片方の部分木という順で調べます。上記の二分木でやってみると、まずB、次に根であるA、最後にCとなります。B-A-C

最後に後順、または帰りがけ順、postorderと呼ばれている探索方法では、部分木を調べてから根を調べる。上記の二分木でやってみると、まずB、次にC、最後に根であるAという順になります。B-C-A

この最小構成で理解できると、より複雑なものでも順序を追うことができました。

L99-69

OCamlのL99-69は現在解答例が無い状態なので、Common Lispで書いたものが正しく動いているのか照らし合わせることができないのですが、文章を読んだ所、要は文字列ab.c...がNode(a Node(b Empty Node(c Empty Empty)) Empty)のようになればよいのかなと思い、そうなるようにコードを書いてみました。コードは以下のようになりました。


;; L-69 Dotstring representation of binary trees.
(defun dotstring-of-tree (tree)
  (cond
    ((typep tree 'empty*) ".")
    ((typep tree 'node*)
     (let ((data (princ-to-string (node*-val tree))))
       (cond
         ((and (typep (node*-l tree) 'empty*)
               (typep (node*-r tree) 'empty*))
          (concatenate 'string data "." "."))
         (t
           (concatenate 'string
                        data
                        (dotstring-of-tree (node*-l tree))
                        (dotstring-of-tree (node*-r tree)))))))))

(defun tree-of-dotstring (str)
  "e.g.) * tree-of-dotstring \"ab..c..\" "
  (labels ((make (ofs s)
             (if (or (>= ofs (length s)) 
                     (char= (schar s ofs) #\.))
               (list (empty) (+ ofs 1))
               (let ((v (schar s ofs)))
                 (if (< (+ ofs 1) (length s))
                   (let* ((tmp1 (make (+ ofs 1) s))
                          (l (car tmp1))
                          (ofs1 (cadr tmp1))
                          (tmp2 (make ofs1 s))
                          (r (car tmp2)))
                     (list (node v l r) (+ ofs1 1)))
                   (if (char= v #\.)
                     (list (empty) (+ ofs 1))
                     (list (node v (empty) (empty)) (+ ofs 1))))))))
    (car (make 0 str))))

一応自分で確認したところ、うまくいっているように思います。もし間違いなどお気づきの方がいらっしゃいましたら気軽にご指摘ください。

追記(2020/08/12)

OCamlのL99ではdotstring_of_treeとtree_of_dotstringがなかったので、tree_of_stringとstring_of_treeを改造して書いてみました。動作は確認済みです。


let tree_of_dotstring =
  let rec make ofs s =
    if ofs >= String.length s || s.[ofs] = '.' then
      Empty, ofs
    else
      let v = s.[ofs] in
      if ofs + 1 < String.length s then
        let l, ofs = make (ofs + 1) s in
        let r, ofs= make (ofs + 1) s in
        Node(v, l, r), ofs
      else
        if s.[ofs] = '.' then Empty, ofs
        else Node(v, Empty, Empty), ofs + 1 in
  fun s -> fst(make 0 s)
;;

let rec dotstring_of_tree = function
  | Empty -> "."
  | Node(data, l, r) ->
      let data = String.make 1 data in
      match l, r with
      | Empty, Empty -> data ^ "." ^ "."
      | _, _ -> data ^ (dotstring_of_tree l) ^ (dotstring_of_tree r)
;;
author: date:
Label: ,