The sequence abstraction






cycognito



clojure logo

Topics

  1. Lists

  2. Vectors

  3. Sequences

Lists

  • The core of LISP: LISP stands for LISt Processing.

  • Logically, that’s the only data structure we need

  • In terms of performances, it’s not enough

hello list

List creation

You can mix element of different types inside a list

(list 1 2 "hello")

You can nest lists inside lists inside lists inside lists…​

(list 1 2 (list "a" "b") (list 1.2 (list 3.43243 2.5)))

There is a syntactic sugar for list creation: the single quote '

'(1 2 3)

And it works fine with nested lists

'(1 2 ("a" "b" (1 2 4)))

Query on lists

Get the first element of a list

(first '(1 2 3 4 5))

Check if the list is empty

(empty? '(1 2 3 4 5))

Removing the first element of a list

Create a new list without the first element

(def a '(1 2 3 4 5))
(def b (rest a))

The new list is changed

b

The original list is left unchanged

a

Adding an element to a list

Create a new list with an element prepended

(def c '(1 2 3 4 5))
(def d (cons 0 c))

The new list is changed

d

The original list is left unchanged

c

Efficient immutable lists

The implementation of rest

immutable lists rest


The implementation of cons

immutable list cons

Vectors

Vectors are like lists but with fast random access.

Vector creation

Vectors are created using vector

(vector 1 2 3 4 5)


Nested vectors can be created using the literal []

(def a [1 2 3 4 "aa" [1 2] [1 2 3]])
a

Query on vectors

Random access

(nth ["a" "b" "c"] 2)

Modifying an entry in a vector

Create a new vector with a modified entry

(def v [0 1 2 3 4])
(def w (assoc v 2 200))

The new vector is changed

w

The original vector is left unchanged

v

Efficient immutable vectors

The secrets of persistent data structures Part 1 and Part 2.

clojure vectors

Vectors vs lists

☕ Why do we need lists if vectors has more features?


  • Lists are more efficient in terms of memory

  • For iterations, lists are more efficient in terms of CPU

  • Deep argument: When a list is enough why would we use a vector?

The sequence abstraction

  1. first

  2. rest

  3. empty?

  4. cons

That’s the foundation of the rich set of Clojure data manipulation functions: map, filter, reduce, sort …​

The sequence abstraction in action

The sequence functions work on any data collection

(first [1 2 3 4 5])

Be careful: rest always returns a sequence!

(rest [1 2 3 4 5])

Be careful: cons always returns a sequence!

(cons 0 [1 2 3 4 5])


(empty? [1 2 3 4 5])

Sequence vs. list

Sequences are printed like lists

(rest [1 2 3 4 5])

A sequence is not the same as a list

(= (type (rest [1 2 3 4 5])) (type '(2 3 4 5)))

Equality check the values, not the concrete sequence type

(= (rest [1 2 3 4 5]) '(2 3 4 5))

Equality check the values, not the concrete sequence type

(= [1 2 3 4 5] '(1 2 3 4 5))

Homework

Sequences - Practice

Write a function that receives a sequence and returns its fifth element.

(defn fifth [lst]
;; Write your code here
)


(assert (= (fifth '(1 2 3 4 5 6 7 8)) 5))

Sequences - Practice (2)

🏂 Write a function that receives a number n and a sequence and returns its nth element. You’ll need to use recursion.

(defn nth-element [lst n])


(assert (= (nth-element '(1 2 3 4 5 6 7 8 9 10 11) 10) 10))

Sequences - Practice (3)

🏂 Write a function called select-1-5-7 that receives a sequence and returns a sequence with the elements of the original sequence at positions 1, 5 and 7.

You might use either your nth-element function or clojure nth.

(defn select-1-5-7 [lst])


(assert (= (select-1-5-7 (range 10)) '(0 4 6)))

Sequences - Practice (4)

🏂 Write a function called my-map that receives a function and a sequence and returns a sequence made of the application of the function to the elements of the sequence.

  • You are allowed to use recursion.

  • You are not allowed to use functions from clojure.core like map

(defn my-map [f s])


(assert (= (my-map inc [1 2 3]) '(2 3 4)))

Read