Skip to main content
Add an unrelated addendum to address compman's point more fully
Source Link
C. K. Young
  • 2.4k
  • 19
  • 22

Lists are much more versatile than arrays. With lists, you can recurse (e.g., for mapping or folding) by cdring down a list. This doesn't work for arrays; you'd have to pass in the array index too.

For example, this is a simple implementation of map and fold that take one list only:

(define (map1 f l)
  (if (null? l) l
      (cons (f (car l)) (map1 f (cdr l)))))

(define (left-fold1 f init l)
  (if (null? l) init
      (left-fold1 f (f (car l) init) (cdr l))))

How would you do that for arrays, without having to pass in another argument (for the index)? (Remember, Lisp and Scheme have no pointers, at least none that user code can touch.)


Also, lists can share storage, but arrays cannot. Take this Scheme code for example:

(define (x-world x)
  (cons x '(world)))

(define hello-world (x-world 'hello))
(define goodbye-world (x-world 'goodbye))

Here, hello-world has the value (hello world) and goodbye-world has the value (goodbye world).

There is one important fact, though: in many Scheme implementations, the (world) part of both lists is actually shared. This sharing would be impossible for arrays.


Addendum: To answer compman's point that recursion is somehow "non-production-grade", in Scheme, all standard looping/iteration is done using tail recursion. Here's a tail-recursive version of map1, for example:

(define (map1 f l)
  (let loop ((r '())
             (l (reverse l)))
    (if (null? l) r
        (loop (cons (f (car l)) r) (cdr l)))))

or, even more simply using left-fold1:

(define (map1 f l)
  (left-fold1 (lambda (e r) (cons (f e) r))
              '() (reverse l)))

reverse is a Scheme built-in, but its implementation is equally trivial (and also uses iteration only):

(define (reverse l)
  (left-fold1 cons '() l))

Lists are much more versatile than arrays. With lists, you can recurse (e.g., for mapping or folding) by cdring down a list. This doesn't work for arrays; you'd have to pass in the array index too.

For example, this is a simple implementation of map and fold that take one list only:

(define (map1 f l)
  (if (null? l) l
      (cons (f (car l)) (map1 f (cdr l)))))

(define (left-fold1 f init l)
  (if (null? l) init
      (left-fold1 f (f (car l) init) (cdr l))))

How would you do that for arrays, without having to pass in another argument (for the index)? (Remember, Lisp and Scheme have no pointers, at least none that user code can touch.)


Also, lists can share storage, but arrays cannot. Take this Scheme code for example:

(define (x-world x)
  (cons x '(world)))

(define hello-world (x-world 'hello))
(define goodbye-world (x-world 'goodbye))

Here, hello-world has the value (hello world) and goodbye-world has the value (goodbye world).

There is one important fact, though: in many Scheme implementations, the (world) part of both lists is actually shared. This sharing would be impossible for arrays.

Lists are much more versatile than arrays. With lists, you can recurse (e.g., for mapping or folding) by cdring down a list. This doesn't work for arrays; you'd have to pass in the array index too.

For example, this is a simple implementation of map and fold that take one list only:

(define (map1 f l)
  (if (null? l) l
      (cons (f (car l)) (map1 f (cdr l)))))

(define (left-fold1 f init l)
  (if (null? l) init
      (left-fold1 f (f (car l) init) (cdr l))))

How would you do that for arrays, without having to pass in another argument (for the index)? (Remember, Lisp and Scheme have no pointers, at least none that user code can touch.)


Also, lists can share storage, but arrays cannot. Take this Scheme code for example:

(define (x-world x)
  (cons x '(world)))

(define hello-world (x-world 'hello))
(define goodbye-world (x-world 'goodbye))

Here, hello-world has the value (hello world) and goodbye-world has the value (goodbye world).

There is one important fact, though: in many Scheme implementations, the (world) part of both lists is actually shared. This sharing would be impossible for arrays.


Addendum: To answer compman's point that recursion is somehow "non-production-grade", in Scheme, all standard looping/iteration is done using tail recursion. Here's a tail-recursive version of map1, for example:

(define (map1 f l)
  (let loop ((r '())
             (l (reverse l)))
    (if (null? l) r
        (loop (cons (f (car l)) r) (cdr l)))))

or, even more simply using left-fold1:

(define (map1 f l)
  (left-fold1 (lambda (e r) (cons (f e) r))
              '() (reverse l)))

reverse is a Scheme built-in, but its implementation is equally trivial (and also uses iteration only):

(define (reverse l)
  (left-fold1 cons '() l))
added 133 characters in body
Source Link
C. K. Young
  • 2.4k
  • 19
  • 22

Lists are much more versatile than arrays. With lists, you can recurse (e.g., for mapping or folding) by cdring down a list. This doesn't work for arrays; you'd have to pass in the array index too.

For example, this is a simple implementation of map and fold that takestake one list only:

(define (map1 f l)
  (if (null? l) l
      (cons (f (car l)) (map1 f (cdr l)))))

(define (left-fold1 f init l)
  (if (null? l) init
      (left-fold1 f (f (car l) init) (cdr l))))

How would you do that for arrays, without having to pass in another argument (for the index)? (Remember, Lisp and Scheme have no pointers, at least none that user code can touch.)

 

Also, lists can share storage, but arrays cannot. Take this Scheme code for example:

(define (x-world x)
  (cons x '(world)))

(define hello-world (x-world 'hello))
(define goodbye-world (x-world 'goodbye))

Here, hello-world has the value (hello world) and goodbye-world has the value (goodbye world).

There is one important fact, though: in many Scheme implementations, the (world) part of both lists is actually shared. This sharing would be impossible for arrays.

Lists are much more versatile than arrays. With lists, you can recurse (e.g., for mapping or folding) by cdring down a list. This doesn't work for arrays; you'd have to pass in the array index too.

For example, this is a simple implementation of map that takes one list only:

(define (map1 f l)
  (if (null? l) l
      (cons (f (car l)) (map1 f (cdr l)))))

How would you do that for arrays, without having to pass in another argument (for the index)? (Remember, Lisp and Scheme have no pointers, at least none that user code can touch.)

Also, lists can share storage, but arrays cannot. Take this Scheme code for example:

(define (x-world x)
  (cons x '(world)))

(define hello-world (x-world 'hello))
(define goodbye-world (x-world 'goodbye))

Here, hello-world has the value (hello world) and goodbye-world has the value (goodbye world).

There is one important fact, though: in many Scheme implementations, the (world) part of both lists is actually shared. This sharing would be impossible for arrays.

Lists are much more versatile than arrays. With lists, you can recurse (e.g., for mapping or folding) by cdring down a list. This doesn't work for arrays; you'd have to pass in the array index too.

For example, this is a simple implementation of map and fold that take one list only:

(define (map1 f l)
  (if (null? l) l
      (cons (f (car l)) (map1 f (cdr l)))))

(define (left-fold1 f init l)
  (if (null? l) init
      (left-fold1 f (f (car l) init) (cdr l))))

How would you do that for arrays, without having to pass in another argument (for the index)? (Remember, Lisp and Scheme have no pointers, at least none that user code can touch.)

 

Also, lists can share storage, but arrays cannot. Take this Scheme code for example:

(define (x-world x)
  (cons x '(world)))

(define hello-world (x-world 'hello))
(define goodbye-world (x-world 'goodbye))

Here, hello-world has the value (hello world) and goodbye-world has the value (goodbye world).

There is one important fact, though: in many Scheme implementations, the (world) part of both lists is actually shared. This sharing would be impossible for arrays.

Source Link
C. K. Young
  • 2.4k
  • 19
  • 22

Lists are much more versatile than arrays. With lists, you can recurse (e.g., for mapping or folding) by cdring down a list. This doesn't work for arrays; you'd have to pass in the array index too.

For example, this is a simple implementation of map that takes one list only:

(define (map1 f l)
  (if (null? l) l
      (cons (f (car l)) (map1 f (cdr l)))))

How would you do that for arrays, without having to pass in another argument (for the index)? (Remember, Lisp and Scheme have no pointers, at least none that user code can touch.)

Also, lists can share storage, but arrays cannot. Take this Scheme code for example:

(define (x-world x)
  (cons x '(world)))

(define hello-world (x-world 'hello))
(define goodbye-world (x-world 'goodbye))

Here, hello-world has the value (hello world) and goodbye-world has the value (goodbye world).

There is one important fact, though: in many Scheme implementations, the (world) part of both lists is actually shared. This sharing would be impossible for arrays.