それ sequence-m でできるよ
はじめに
clojure.algo.monadsを使ってみました。
お題
例えば”Hail2U”という文字列を元にして、
["hail2u","hail2U","haiL2u","haiL2U","haIl2u","haIl2U","haIL2u","haIL2U"
それリストモナドでできるよ - 毎日少しずつHaskellを勉強する
,"hAil2u","hAil2U","hAiL2u","hAiL2U","hAIl2u","hAIl2U","hAIL2u","hAIL2U"
,"Hail2u","Hail2U","HaiL2u","HaiL2U","HaIl2u","HaIl2U","HaIL2u","HaIL2U"
,"HAil2u","HAil2U","HAiL2u","HAiL2U","HAIl2u","HAIl2U","HAIL2u","HAIL2U"]
を吐き出す。
それ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で１要素のセットにしています。これで事前に重複となる"芽"を摘んでしまうわけです。
それ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は他とアルゴリズムが異なっていますのであくまでも参考値と思ってください。
