🔥虚無との戦い

📝Clojure Collections and Sequences

22 min read

Overview

Clojureの世界では全ての集合型データはシーケンス.

Clojureのシーケンスや高階関数を巧みに扱うことができるとモテるとか. こういうのは知っているか知らないかなのでイディオムを覚えてモテよう(📝Clojure Idioms).

Clojure: Collections

ClojureのCollectionはimmutableでpersistent.

Clojure is immutable and persistent

最も核となる3つの関数

  • first
  • rest
  • cons

Clojure Collection操作

よく使うものを列挙.

  • conj: コレクションの結合. 他の言語ではpush, concat, appendとか.

📝Clojure シーケンス(clojure.core.sequence)

refs: Clojure - Clojureを学ぼう - シーケンシャルなコレクション

シーケンス型 には4種類の重要なデータ構造がある.

  • list: ()
  • vector: []
  • map: {}
  • set: #{}

🔖List

Clojure: into

into は第一引数のコレクションに, 第二引数のシーケンスの要素全てを, 元のコレクションにとって自然な形で追加 (conj) してくれる関数.

(into %1 %2) は,

(reduce conj %1 %2) つまり %1 に %2 の要素を順に conj したものと同等.

(conj (conj %1 %2の最初の要素) %2の二番目の要素)と同等.

💡Clojure contains?の罠

この値がリストに含まれるかどうかを判定するとき, Clojureのcontains?がつかえないので紛らわしいという話題.

contains? - clojure.core

これはMapにkeyが含まれるかを判定する関数でリストに対してつかっても期待通りの結果にならない…

この場合, someだったりJavaの.contains methodをつかう.

