Cons

cons je jednou ze základních funkcí jazyka Lisp. Jejími parametry jsou dva objekty a výstupem je jejich uspořádaný pár. Například volání cons x y vytvoří uspořádaný pár ( x . y ). Levý prvek tohoto páru je tradičně označován zkratkou car a pravý prvek zkratkou cdr.

Ukázky použití

Spojové seznamy

Interní podoba seznamu (42 69 613) vytvořeného pomocí cons:

(cons 42 (cons 69 (cons 613 nil)))

a vytvořeného pomocí funkce list:

(list 42 69 613)

Jedním ze základních použití uspořádných párů v lispu je vytvoření seznamů v podobě spojových seznamů. Cons se v tomto případě používá vnořeně: Seznam je dvojice, kde car je prvek a cdr je dvojice, kde car je prvek a cdr je dvojice, .... Tato posloupnost je ukončena tím, že cdr je speciálním prvkem nil.

Binární stromy

Binární stromy, u kterých jsou data pouze v listech, lze vytvořit podobně. Každý uzel, který není listem, je dvojicí svých podstromů. Například:

(cons (cons 1 2) (cons 3 4))

vytvoří strukturu:

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

tedy strom:

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

Výše uvedené spojové seznamy lze z tohoto hlediska vlastně pokládat také za stromy, ovšem zcela nevyvážené. Například seznam (1 . 2 . 3), který můžeme zapsat jako takovýto spojový seznam:

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

je vlastně následujícím binárním stromem:

   *
  / \
 1   *
    / \
   2   *
      / \
     3  nil

Reference

V tomto článku byl použit překlad textu z článku cons na anglické Wikipedii.