IPersistentStack

Last updated at 2017-06-28Posted at 2017-06-28

普段Clojureを書く中であまり使わない(というか一度も使ったことない)popとpeekについて調べてまとめてみた。

要点

一般的にはLIFOな抽象データ型で以下の3つの操作をサポートしている物

このうちpushとpop操作がスタックを満すのに必須で、peekは任意っぽい

一般的なスタックの操作はミュータブルで、Clojureと相性が悪いためスタック操作のイミュータブル版は以下になる

注：イミュータブルなコレクションの文脈では'最後'というのは関数の適用の順序で
'追加'も要素を追加した後のコレクションを返す関数をコレクションに適用するという意味になる

listは先頭に、vectorは最後尾に要素を追加した物が返ってくる

;; conj to a list
(conj '(1 2 3 4) 5) => (5 1 2 3 4)

;; conj to a vector
(conj [1 2 3 4] 5) => [1 2 3 4 5]

追加する先がlistにせよvectorにせよイミュータブルなスタックとみなした場合、
'最後'にconjした要素が5なのでpeekをすると5が返ってくる。

(-> [1 2 3 4]
    (conj 5)
    peek) =>5

(-> '(1 2 3 4)
    (conj 5)
    peek) => 5

追加する先がlistにせよvectorにせよイミュータブルなスタックとみなした場合、
'最後'にconjした要素が5なのでpopをすると5を除外したコレクションが返ってくる。

;; popping from a vector
(-> [1 2 3 4]
    (conj 5)
    pop) => [1 2 3 4]

;; popping from a list
(-> '(1 2 3 4)
    (conj 5)
    pop) => (1 2 3 4)

lastはシーケンスの抽象に依存しているなので、先頭から最後に辿り付くまで要素を全て走査してしまうため遅いが、
vectorに対するpeekは高速で最後尾の要素を取得できる

(time
 (last [1 2 3 4 5 6 7 8 9]))
;; "Elapsed time: 0.171368 msecs"


(time
 (peek [1 2 3 4 5 6 7 8 9]))
;; "Elapsed time: 0.066708 msecs"