CLOJURE for the BRAVE and TRUEでClojure学習 part3

はじめに

Clojure の学習備忘録。 今回は、Chapter 4: Core Functions in Depthの残り箇所。

今回のあつかうテーマは、以下の通り。

  • 遅延シーケンス
  • 無限シーケンス
  • コレクション関数(conj, into)
  • 代表的な高階関数(apply, partial, complement)

遅延シーケンスといっても、実際に要素にアクセスするまで全く計算しないではなく、 パフォーマンス上先行するいくつか要素も計算してしまうというのは面白い。

Lazy Seqs

mapは他のシーケンス関数と同様、引数のコレクションにseqを適用するだけではなく、遅延シーケンス を返す。
遅延シーケンスとは、要素に実際にアクセスするまで計算を行わないシーケンスのことである。 それに対してシーケンスの全要素が計算されているものは、リアライズシーケンスと呼ぶ。 必要になるタイミングまで計算を遅延させることは、より効率的なプログラミングを可能にし、無限シーケンスが構築できるようになる。

Demonstrating Lazy Seq Effciency

遅延シーケンスについて理解するために、次の例を考えよう。あなたはヴァンパイアを特定するタスクに参加しており、1 億人の容疑者の中からヴァンパイアを特定しないといけない。ヴァンパイアデータベースのサブセットはスタブ化して、次の通りである。

(def vampire-database
  {0 {:makes-blood-puns? false, :has-pulse? true  :name "McFishwich"}
    1 {:makes-blood-puns? false, :has-pulse? true  :name "McMackson"}
    2 {:makes-blood-puns? true,  :has-pulse? false :name "Damon Salvatore"}
    3 {:makes-blood-puns? true,  :has-pulse? true  :name "Mickey Mouse"}})

(defn vampire-related-details
  [social-security-number]
  (Thread/sleep 1000)
  (get vampire-database social-security-number))

(defn vampire?
  [record]
  (and (:makes-blood-puns? record)
        (not (:has-pulse? record))
        record))

(defn identify-vampire
  [social-security-numbers]
  (first (filter vampire?
                  (map vampire-related-details social-security-numbers))))

vampire-related-details は 1 秒でデータベースからレコードを見つける関数である。 vampire? はレコードがヴァンパイアかどうかを判定する関数。 identify-vampireマイナンバーとデータベースのレコードをマッピングして、はじめに一致したレコードを返す。

これらの関数の処理時間を計測するには、 time を使用すればよい。

(time (vampire-related-details 0))
; => "Elapsed time: 1001.373258 msecs"
; => {:makes-blood-puns? false, :has-pulse? true, :name "McFishwich"}

1 行目には、関数処理にかかった時間が出力される。
2 行目は、関数の戻り値である、データベースのレコードが出力される。

遅延が考慮されていない map ならば、全要素に対して vampire-related-details 関数を適用し、その後、 filter を適用することになる。1 億人の容疑者からヴァンパイアを見つけるならば、全要素なめるのに 1 億秒つまり 12 日必要となり、街の半分の人が死んでしまう。しかし Clojuremap は遅延を考慮されているので、そんな心配はいらない。

(time (def mapped-details (map vampire-related-details (range 0 1000000))))
; =>"Elapsed time: 0.053236 msecs"
; => #'user/mapped-details

この例では、 range によって 0 から 999,999 までの遅延シーケンスを生成し、 map が返す遅延シーケンスを mapped-details にバインドしている。しかし、 range が返すシーケンスの全要素に対して vampire-related-details はまだ適用されていないので、処理時間は 12 日もかからず、一瞬で終わる。

遅延シーケンスは、一つはシーケンスの要素をリアライズ方法が記述されたレシピと、今までリアライズされた要素の2つから構成される。 map を使用してもどの要素もまだリアライズされていないが、要素を生成するレシピはある。リアライズされていない要素にアクセスすれば、その度遅延シーケンスはレシピにあるとおり要素を料理して返すことになる。

