The Cons Cell

  • Lists are built from CONS CELLS
  • The basic element of (linked) lists.

#+demo
(ql:quickload "draw-cons-tree")

#+demo
(use-package :draw-cons-tree)

(draw-tree 
  (list :a :b))

(draw-tree (cons :a :b))
;; CONS = construct object in memory

;; how to build a (proper) list from CONS cells?
;; lists actually have a nil pointer as the last element.
(cons 1 (cons 2 nil)) = (1 2)

Access elements in a cell

;; first, rest

  • Performance: don't use lists with thousands of elements: because the computer will start at number 1 until it can access to the needed index. It's because lists are not like arrays, the next element might not be stored next to each other in the computer memory.

  • But push in front and reverse are fast.

  • CAR and CDR ("counder")

  • CAR is the equivalent of FIRST (Content of the Address part of the Register)

  • CDR is the old name for REST (Content of the Decrement part of the Register)

  • We use first and rest for working with a list, car and cdr when we want to emphasize that we are not working with a proper list, but with something built from CONS cells.

  • This algorithm "conses" a lot = it allocates too much memory.