Programmer's Note

コード読み書きの備忘録。

続：Haskell/Clojureでrepeated_combinationを実装してみる

Haskell Clojure

http://hifistar.hatenablog.com/entry/2018/03/24/131654:repeat_combinationを実装してみるの続き。

この前書いたコードは結構無駄が多くて、実はもっとぜんぜん簡潔にコードが書けた。 ここまで簡潔なコードにブラッシュアップできたのは、Haskellのおかげだなと。

Clojureだけの場合は、ある程度で満足して、先に思考を進めることはあまりしなかった。 Haskellでコードを書くと、違う視点でものごとを考えることができる、というのが大きい。

Haskellは、文字通り「型にはまる」とコードがものすごくシンプルになる、と実感する。 関数のInput/Outputの型（データの抽象度のレベル感）を揃えることが、が非常に大事だと学んだ。

これはプログラミングの基本中の基本かもしれないが、なかなか意識しても難しい。 Haskellの場合は強制的にそれをさせる、という意味でかなり良い。

Clojureの場合は、そろってなくてもプログラムが組める。自由度が高い。 ifなどの条件文で動的に型をチェックして、処理を振り分けてしまえる。 これはもろ刃の剣で、素早くコードを組んだり変更したりするには向いているが、かなり意識しないとプログラムの構造がmessyになる。

双方をやることでいろいろ気づきが出てきて、「結局こういうことじゃね？」という風に理解が深まる。 短いコードで表現できるアルゴリズム系の勉強に、結構いいんじゃなかろうかと思った。

さて、あらためてrepeat_combinationの実行例：

*Main> repeat_combination [1,2,3] 2
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
*Main> repeat_combination [1,2,3] 3
[[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]]
幅優先で組み合わせする場合

結局こういうことだ。（「幅優先」という表現が合っているか微妙だが）

Haskell
repeat_combination :: [Int] -> Int -> [[Int]]
repeat_combination xs 0 = [[]]
repeat_combination xs n = [ x : y | x <- xs, y <- repeat_combination xs (n-1)]
Clojure
(defn repeat-combination [xs n]
  (if (= n 0)
    [[]]
    (for [x xs
          y (repeat-combination xs (dec n))]
       (cons x y))))

上記は、組み合わせた結果の帰り値に対して、さらに組み合わせを計算する。

末尾最適化可能なやり方

同じ幅優先だが、こちらは引数に結果を渡すやり方で、これだと末尾最適化できる。

Haskell
combination :: [Int] -> [[Int]] -> Int -> [[Int]]
combination xs ys 0 = ys
combination xs ys n = combination xs [ x : y | x <- xs, y <- ys ] (n-1)

repeat_combination :: [Int] -> Int -> [[Int]]
repeat_combination xs n = combination xs [[]] n
Clojure
(defn combination [xs ys n]
  (if (= n 0)
    ys
    (recur xs
           (for [x xs, y ys] (cons x y))
           (dec n))))

(defn repeat-combination [xs n]
  (combination xs [[]] n))
深さ優先で組み合わせる場合

これも引数に結果を渡して繰り返すやり方。

Haskell
combination xs ys 0 = [ys]
combination xs ys n = concat [combination xs (ys++[x]) (n-1) | x <- xs]

repeat_combination :: [Int] -> Int -> [[Int]]
repeat_combination xs n = combination xs [] n
Clojure
(defn combination [xs ys n]
  (if (= n 0)
    [ys]
    (apply concat
           (for [x xs] (combination xs (conj ys x) (dec n))))))

(defn repeat-combination [xs n]
  (combination xs [] n))

concatが美しさを損ねているが、まあしょうがない・・・。

ひとつ選ぶとしたら、分かりやすさと簡潔さ、プラスStack Overflowにならないので、２番目のやり方かなあ。