上の例の場合、 map-detailsリアライズされていないが、map-details の要素にアクセスすれば、要素に対してレシピを適用することになり、検索時間に 1 秒かかるだろう。

(time (first mapped-details))
; => Elapsed time: 32070.326583 msecs"
; => {:makes-blood-puns? false, :has-pulse? true, :name "McFishwich"}

処理に 32 秒かかっている。1 億秒よりかはずっと速くなったが、期待しているよりも 31 秒も多くかかってしまっている。ひとつの要素にアクセスするだけなので 1 秒で済むはずなのになぜだろうか?

それは、Clojure が遅延シーケンスをチャンクに分割するからなのである。1 要素をリアライズするときに先行していくつかの要素もリアライズしている。例の場合だと、1 要素アクセスしても続く 31 要素もリアライズしたので 32 秒かかったのである。 これはパフォーマンス的な理由で行われている。

遅延シーケンスの要素の評価は、初回アクセスのときだけである。よって、もう一回 mapped-details のはじめの要素にアクセスしてもほとんど時間はかからない。

(time (first (mapped-details)))
; => "Elapsed time: 0.022 msecs"
; => {:name "McFishwich", :makes-blood-puns? false, :has-pulse? true}

遅延シーケンスについて整理できたので、はじめに書いたコードが時間かからないことも理解できるだろう

(time (identify-vampire (range 0 1000000)))
; => "Elapsed time: 32019.912 msecs"
; => {:name "Damon Salvatore", :makes-blood-puns? true, :has-pulse? false}

Infinite Sequences

遅延シーケンスの特徴を利用して、無限シーケンスも作成できる。今までシーケンスは有限であったが、Clojure では無限シーケンスを作成できる関数を用意されてる。 repeat はその一つであり、渡された引数の値からなる無限シーケンスを構築する

(concat (take 8 (repeat "na")) ["Batman!"])
; => ("na" "na" "na" "na" "na" "na" "na" "na" "Batman!")

ここでは、文字列 "na" を要素にもつ無限シーケンスを構築している。

repeatedly をつかえば、もっと柔軟な無限シーケンスを構築できる

(take 3 (repeatedly (fn [] (rand-int 10))))
; => (1 4 0)

repeatedly でできた無限シーケンスの要素は、匿名関数 (fn [] (rand-int 10)) の適用結果になる。REPL を実行するたびに、取得要素はランダムに変化する。

遅延シーケンスをリアライズする first や take といった関数は、シーケンスの次の要素がなんであるかを知らないし、取得した要素の次があるならば、ただそれを取得するだけである。

(defn even-numbers
  ([] (even-numbers 0))
  ([n] (cons n (lazy-seq (even-numbers (+ n 2))))))

(take 10 (even-numbers))
; => (0 2 4 6 8 10 12 14 16 18)

ここでは、再帰を利用した無限シーケンスを作成してる。cons は第一引数の要素と第二引数のリストから新たなリストを作成している。

