Friday, July 31, 2009

Sequences, Arrays and Vectors

As I mentioned in my earlier post, lists and arrays are a sub-type of sequences. Hence in this article, I first give an overview of some functions that work for any sequence (lists and arrays) before describing arrays and some basic functions on arrays. As before, the detailed version for this topic can be found here.
  1. Sequences
    1. Lists & cons cells
    2. Arrays
      • Strings
      • Vectors
      • bool-vector
      • char-table


So what is a sequence? The sequence that we are using and referring to here is the mathematical definition of sequence.In mathematics, a sequence is an ordered list of objects (or events). Thus any list or array is a sequence and any sequence is either a list or an array.

The functions sequencep and length, described below are intuitive.
;; 6.1 Sequences
;; (sequencep object)  ==> Is object a sequence?

(sequencep ())        ; A list is a sequence
(sequencep '(a b c))  ; Another list
(sequencep "Hello")   ; A string is an array and hence a sequence
(length "Hello")      ; length returns the length of the sequence

The elt function is a generalization of the functions 'nth' and 'aref' which work on lists and arrays respectively.
Its form is (elt sequence index) where, sequence is any list/array and the value at index is returned.
The function copy-sequence returns a copy of the sequence given as argument to it.
;; elt sequence index ==> element of sequence at (0-based) index
(elt [1 2 3 4] 2)
(elt '(1 2 3 4) 2)
(string (elt "1234" 2))

;; copy-sequence sequence
;; shared structure
;; does not work with circular lists

(setq seq '(1 2 3 4))
(setq a (copy-sequence seq))

As an aside, have a look at the string function that has been used above. It is pretty useful and the program below is cool.
You must check it out.
;; The string function
(string ?a)
(string 99 97 116)
(string 108 105 115 112  32 105 115 32 97 109 97 122 105 110 103)
;; Want to know what the above program outputs?
;; You just have to execute it to know !!!


An array is a very important data structure that is prevalent in almost every programming language like C, Java, python and others. However, in the past, lisp has focussed and given preference to lists more than to arrays (from what i know and in my opinion). Thus, the support for arrays is very meagre in lisp.

However, an array is a very essential data type. It is similar to a list. It is a sequence but the way it differs from lisp is the manner you access an element. The time taken to access an element of a list is proportional to the position or location of the element in the list whereas the time taken to access and set the element in an array is constant, independent of it's position in the array.
;;6.2 Arrays
;; types -- "strings","vectors","bool-vectors" & "char-tables"

;; zero-based indexing, fixed length,
;; self-evaluating,
;; can be changed using aset
;; Value can be read using aref.

(arrayp [1 2 3])         ; [1 2 3] is a vector, a subtype of array
(arrayp (syntax-table))  ; (syntax-table) returns a char-table

The function
  • 'aref' gets the element at a particular position from an array.
    (For those who know C or java (aref array i) <==> array[i])
  • 'aset' is used to set an element in the array.
  • 'fillarray' is used to set(or reset) all elements of the array to some value
(aref "abcdefg" 1)
(string (aref "abcdefg" 1))   ; an example of string too

(setq w [foo bar baz])
(aset w 0 'fu)

(setq x "asdfasfd")
(aset x 3 ?Z)

(setq a [a b c d e f g])
(fillarray a 0)

(setq s "When in the course")
(fillarray s ?-)


A vector is a very interesting sub-type of an Array. It provides for maximum flexibility in creating an array as each element of a vector can be of any data type.
;; 6.4 Vectors

(setq avector [1 two '(three) "four" [five]])
(eval avector)
(eq avector (eval avector))        ; Shows that an array is a self-evaluating form

;; 6.5 Functions for Vectors
;; vectorp, vector, make-vector
;; vconcat,

(setq avector [1 two (quote (three)) "four" [five]])

(append avector nil)

;; 6.7 Bool-vectors

(setq s (make-bool-vector 10 t))
(bool-vector-p s)


Post a Comment