短所

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータプログラミングcons/ ˈkɒnz /または/ ˈkɒns /)はLispプログラミング言語のほとんどの方言の基本的な関数ですconsは、2つの値または値へのポインタを保持するメモリオブジェクトを構築します。これらのオブジェクトは、(cons)セル、conses、非アトミックS式( "NATSes")、または(cons)ペアと呼ばれます。Lispの専門用語では、「xyに変換する」という表現は、次のように新しいオブジェクトを作成することを意味します。cons (cons x y)結果のペアには、car(最初​​の要素、またはレジスタのアドレス部分の内容)と呼ばれる左半分と、 (2番目の要素、またはレジスタのデクリメント部分の内容)と呼ばれる右半分があります。 cdr

これは、引数を指定して新しいオブジェクトを作成するコンストラクターのオブジェクト指向の概念と大まかに関連しており、代数的データ型システム のコンストラクター関数とより密接に関連しています。

「短所」という言葉や「短所に」のような表現も、より一般的な関数型プログラミングの専門用語の一部です。特にリスト処理のコンテキストで同様の目的を持つ演算子は、「短所」と発音されることがあります。(良い例は、MLScalaF#Elm::の演算子、またはリストの先頭に要素を追加する Haskellの演算子です。):

を使用

consセルは、順序付けられたデータのペアを保持するために使用できますが、より複雑な複合データ構造、特にリストバイナリツリーを構築するためによく使用されます。

順序対

たとえば、Lisp式は、左半分(いわゆるフィールド)に1、右半分(フィールド)に2を保持するセルを構築します。Lisp表記では、値は次のよう になります。(cons 1 2)carcdr(cons 1 2)

(1.2)

1と2の間のドットに注意してください。これは、S式が「リスト」ではなく「ドットペア」(いわゆる「コンペア」)であることを示しています。

リスト

リスト(42 69 613)の短所セル図cons
短所 42  短所 69  短所 613  nil )))
と書かれていlistます:
リスト 42  69  613 

Lispでは、リストはconsペアの上に実装されます。より具体的には、Lispのリスト構造は次のいずれかです。

  1. 空のリスト()。これは通常、と呼ばれる特別なオブジェクトnilです。
  2. carリストの最初の要素でありcdr、残りの要素を含むリストであるconsセル。

これは、内容を、、、およびで操作できる単純な単一リンクリスト構造の基礎を形成します。短所のペアでもない唯一のリストであることに注意してください。例として、要素が1、2、および3であるリストについて考えてみます。このようなリストは、次の3つのステップで作成できます。 conscarcdrnil

  1. 短所3 nil、空のリスト
  2. 結果に短所2
  3. 結果に短所1

これは、単一の式に相当します。

短所 1  短所 2  短所 3  nil )))

またはその省略形:

リスト 1  2  3 

結果の値はリストです:

(1。(2。(3。nil)))

すなわち

*-*-*-nil
 | | |
 1 2 3

これは一般的に次のように省略されます。

(1 2 3)

したがって、cons既存のリンクリストの前に1つの要素を追加するために使用できます。たとえば、xが上記で定義したリストである場合、リストは次のように生成 されます。(cons 5 x)

(5 1 2 3)

もう1つの便利なリスト手順はappend、2つの既存のリストを連結する(つまり、2つのリストを1つのリストに結合する)です。

にデータのみを格納する二分木も、を使用して簡単に構築できconsます。たとえば、次のコードは次のとおりです。

短所 短所 1  2  短所 3  4 ))

ツリーの結果:

((1 .2)。(3 .4))

すなわち

   *
  / \
 **
/ \ / \
1 2 3 4

技術的には、前の例のリスト(1 2 3)も二分木であり、特に不均衡なものです。これを確認するには、図を再配置するだけです。

*-*-*-nil
 | | |
 1 2 3

次の同等物に:

   *
  / \
 1 *
    / \
   2 *
      / \
     3なし

会話で使う

短所は、命令型プログラミング言語で使用されるような破壊的な操作を使用するのではなく、メモリ割り当ての一般的なプロセスを参照できます。例えば:

ばかげているのではなく、副作用を入れることでコードを少しスピードアップしました。

機能の実装

Lispにはファーストクラスの関数があるため、consセルを含むすべてのデータ構造は関数を使用して実装できます。たとえば、Schemeでは:

define cons x  y 
  lambda m  m  x  y )))
define car z 
  z  lambda p  q  p )))
define cdr z 
  z  lambda p  q  q )))

この手法はチャーチエンコーディングとして知られています。これは、「consセル」としての関数を使用して、 conscar、およびcdr操作を再実装します。チャーチエンコーディングは、純粋なラムダ計算でデータ構造を定義する通常の方法です。これは、Schemeに密接に関連する抽象的な理論的な計算モデルです。

この実装は、学術的には興味深いものですが、consセルを他のSchemeプロシージャと区別できなくし、不必要な計算の非効率性をもたらすため、実用的ではありません。

ただし、同じ種類のエンコーディングを、バリアントを含むより複雑な代数的データ型に使用できます。この場合、他の種類のエンコーディングよりも効率的であることが判明することもあります。[1]このエンコーディングには、ラムダの代わりにインターフェースを使用して 、 Java などのバリアントを持たない静的に型付けされた言語で実装できるという利点もあります。

も参照してください

参考文献

  1. ^ 「アーカイブされたコピー」 (PDF)2010-03-31にオリジナル (PDF)からアーカイブされました2009年3月1日取得{{cite web}}:CS1 maint:タイトルとしてアーカイブされたコピー(リンク

外部リンク

  • SDRAW、描画用のCommon Lisp コードは、consセル構造を描画します。デビッドS.トゥレツキーから。