(cons 0 '(2 4 6))
; => (0 2 4 6)

even-numbers では、今の要素と次の要素の計算手順が記された遅延シーケンスをコンス操作の引数に渡すことで 無限シーケンスを構成している。

The Collection Abstraction

シーケンスの抽象化は、構成要素各々に対するオペレーションに関するものに対して、コレクションの抽象化は、データ構造全体に関するものになる。たとえば、 count, empty?, every? とった関数は、個々の要素ではなく、その全体を対する操作になる。

(empty? [])
; => true

(empty? ["no"])
: => false

ここでは代表的で、よくごっちゃになりがちな関数 into, conj をとりあげる。

into

今までみたきたように、シーケンス関数の戻り値はオリジナルのデータ構造ではなく、seq である。それをオリジナルなデータ構造に変換したいとき into がつかえる。

(map identity {:sunlight-reaction "Glitter!"})
; => ([:sunlight-reaction "Glitter!"])

(into {} (map identity {:sunlight-reaction "Glitter!"}))
; => {:sunlight-reaction "Glitter!"}

map 関数は hashmap を seq に変換するが、 into で hashmap に変換し直している。hashmap 以外のデータ構造にも変換できる。

ベクタに変換する

(map identity [:garlic :sesame-oil :fried-eggs])
; => (:garlic :sesame-oil :fried-eggs)

(into [] (map identity [:garlic :sesame-oil :fried-eggs]))
; => [:garlic :sesame-oil :fried-eggs]

セットに変換する

(map identity [:garlic-clove :garlic-clove])
; => (:garlic-clove :garlic-clove)

(into #{} (map identity [:garlic-clove :garlic-clove]))
; => #{:garlic-clove}

into の第一引数が空である必要はない。空ではないと、追記させることができる。

(into {:favorite-emotion "gloomy"} [[:sunlight-reaction "Glitter!"]])
; => {:favorite-emotion "gloomy" :sunlight-reaction "Glitter!"}

(into ["cherry"] '("pine" "spruce"))
; => ["cherry" "pine" "spruce"]

conj

conj 関数もコレクションに要素を追加するが、into と少し異なる。

(conj [0] [1])
; => [0 [1]]

[1] のまま追加されてしまう。

(into [0] [1])
; => [0 1]

一方 into の場合、 1 で追加される conj で同じ結果を得たい場合は、次の通り。

(conj [0] 1)
; => [0 1]

conjスカラー値で受け取るのに対して、 into はコレクションを引数にとるという違いがある。

Function Functions

関数を引数にとったり、戻り値として返す代表的な高階関数として、 apply, partial をとりあげる。

apply

apply は、引数に関数とシーケンスをうけとり、シーケンスを関数の引数として適用するたとえば、 受け取った引数で最大の値を返す max 関数で考えてみる。

(max 0 1 2)

しかし、引数にベクタを受け取った場合、期待どおりにいかない。

(max [0 1 2])
; => [0 1 2]

max に渡すときは、ベクタとしてまとめて渡してはいけず、比較したい値をそれぞれ引数としてわたさないといけない。そして、ベクタとして渡しても動作させるには、 apply が使える。

(apply max [0 1 2])

partial

partial は引数に、一個の関数(f)と 0 個以上の引数(arg)をとり、新しい関数を返す。partial が返す関数を引数(new arg)つきで呼び出すと、partial に渡した f に arg と new arg を渡して適用される。

(def add10 (partial + 10))
(add10 3)
; => 13
(add10 5)
; => 15

(def add-missing-elements
  (partial conj ["water" "earth" "air"]))

(add-missing-elements "unobtainium" "adamantium")
; => ["water" "earth" "air" "unobtainium" "adamantium"]

add10 を呼び出すと、 (+ 10) に与えられた引数を追加して (+ 10 3) が実行される。(+ 10) のように+関数の第一引数を 10 で固定させた関数を作るのが、 partial である。

コンテキストは異なるが関数とその引数の組み合わせが同じものを繰り返し使用するとき、partial は効果的である。

(defn lousy-logger
  [log-level message]
  (condp = log-level
    :warn (clojure.string/lower-case message)
    :emergency (clojure.string/upper-case message)))

(def warn (partial lousy-logger :warn))

(warn "Red light ahead")
; => "red light ahead"

(warn "Red light ahead") を呼び出すことは、 (lousy-logger :warn "Red light ahead") を呼び出すことと同じである。

complement

前節で、1 億人からヴァンパイアを特定する identify-vampire 関数を作成したが、逆に人間を特定するにはどうすればよいだろうか?

(defn identify-humans
  [social-security-numbers]
  (filter #((not (vampire? %)))
          (map vampire-related-details social-security-numbers)))

filter 関数の第一引数は、 #(not (vampire? %)) となっているが、 この述語関数の戻り値を反転させるのが、 complement 関数である。

(defn not-vampire? (complement vampire?))
(defn identify-humans
  [social-security-numbers]
  (filter not-vampire?
          (map vampire-related-details social-security-numbers)))