(defn in?
  "true if coll contains elm"
  [coll elm]
  (some #(= elm %) coll))
 
(.contains [100 101 102] 101)

ref. data structures - Test whether a list contains a specific value in Clojure - Stack Overflow

文字列はこっち. 文字列を含むか？: clojure.core/includes?

Clojure: スタック/キュー(stack/queue, FIFO/LIFO)

Clojure.lang.PersistentQueueという隠し機能かあるらしい.

Clojure.lang.PersistentQueue/EMPTYが空キューを示す.

conj/pop/peekで操作. 閲覧はseqで変換する.

swap-vals!とキューでのpop

Clojure 1.9で追加されたswap-vals!をつかうのもよい.

(defn push! [a v] swap! a (conj v))
(defn pop! [a] (-> a
                 (swap-vals! pop)
                 first
                 peek))
 
(def queue (atom clojure.lang.PersistentQueue/EMPTY))
(def stack (atom []))

有限サイズキュー

有限のキューなら以下の実装でいける.

(defn push [v i n]
  (if (>= (count v) n) (conj (subvec v 1 n) i) (conj v i) ))

ref. queue - Fixed length stack structure in Clojure - Stack Overflow

ring-bufferライブラリもある.

💡大きなサイズのvectorはlastよりpeek

大きなサイズのvectorはlastよりpeekが推奨されている. lastもpeekもどちらも末尾の要素を取り出す.

;; Prefer clojure.core/peek over `last` for potentially large vectors.

ref. https://clojuredocs.org/clojure.core/last

💡listのマージ

listに対してmergeをすると期待通りにならない罠がある.

(merge '(1 2 3) '(4 5 6))
;; => ((4 5 6) 1 2 3)

この場合, concat を利用する. 戻り値はLazu Seqになることに注意(input がvectorでもseq).

concatはLazySeqを返すものの, 結合の途中で中身を評価することに注意. とくに遅延シーケンスを評価せずに結合したいときはlazy-catをつかうこと.

💡listの空初期化

()をそのまま書くと評価されてしまうため, quote(’ シングルクオテーション)を()の前につける.

すなわち, `() である.

💡consとconjの違い

conjはリストに使う場合とベクタに使う場合で挿入が前後異なる.

それは効率性を考慮した設計らしい. conjは効率的に挿入するためにリストならば前へ, ベクタなら後ろへ追加する.

Clojure: Map(clojure.core.map)

📝連想配列(Associative Map)としてのMap(!= Clojure: map(function)).

Syntax

  • assoc: (key, value)の追加
  • dissoc: (key, value)の削除
  • update: (key)の指す(value)に引数で与えられた関数を適用して置き換える.
  • merge: (key, value)の集合の追加

assocは値を更新してMapを返す. updateは値に関数を適用してMapに束縛する.

Mapのmerge

もしmergeする際に左と右に同じkeyがある場合は, 後ろ側のvalue(latter)が優先される(上書きマージ).

ref. https://clojuredocs.org/clojure.core/merge

Clojure: シーケンスライブラリ(map/filter/reduce)

Clojureにおけるデータ操作高階関数(map/filter/reduce)他のまとめ.

基本的には4つに分類できる(ref. 💡プログラミングClojureより高階関数４分類).

有限のコレクションに対してはリスト内包表記もある(ref. 💡Clojureの繰り返し: map vs doseq(for)).

いろいろあるが手を動かして覚えたほうがいい. 基本的な機能は他の言語でもあるのでシンタックスを覚えるのみ.手続き的なパラダイムから脱出するためにも身に着けたいところ.

ref. 📝Clojure Tips

シーケンスにはユーティリティ関数もいろいろあるのでその都度覚えよう.

ref. シーケンスの分離と合流テクニック

reduceを進化させた📝Clojure Transducerもある.

Clojure 高階関数 Overview

  • mapはシーケンスに関数を適用してシーケンスを返す.
  • filterはシーケンスの要素のそれぞれにpredicateを適用してtrueの要素のみを取り出す.
  • reduce はシーケンスをaccuumurateして単一の戻り値を返す.
  • forはシーケンスを順番通りに通りに取り出す.
    • 手続き的に処理したい場合に使う.
    • pythonのforeach, zip的な.
  • flattenは入れ子構造の配列を単一シーケンスに変換する.

Clojure: map(function)

mapは遅延シーケンスを構築しdorun/doallなどで強制評価してはじめてリストが順次実行される.

しかしdoallを一連のmap/filter/reduce中に挟むと処理速度が落ちるため必要なときのみ利用する. または逐次処理であるdoseqを検討する.

途中で中身が必要というのはそもそもmapを命令形のfor文のノリで使っている可能性が高い.

mapの各要素を並列に実行するclojure pmapもある.

clojure: filter

与えられたコレクションから条件に合うもの抜き出す.

(filter pred coll)

filter系は派生関数がいろいろある.

  • remove は filterの逆で条件がtrueになるものを取り除く.
  • keep は fで評価した結果がnilでないものを残す.

tag: 🔖filter

📝Clojure: reduce

Clojureにおける🔖reduceまとめ. Clojureには📝Clojure Transducerというreduceを拡張した仕組みがある.

reduceに渡すカスタム関数

自作の関数を渡す時は, 引数に注意. 必ず2つ渡す必要がある.

(fn [acc x]
  (accoc acc :hoge x))

1つ目が集約結果の変数. 2つ目が今回処理する変数.

いつも忘れる & ネットで見つからない..

reduced: reduceを途中で打ち切る

条件にマッチしたらreduceを途中で打ち切るhelper関数としてreducedがある. loop/recurで書いていた処理もreduceで書きやすくなる.

reduced - clojure.core | ClojureDocs

(defn limit [x y]
  (let [sum (+ x y)]
    (if (> sum 10) (reduced sum) sum)))
 
(reduce limit 0 (range 10))
;; => 15

clojure: every?/some(all/any)

all, 全てがtrueならtrue.

(every? true? xs)

any, 1つでもtrueならtrue.

(some true? xs)

clojure.core/reductions

reduceの拡張. reduceだと最終的なoutputは処理の最終結果だが, reductionsはひとつずつの処理結果がリストになってすべて帰ってくる.

これはたとえば, reduceに🔖Accumulatorを組み合わせて書くような処理だったり, Clojure: 累積和(cumsum)の計算で活用できる.

https://clojuredocs.org/clojure.core/reductions

Clojure: 遅延シーケンス(Lazy Sequence)

📝Clojure シーケンスの多くは遅延評価される. 必要になるまで評価されない. すなわち遅延シーケンス.

📚プログラミングClojureでは, ほとんどすべてのケースで遅延シーケンスをつかったほうがいいといっている. ただ, 実践的にはClojure: シーケンスライブラリ(map/filter/reduce)をつかう延長で, インプットがどんなシーケンスでも処理する途中で遅延シーケンスが戻る結果つかっていることが多い印象.

言い換えると, シーケンスを処理する延長で意識せずとも利用している. 逆に言えば, Clojureを書いていると意識しなくて使ってしまうので, Clojureの遅延評価戦略は頭に入れておかないと思わぬバグを踏む.

遅延シーケンスの生成(lazy-seq)

遅延シーケンスの生成, またはその派生.

  • lazy-seq: 遅延シーケンス生成(cf. seq)
  • range: 遅延シーケンスの数列を作成できる.

see also. Clojure: 遅延評価(Laziness Evaluation)

遅延シーケンスの結合(lazy-cat)

concatはLazySeqを返すものの結合の途中で中身を評価することに注意. とくに遅延シーケンスを評価せずに結合したいときはlazy-catをつかう.

これはconcatのマクロでありやっていることは以下に過ぎない.

(lazy-cat xs ys zs) = (concat (lazy-seq xs) (lazy-seq ys) (lazy-seq zs))

シーケンス計算の強制評価(doall/dorun)

遅延シーケンスの実現には doall, dorunを利用する.

💡Clojure設計思想としての遅延評価戦略

なぜClojureの世界では全てが遅延シーケンスなのか?

値が必要になるまでその評価を遅らせるという🔖Clojure Wayががある.

💡Clojureでは遅延シーケンスを使いこなすことがキモ

Clojureの世界と実際のWeb開発

ここで語られている本質を理解したい.

  • 全てのリスト処理関数の大半は遅延シーケンスをつくる.
    • map/filter/reduce/constantly
    • iterate/repeat
  • 遅延シーケンスは要素を取得すると実体化する.
  • 全ては遅延実行される.
    • RDBへちょっとずつクエリを投げて最終的に全部取る遅延シーケンス.
    • 外部APIからoffset/limitを使って適宜データを取得する遅延シーケンス.

遅延シーケンスを返す関数を繰り返し適用する場合にこの問題が発生しうる

loop/recurの繰り返し処理でconcatをつかうと, concatの中で利用しているlazy-seqがseq, cocat, lazy-seqの無限ループを生んでStackoverflowするというTopic.

これはconcatのみではなく, 遅延シーケンスを返す関数一般にいえる.

Clojure遅延シーケンスとGCの関係

遅延シーケンスから取り出して処理し終わった要素は, 📝JVM:ガベージコレクションされるのか?というTopic.

takeやdropで無限シーケンスから実体化されたものは, そのあと参照がなくなればGCされる.

Clojure: 無限シーケンス

無限シーケンス, infinite sequence.

(遅延)無限シーケンスの生成

  • repeat: 遅延シーケンスのシンボルの繰り返しが作成できる.
  • repeatedly: 指定回数だけ無名関数を適用したシーケンスを作成できる.
  • iterate: 関数適用のシーケンスを作成できる. 数学の漸化式.

take/take-while: ある条件を満たすまで処理を続ける

takeは指定された数だけ要素を取得する.

take-whileはreduceの発展で, predを満たすまでシーケンスから要素を取得する.

たとえば先頭からソートされた状態でtimestampを条件にして取得するならば, filterよりも効率的である. ましてやlaze-seqなどはfilterよりもなおさらよい.

take-while - clojure.core | ClojureDocs

無限シーケンスを扱う上での重要な関数.

💡Clojureの再帰と無限シーケンスの関係

面白い記事. 再帰とは, loop/recurのシンタックス, 手続き型のwhile, イベントループ. これを遅延シーケンスで書き直す.

イベントループを遅延遅延シーケンスで書き換える． - tnoda-clojure

明確にinput, process, outputをわけることで, 入出力のいわゆる副作用と純粋な処理を分離してきれいにかけるという話.

🤔無限遅延シーケンスとは無限に生成できるルールが定義されてつど要素を生成するシーケンス

遅延シーケンスと無限シーケンスは概念としては指し示すものが違う.

無限遅延シーケンスという単語をきくが, 正確にはClojureで無限シーケンスというと, 無限な遅延シーケンスということで, 遅延シーケンスの無限という性質を指している. Clojureの無限シーケンスの性質としてLazinessという性質あるため, よく無限遅延シーケンス(lazy and infinite)と言われたりする(という理解).

無限の要素をもつシーケンス. これは, 要素の生成が処理として定義されたようなシーケンスであり, 取り出すときにそのつど評価して値を生成する, 言い換えればそれまでは評価を遅延している. という意味で, 無限シーケンスとは遅延シーケンス.

なにも無限だからといって, 1GBメモリをつんだPCから時空間が歪んだ先にある特別なアカシックレコードにアクセスしてそこに10000GBのデータの実体があるわけではない. そのつど生成している.

しかし, 無限というと直感的にはわかりにくい. 数学における極限や無限の概念と似ているかもしれない. 自然数すべて, など.

References

Clojure: シーケンスTopics

💡Clojureは省メモリなpersistentのデータ構造

📝永続性(persistent)とは, 更新のときに元のデータを保持するということは, 元のデータが大きいときはメモリ効率が悪いのでは？となるが, そこはよろしくやっているらしい.

イミュータブル時代の言語としてのClojure - Qiitaより.

ClojureではBit-partitioned hash triesというデータ構造を使って、イミュータブルでありながら省メモリで高性能を確保しています。

リスト全体をコピーするのではなく、リストをツリー構造で表現しておいて、変更が必要なサブツリー以外はもとのツリーを参照するというものです。

💡Clojure: transient: mutableなデータ構造

Clojureは工夫をしつつもimmutable性を保っているが(💡Clojureは省メモリなpersistentのデータ構造), それでも高速に更新が必要なときは非効率になる.

このとき, mutableなcollectionを作成するために, transientというデータ構造をつくる仕組みがある.

transientは単一スレッドで利用することを前提としていて, 変更が終わった persistent! という関数でpersistentに戻すことを前提としている.

💡ClojureにおけるSequenceとCollectionの違い

ClojureではCollectionとSequenceは異なる概念.

  • collection: データ構造の抽象.
  • sequence: collectionの中でデータを順次アクセス可能(シーカブル)なもの.

SequenceはCollectionの特殊な形態であり、Collectionを表現する方法の1つ.

実装レベルでは coll?で真が変えればcollection, seq?で真が変えればsequence.

collectionはIPersistentCollectionというインタフェースを実装しているもの. IPersistentCollectionは5つのメソッド（count, cons, empty, equiv, seq）からなる.

sequenceはISeqというインタフェースを実装しているもの. ISeqは(first, next, more, cons)からなる.

💡Clojureデータ構造の操作関数の分類

Clojureの関数は大きく分けて２つの種類に分けられる.

  • データ構造の操作の関数(conj, disj, assoc, dissoc…)
  • シーケンス操作の関数(cons, map, filter, reduce..)

データ構造を操作する関数は関数の次にデータ構造を受ける. 一方シーケンス操作は関数評価式の最後にデータ構造を受ける.

Clojure: Threading Macros にも 2種類あるのもこれが関係している.

ref: Clojure - Frequently Asked Questions

Associative vs Sequencialという概念の対立

T.B.D.

シーカブルとは

T.B.D. あとで深堀.

グラフビュー

バックリンク

Recents