62

リストの先頭に追加するのは簡単です:

user=> (conj '(:bar :baz) :foo)
(:foo :bar :baz)

ベクトルへの追加は簡単です。

user=> (conj [:bar :baz] :foo) 
[:bar :baz :foo]

ベクトルを取得しながら、どうすれば (慣用的に) ベクトルの先頭に追加できますか? ベクトルではなく seq を返すため、これは機能しません。

user=> (cons :foo [:bar :baz])     
(:foo :bar :baz)

これは醜いです（IMVHO）：

user=> (apply vector (cons :foo [:bar :baz])) 
[:foo :bar :baz]

注：基本的には、追加および先頭に追加できるデータ構造が必要です。大きなリストに追加すると、パフォーマンスが大幅に低下するはずなので、ベクトルを考えました..

4

5 に答える 5

80

ベクトルは先頭に追加するようには設計されていません。O(n) プリペンドのみがあります:

user=> (into [:foo] [:bar :baz])
[:foo :bar :baz]

あなたが望むのは、おそらくfinger treeです。

于 2010-11-04T10:40:11.817 に答える
18

この質問は古いことは知っていますが、差分リストについて誰も何も言わなかったので、追加して先頭に追加できるものが本当に欲しいと言っているので、差分リストが役立つように思えます。これらは Clojure では人気がないように見えますが、実装が非常に簡単で、finger ツリーよりもはるかに複雑ではないため、今、小さな差分リスト ライブラリを作成しました (そして、それをテストしました)。これらは O(1) 時間で連結されます (先頭または末尾に追加)。差分リストをリストに戻すには、O(n) のコストがかかるはずです。これは、多くの連結を行っている場合に適したトレードオフです。多くの連結を行っていない場合は、リストに固執するだけですよね? :)

この小さなライブラリの関数は次のとおりです。

dl:差分リストは実際には、それ自体の内容を引数と連結し、結果のリストを返す関数です。差分リストを作成するたびに、データ構造のように機能する小さな関数を作成しています。

dlempty:差分リストはその内容を引数に連結するだけなので、空の差分リストは恒等関数と同じです。

undl:差分リストの機能により、差分リストを nil で呼び出すだけで通常のリストに変換できるため、この関数は実際には必要ありません。それは便宜上のものです。

dlcons:リストの先頭にある項目を conses します -- 完全に必要というわけではありませんが、cons は十分に一般的な操作であり、ワンライナーです (ここのすべての関数と同様)。

dlappend: 2 つの相違リストを連結します。私はその定義が最も楽しいと思います - それをチェックしてください! :)

そして今、これがその小さなライブラリです。O(1) の追加/前置データ構造を提供する 5 つの 1 行の関数です。悪くないですよね？ああ、ラムダ計算の美しさ...

(defn dl
  "Return a difference list for a list"
  [l]
  (fn [x] (concat l x)))

; Return an empty difference list
(def dlempty identity)

(defn undl
  "Return a list for a difference list (just call the difference list with nil)"
  [aDl]
  (aDl nil))

(defn dlcons
  "Cons an item onto a difference list"
  [item aDl]
  (fn [x] (cons item (aDl x))))

(defn dlappend
  "Append two difference lists"
  [dl1 dl2]
  (fn [x] (dl1 (dl2 x))))

これで実際にそれを見ることができます：

(undl (dlappend (dl '(1 2 3)) (dl '(4 5 6))))

戻り値:

(1 2 3 4 5 6)

これも同じものを返します。

((dl '(1 2 3)) '(4 5 6))

違いリストを楽しんでください！

アップデート

理解するのがより難しいかもしれないいくつかの定義を次に示しますが、より良いと思います。

(defn dl [& elements] (fn [x] (concat elements x)))
(defn dl-un [l] (l nil))
(defn dl-concat [& lists] (fn [x] ((apply comp lists) x)))

これにより、次のようなことが言えます。

(dl-un (dl-concat (dl 1) (dl 2 3) (dl) (dl 4)))

どちらが返されますか

(1 2 3 4)
于 2012-11-12T22:53:15.683 に答える
3

ユーザー optevo がフィンガー ツリーの回答の下のコメントで述べたように、RRB ツリーを実装するclojure/core.rrb-vector libを使用できます。

RRB ツリーは、Clojure の PersistentVectors に基づいて構築されており、対数時間の連結とスライスが追加されています。ClojureScript は、vector-of関数がないことを除いて、同じ API でサポートされています。

このライブラリはそれに値すると思うので、これを別の回答として投稿することにしました。ClojureScript をサポートし、さまざまなデータ構造の実装に関する仕事で Clojure コミュニティ内でよく知られているMichał Marczykによって保守されています。

于 2015-10-14T19:05:58.350 に答える
2

If you don't fear quasiquoting, this solution is actually pretty elegant (for some definitions of 'elegant'):

> `[~:foo ~@[:bar :baz]]

[:foo :bar :baz]

I actually use this on occasion in real code, since the declarative syntax makes it pretty readable IMHO.

于 2018-12-21T19:53:41.880 に答える
1

Tupelo Library に組み込まれている便利な機能を使用することをお勧めします。例えば：

(append [1 2] 3  )   ;=> [1 2 3  ]
(append [1 2] 3 4)   ;=> [1 2 3 4]

(prepend   3 [2 1])  ;=> [  3 2 1]
(prepend 4 3 [2 1])  ;=> [4 3 2 1]

比較すると、生の Clojure では間違いを犯しやすいです。

; Add to the end
(concat [1 2] 3)    ;=> IllegalArgumentException
(cons   [1 2] 3)    ;=> IllegalArgumentException
(conj   [1 2] 3)    ;=> [1 2 3]
(conj   [1 2] 3 4)  ;=> [1 2 3 4]

; Add to the beginning
(conj     1 [2 3] ) ;=> ClassCastException
(concat   1 [2 3] ) ;=> IllegalArgumentException
(cons     1 [2 3] ) ;=> (1 2 3)
(cons   1 2 [3 4] ) ;=> ArityException
于 2016-07-07T19:42:16.573 に答える