再帰の処理を追うのがすこぶる苦手

OCamlのL99-27でピタッと止まる

しばらく記事の更新が遅れてしまってました。実はここのところOCamlのL99問題の答えを読みながら、それをCommon Lispで書いてみるということをずっとやっていました。

なぜこのようなやり方をしているのかと言いますと、そもそも私はOCamlにはまだ慣れていないし、Common Lispも初心者という状態です。しかし、年齢的にも生活的にも時間が限られている。したがって、少しばかり理解しているOCamlのコードを読むことでより一層OCamlに慣れ、さらにCommon Lispで書くことによって、Common Lispにも慣れていく、という方法を思いつきました。そもそもL99問題の解答は、プロの方がベストなものを提供してくれているわけですから、よい見本にもなるのではないか、と思います。

これはちょっとした過去の経験からで、中学の時分、卓球部だった頃、ワルドナーという伝説の選手の試合を観て「模倣」したところ、何か急に強くなったり、高校の時分、マイケル・ジョーダンのシュートフォームを「模倣」したところ、何か急にシュートが入るようになったり、ということがありました。もちろんそれまで必死に「自分なりに」努力しているのですが。

「模倣」することで、何かを掴む。そして何かを掴むと楽しくなる。楽しくなると、自然とより学ぶようになる。あくまでもこれは私の学習法。

このやり方は正しかったのか

結果的にこのやり方で、どちらの言語の「慣れ度」も少しずつ上がったように思います。特にCommon Lispの方では、ほぼ0に近かったものが、3くらいにはなったような気がします。

しかし、スポーツと同様、どうしても「模倣」できない場合があります。それが今回どん詰りとなったL99-27です。

OCamlのL99-27の解答は、ネストが深めで、再帰多め、という非常に私的にわかりにくい代物でした。

再帰がわかりにくい時、私は図を紙に書いて処理を追うのですが、今回も同様のやり方を行いました。が、それでも複雑で分かりにくい。もともと再帰で頭がチンチラポッポとなる私ですから余計にわかりにくい。

まずはOCamlの解答をご覧ください。


let group list sizes =
  let initial = List.map (fun size -> size, []) sizes in
  let prepend p list =
    let emit l acc = l :: acc in
    let rec aux emit acc = function
      | [] -> emit [] acc
      | (n, l) as hd :: tl ->
          let acc = if n > 0 then emit ((n - 1, p :: l) :: tl) acc else acc in
          inner_aux (fun l acc -> emit (hd :: l) acc) acc tl
    in
    aux emit [] list
  in
  let rec aux = function
    | [] -> [ initial ]
    | hd :: tl -> List.concat (List.map (prepend hd) (aux tl))
  in
  let all = aux list
  in
  let complete = List.filter (List.for_all (fun (x, _) -> x = 0)) all
  in
  List.map (List.map snd) complete
;;

難しい……。

そこで私、各パーツを分解することにしました。しかし……

分解方法が間違っていたのか、期待した結果には至らず……

完全に心が折れました。なぜこんなわかりにくいコードを書くのだ……(自分のOCamlの知識不足を棚に上げて憤る)

そんな時、HaskellのH-99というものを発見しました。コードは以下のようなもの。


combination :: Int -> [a] -> [([a], [a])]
combination 0 xs     = [([], xs)]
combination n []     = []
combination n (x:xs) = ts ++ ds
    where
        ts = [ (x:ys, xs) | (ys, zs) <- -="" 1="" ::="" combination="" ds="[" group="" n="" nt="" x:zs="" xs="" ys="" zs=""> [a] -> [[[a]]]
group [] _      = [[]]
group (n:ns) xs = [ g:gs | (g, rs) <- code="" combination="" group="" gs="" n="" ns="" rs="" xs="">

見やすい。これならいけるかも…


(defun combination (n l)
  (cond
    ((= n 0) (list (list '() l)))
    ((null l) '())
    (t
     (let ((ts (loop for (ys nil) in (combination (- n 1) (cdr l))
                     collect (list (cons (car l) ys) (cdr l))))
           (ds (loop for (ys zs) in (combination n (cdr l))
                     collect (list ys (cons (car l) zs)))))
       (append ts ds)))))

(defun group-hs (sizes l)
  (cond
    ((endp sizes) '(()))
    (t
     (loop for (g rs) in (combination (car sizes) l)
           collect (loop for gs in (group (cdr sizes) rs)
                         collect (cons g gs))))))

結果はH-99の結果と同じになりました。

今回学んだこと

OCamlの知識がまだまだ不足している。

Common Lispのコンスセルとリストをまだしっかり理解できていない。

Haskellの内包表記は意外と見やすい、と今のところ思っている。

もともとの性格上、壁はぶち抜くまで叩き続けてしまうが、すぐ横に扉があるかもしれないということを確認するゆとりを持つべきである。

追記(2020/06/06)

ようやくOCamlのL99−27の再帰の流れを掴むことができました。結果、無理やりながらなんとかCommon Lispで同じ結果を得ることができるコードを書くことができました。

再帰の流れを追うのに、結局コピー用紙数枚と鉛筆で愚直に書いて追うというやり方をしました。そして途中で気づいた(気づいてよかった)のですが、group ["a"] [1;0]という最小限の再帰で済む値の流れを追うことにしました。賢い方はおそらく最初からこうするのだろうな……(情けない)

実際のコードはGitHubに置いておきました。こちら

2020/05/28