最長重複文字列問題 in Clojure
Clojure を学ぶ
Groovy と Scala は Java の文化圏から生まれたものだが、Clojure は Lisp の文化圏から Java に入ってきたものだ。
関数の呼び出しが (関数名 引数1 引数2 ...) と前置記法で書いたリストであるところは Lisp だが、他の Lisp 系言語に比べると Groovy よりである。
今回は関数プログラミングのスタイルなので無名関数の書き方から Groovy と比較してみる
無名関数の書き方
Groovy | Clojure |
---|---|
{ x -> 2 * x } | (fn [x] (* 2 x)) |
{ x -> 2 * x } | #(* 2 %) |
{ 2 * it } | #(* 2 %) |
{ x, y -> x + y } | (fn [x y] (+ x y)) |
{ x, y -> x + y } | #(+ %1 %2) |
{ it[0] + it[1] } | #(+ (first %) (second %)) |
- 引数が1つならその引数
- 引数が複数なら引数リスト
Clojure の暗黙のパラメータ % は最初の引数を表わす。
- % と %1 は同じ意味
リストとベクタ
Groovy | Clojure |
---|---|
new ArrayList(){{ add(1);add(2);add(3) }} | (list 1 2 3) |
[1,2,3] | (quote (1 2 3)) |
[1,2,3] | '(1 2 3) |
[1,2,3] | '(1,2,3) |
[1,2,3] | [1 2 3] |
[1,2,3] | [1,2,3] |
ベクタの特典
さらにうれしいことにベクタにはもれなく特典がついてくる。
Groovy | Clojure |
---|---|
[1,2,3][0] | ([1,2,3] 0) |
無名関数の呼び出しと apply
Groovy | Clojure |
---|---|
{ x, y -> x + y }(1,2) | (#(+ %1 %2) 1 2) |
{ it[0] + it[1] }([1,2]) | (#(+ (first %) (second %)) [1,2]) |
{ it[0] + it[1] }([1,2]) | (#(+ (% 0) (% 1)) [1,2]) |
{ x, y -> x + y }(*[1,2]) | (apply #(+ %1 %2) [1,2]) |
{ x, y -> x + y }([1,2]) | (apply #(+ %1 %2) [1,2]) |
前置記法のメリット
assert [6,6,6].collect{ it + 1 } == [7,7,7] assert [[1,2,3],[6,5,4]].transpose().collect{ it[0] + it[1] } == [7,7,7]
Groovy の場合は、1つのリストと複数のリストで処理が変わる。
;; いくつでもリストを渡せる (map #(+ % 1) [6,6,6]) ;=> (7 7 7) (map #(+ %1 %2) [1,2,3] [6,5,4]) ;=> (7 7 7) ;; 関数呼び出しの形が決まっているので関数だけ渡せばよい (map inc [6,6,6]) ;=> (7 7 7) (map + [1,2,3] [6,5,4]) ;=> (7 7 7)
部分適用
def incinc = { x, y -> x + y }.curry(2) assert [5,5,5].collect(incinc) == [7,7,7] assert [5,5,5].collect(2.&plus) == [7,7,7] // メソッドクロージャ
関数だけ必要な場合が多いので Groovy より部分適用が役に立つ。
(map (partial + 2) [5,5,5]) ;=> (7 7 7)
左から右演算子
Lisp の場合、前置記法はいいのだが入れ子になるのが問題なのだ。
しかし、Clojure では (->> 引数1 関数1 関数2 ...) と書くと (関数1 引数1) を実行した結果を関数2に...という風につなげられる。
これはほとんど obj.method1.method2 という意味なので Groovy に近い。
実際に文字を連結する。バックスラッシュで始まるのが文字リテラル。Groovy には文字リテラルはないが...
;; 文字 \a を文字列にする (str \a) ;=> "a" ;; 左から順に処理を行う (->> \a str) ;=> "a" ;; あらかじめ括弧があってもよい (->> \a (str)) ;=> "a" ;; ->> は引数の最後に追加する (->> \a (str \b)) ;=> "ba" ;; -> は引数の先頭に追加する (-> \a (str \b)) ;=> "ab" ;; 関数は複数並べておくことができる (-> \a (str \b) (str \c)) ;=> "abc" ;; これより読みやすい (#(str (str % \b) \c) \a) ;=> "abc"
その他
真偽値で偽になるのは false, nil だけということは覚えておかないといけない。
個々の関数は調べるしかない。
Clojure は Scala と比べるとそれほど関数が多くなくドキュメントも調べやすい。
Other version には jQuery を使ったリッチなものや PDF もある。
実装してみる
(defn tails [xs] (take (inc (count xs)) (iterate rest xs))) (defn seq-asc [xs ys] (if-let [non-zero (some #(when (not= 0 %) %) (map compare xs ys))] non-zero (compare (count xs) (count ys)))) (defn make-pair [xs] (partition 2 1 xs)) (defn comlen [xs ys] (count (take-while #(apply = %) (map vector xs ys)))) (defn lenstr [xs ys] (vector (comlen xs ys) xs)) (defn calc-len [xs] (map #(apply lenstr %) xs)) (defn choose-max [xs] (when (not-empty xs) (apply max-key first xs))) (defn extract [xs] (when (not-empty xs) (apply #(take %1 %2) xs))) (def max-dup-str (comp extract choose-max calc-len make-pair (partial sort seq-asc) tails)) (assert (= "issi" (->> "mississippi" seq max-dup-str (apply str)))) (assert (= (max-dup-str [8,10,8,10,12,8,10,8,10,12,8]) [8,10,8,10,12,8]))
takeWhile 待ちの間に何回か修正して今はこうなっている。
if-let は Groovy の ?: 演算子に近いかと思う。
Clojure でも文字列をリストのように扱うことはできない。
文字列を渡せるようにする
(defmulti max-dup-str class) (defmethod max-dup-str :default [xs] (->> xs tails (sort seq-asc) make-pair calc-len choose-max extract)) (defmethod max-dup-str String [xs] (->> xs seq max-dup-str (apply str))) (assert (= (max-dup-str "mississippi") "issi")) (assert (= (max-dup-str "a") "")) ; (assert (= (max-dup-str "") nil)) AssertionError (assert (= (max-dup-str [8,10,8,10,12,8,10,8,10,12,8]) [8,10,8,10,12,8]))
defmulti と defmethod を使えば引数の型で分岐できる。
class 関数を指定しているので型で分岐しているだけであって他の関数を使えば型以外でも処理を分けられるらしい。
納得いかないのは str の引数が nil でも引数なしでも空文字を返してくる。
そこで調べてみたら Groovy の ?. のようなものがあったのでこれを使ってみた。
(use '[clojure.contrib.core :only (-?>>)]) (defmethod max-dup-str String [xs] (-?>> xs seq max-dup-str (apply str))) (assert (= (max-dup-str "") nil))
nil を回避している理由が若干違うような気がする
ただ contrib ライブラリを使っているのでおまけ。? は Groovy 由来だと思うので書いてみた。