最長重複文字列問題 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 %))

Groovy ではパラメータを明示する場合としない場合で -> しか違いがないが、Clojure では fn か # の違いがある。 Groovy の暗黙のパラメータ it は引数全体を表わす。

• 引数が1つならその引数
• 引数が複数なら引数リスト

Clojure の暗黙のパラメータ % は最初の引数を表わす。

• % と %1 は同じ意味

Clojure の # の記述では入れ子にできない。

リストとベクタ

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]

Clojure のリストは2種類あって丸括弧をリストとよび角括弧をベクタと呼ぶ。 丸括弧はプログラムを書くときに使って、角括弧はデータを表わすときに使う。 角括弧の場合、先頭は関数でなくても構わない。 空白区切りの変わりにカンマ区切りでも構わないので Groovy とまったく同じ記法で書ける。

ベクタの特典

さらにうれしいことにベクタにはもれなく特典がついてくる。

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])

Clojure の apply 関数は Groovy の展開演算子のようなものだ。 しかし、注目すべき点は Groovy の下2つの書き方だ。展開してもしなくても違いがない。 Groovy のクロージャは自分のパラメータ数をみて展開するか展開しないか判断しているのだ。 これは高階関数を使う際に展開演算子を記述するタイミングがないのでこうなっている。 ちなみに Scala ではクロージャ側でパターンマッチできるので展開していない。

前置記法のメリット

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)

Clojure の場合は演算子も関数なので + 演算子が sum 関数のような働きをする。

部分適用

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 と比べるとそれほど関数が多くなくドキュメントも調べやすい。

• Clojure - Cheatsheet

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 由来だと思うので書いてみた。