search


Data Structures: Lists and Vectors
Mon Apr 02 00:00:00 UTC 2018

In our last class, there was a question about the difference between parenthesis ( ) and bracket [ ]. Let's look at a code example of how the parentesis and brackets are used:

(defn square [x] (* x x)) (prn "square of 4 is" (square 4)) (prn "square of 5 is" (square 5))

The code above defines a function name square that has one input name x. The only place where the brackets are used is for the function parameter [x]

You might be wondering can [x] be replace with (x)? The answer is NO. Try yourself and see what happens. The REPL will show an error. You next question might be why? That's a good question but the answer is because the designer of Clojure made it that way. That's an unsatisfying answer but the rationale of this decision is beyond the scope of this post. You will not appreciate the rationale until you've done a lot of Clojure programming. However, this can be a question you write down in your notebook of questions to investigate on your own. Unfortunately for now, this is just syntax rule of Clojure you have to accept because the designer of Clojure dictated it. With other dialects of LISP, like Scheme and Common LISP the answer is YES. For example, the square function written in Scheme and Common LISP is

(defun square (x)
  (* x x))

The syntax of Clojure requires parameter of a function be enclosed in brackets [ ] but the syntax of other LISP dialects use parenthesis ( ) to enclose parameter of function

What exactly is ( ) ?

( ) is the literal representation of list which is a data structure from which LISP gets its name. LISP stands for LISt Processing. A list is a sequence of things. Here are more examples of a list

(def a (list 1 2 3)) ;;this is a list of 3 numbers (def b '(1 2 3)) ;;same list of 3 numbers using the quote ' ;;There are two basic operations on lists: first and rest (prn "first element of a is "(first a)) (prn "the rest of a is " (rest a))
What exactly is [ ] ?

[ ] is the literal represnetation of a vector which is similar to a list except an element of the vector can be retrieved directly using an index. We saw how vector are used to hold the parameters ofa function. Here are examples of vectors and how they are used

(def v [1 2 3]) ;; a vector of 3 numbers (prn "(first v) =" (first v)) ;;first element of vector v (prn "(rest v) =" (rest v)) ;;rest of vector v (prn "(nth v 0) =" (nth v 0)) ;;use nth function to get first element of v. first element starts at 0 (prn "(nth v 1) =" (nth v 1)) ;;second element of vector v. (prn "(nth v 2) =" (nth v 2)) ;;third element of vector v.
What is the difference between a list and a vector?

list and vectors are both sequences of things on which you can call first and rest on. However, the elements of a vector can be accessed using a integer index with the nth function. You cannot use the nth function on a list

A good analogy to show the difference between a list and a vector is a book. If the pages of a book are contained in a list, to get to 10th page, you must read through pages 1 to 9 before you can read the 10th page. However, if the pages of a book are contained in a vector, you can just jump to the 10th page directly without reading pages 1 to 9.

What do LISP programmers mean when they say code is data?

Look at the square function above. It is composed of two nested lists, a vector and 4 unique symbols in other words data LISP/Clojure code is written in terms of its own data structures. This is called homoiconicity . Since LISP code is expressed in LISP data structures, writing code to manipulate code is easy. We will get to this concept when we cover macro. Other languages have copied ideas from LISP but not the LISP macro system.

If code is data, is the reverse true? is data code?

No! Data is not code. Code is semantic interpretation of data. LISP data is represented as s-expression . S-expressions are expressive enough to represent ANY type of data. S-expression is an abstract syntax for data. We've experimented with HTML. HTML is a limited concrete subset of s-expressions. XML and JSON, which are commonly used for encoding data in distributed systems, are also limited forms of s-expressions. Clojure's flavor of s-expressions is called EDN EDN defines the syntax of data but not the semantics. Code is data that is given special semantic meaning.

for example, this is data: a list of 3 numbers

(1 2 3)
This is also data but it is more complex.
(defn square [x]
	(* x x))
For the above data to become code, we have to interpret and give meaning to the data. The rules of LISP is what defines the semantics and make data code. For example, one rule of LISP is the first element of a list must be a function. Since the first element is defn it is valid code. However, (1 2 3) is data and not code because the first element is not a callable function. Try typing (1 2 3) into the REPL. You will get a syntax error. It must be treated as data by quoting it with the apostrophe ' like '(1 2 3)

We can give semantic meaning to (1 2 3) and make it code but we would have to write our own interpreter. In fact LISP/Clojure, are great tools for writing interpreters. The website you're reading right now is written in a language I invented to give semantic meaning to data.

Does Clojure have other built-in data-structures?

I'm glad you asked. Yes. In addition to lists and vectors, Clojure has 2 other built-in data-structures

  • Maps
  • Sets

However I will discuss this in another post