Code Aquarium

minazoko's blog -*- 水底のブログ -*-

それ sequence-m でできるよ

はじめに

clojure.algo.monadsを使ってみました。

お題

例えば”Hail2U”という文字列を元にして、

["hail2u","hail2U","haiL2u","haiL2U","haIl2u","haIl2U","haIL2u","haIL2U"
,"hAil2u","hAil2U","hAiL2u","hAiL2U","hAIl2u","hAIl2U","hAIL2u","hAIL2U"
,"Hail2u","Hail2U","HaiL2u","HaiL2U","HaIl2u","HaIl2U","HaIL2u","HaIL2U"
,"HAil2u","HAil2U","HAiL2u","HAiL2U","HAIl2u","HAIl2U","HAIL2u","HAIL2U"]
を吐き出す。

それリストモナドでできるよ - 毎日少しずつHaskellを勉強する

それset-mでできるよ

ただし順序不定、結果はリスト(Cons)のセット。

(use 'clojure.algo.monads)
(require '[clojure.string :as s])

(with-monad set-m
  (m-map (juxt s/upper-case s/lower-case), "Hail2U"))

;;=> #{("h" "A" "i" "L" "2" "U") ("h" "a" "i" "L" "2" "U") ("h" "A" "I" "L" "2" "U") ("h" "A" "i" "l" "2" "U") ... }

clojure.algo.monads では、with-monad で式を囲むことでモナドのコンテキストを決定します。with-monad の第一引数、この場合 set-m が対象のモナドになります。
with-monadの第一引数、set-mのコンテキストになります。*1
set-mはHaskell等でいうところのリストモナドのような非決定性計算(多重ループ処理)を行うモナドです。ただし計算結果はsetコレクションになります。つまり自動的に重複が取り除かれます。

m-map は Haskell の mapM にあたります。

短く簡潔に書くことを主眼においたコードですが、結果がsetコレクション(lazy sequenceじゃない)だし、文字列の列挙にもなっていないところはいまいちです。

それsequence-mでもできるよ

useとrequireは同じなので省略します。

(with-monad sequence-m
  (->> "Hail2U"
       (m-map #(sorted-set (s/upper-case %) (s/lower-case %)))
       (map s/join)))

;;=> ("HAIL2U" "HAIL2u" "HAIl2U" "HAIl2u" "HAiL2U" "HAiL2u" "HAil2U" ...)

結果は文字列を要素とするlazy sequence。並びは辞書順です。

Haskellのリストモナドに対応するのがこのsequence-mです。vectorでも文字列でもsetでもなんでもシーケンスになってしまうのがClojureの仕様ですので、文字列で返すためには最後に変換(join)してやらなけばなりません。

set-mでは全組み合わせを作ってから重複を除去する仕組みでしたが、今回は最初から重複しないように作っています。upper-caseとlower-caseで大小文字のペアを作り、どちらも同じ文字ならばsorted-setで1要素のセットにしています。これで事前に重複となる"芽"を摘んでしまうわけです。

それcertesian-productでもできるよ

おまけ。モナドじゃありません。
clojure.math.combinatorics の certesian-productを使った例。

(require '[clojure.string :as s]
         '[clojure.math.combinatorics :as c])

(->> "Hail2U"
     (map #(sorted-set (s/upper-case %) (s/lower-case %)))
     (apply c/cartesian-product)
     (map s/join))

結果はsequence-mの時と同じなので省略します。

パフォーマンス

seedに20文字の文字列を与えて、timeマクロで大雑把に計測。単位はミリ秒。

set-m 1673
sequence-m 648
cartesian-product 940

今回のケースでは、差は大きくはありませんが、sequence-mが最も高パフォーマンスでした。
set-mは他とアルゴリズムが異なっていますのであくまでも参考値と思ってください。

おわりに

今まであまり使ったことのなかった clojureモナドライブラリ algo.monadsを試してみました。静的型付関数型言語モナドとは実装も思想も異なっていますが、それなりにモナディックなエッセンスをコードに取り入れる役には立ちそうだと思いました。
もう少し調べてみたい。

*1:「対象」という単語は圏論の用語なので、ここでの使用は避けました。