CODEWITHSUNDEEP
schemeracket
rnso
rnso

Reputation: 24535

Using cons/car vs append to create lists in Racket

I want to make a list of squares. I can do it with following code: 

(define (makelistsq n)
  (define outlist '())
  (for ((i n))
    (set! outlist (append outlist (list (* i i))))
    )
  outlist
  )

(makelistsq 5)

Output:

'(0 1 4 9 16)

However, I have seen that often cons and car keywords are used to create and add to lists. Does that method has any advantage over appending as above? So, is following better or same as above: 

(define (makelistsq2 n)
  (define outlist '())
  (for ((i n))
    (set! outlist (cons (* i i) outlist))
    )
  (reverse outlist)
  )

Thanks for your answers/comments.

Edit: on this page Cons element to list vs cons list to element in Scheme it is mentioned that all use of append is wrong:

For those rare occasions where you need to add one element at the end (and believe me, doing so generally means that you're thinking the algorithm wrong) you can use append

Upvotes: 0

Views: 6388

Answers (3)

simmone
simmone

Reputation: 379

my version:

#lang racket

(define (make-square-list n)
  (let loop ([count 1]
             [result_list '()])
    (if (<= count n)
        (loop (add1 count) (cons (* count count) result_list))
        (reverse result_list))))

(make-squqre-list 10)

(1 4 9 16 25 36 49 64 81 100)

Upvotes: 0

Sylwester
Sylwester

Reputation: 48745

cons is the constructor for a pair. A list isn't anything else than a chain of cons that is terminated by the empty list ().

append is a function that uses cons in the implementation. Here is the implementation for a two argument append:

(define (append lst1 lst2)
  (if (null? lst1)
      lst2
      (cons (car lst1) 
            (append (cdr lst1) lst2))))

In plain english it makes an new pair for every pair of lst1 and then attach the lst2. It's not very efficient so in your first example to produce that 5 element list it has to have made a 4, 3, and 2 element list in addition to the one element list you explicitly made for each step.

When working with lists it iterates in order from first to last, but the creation of a list happens from end to beginning. Often it's not possible to do something in reverse and thus need to reverse the result in the end, but in your case it's easy to count down instead of up.

(define (make-square-list end)
  (let loop ((n (sub1 end)) (acc '()))
    (if (< n 0)
        acc
        (loop (sub1 n) 
              (cons (* n n) acc)))))

With higher order functions you can eliminate the boilerplate but #!racket has an alternative that makes even shorter code called for/list. 

(define (make-square-list end)
  (for/list ((n (range end)))
    (* n n)))

for/list is basically the same as map but as a special form.

Upvotes: 2

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236004

I won't repeat my own answer :P . Yes, using append is generally the wrong way to build an output list. But neither of your implementations seem right - most of the time, you have to forget about set! and loops.

Recursion is the way to go, and using cons and (if necessary) reverse at the end is the preferred way to build a list. In fact, the function in the question can be expressed more succinctly using built-in procedures, and this is the recommended way when writing functional-style code:

(define (makelistsq2 n)
  (map (lambda (x) (* x x))
       (range n)))

For the sake of completeness, let's see how we would write the procedure from scratch, using cons for building the output - for those rare occasions when there isn't a built-in procedure that does what you need. This generates a recursive process, notice that here we go from zero to n-1:

(define (makelistsq2 n)
  (define (helper i)
    (if (= i n)
        '()
        (cons (* i i)
              (helper (add1 i)))))
  (helper 0))

The above solution is fine, and works perfectly for small lists. If (and only if) the output list is huge, you might want to build it using tail recursion; this is more efficient as it doesn't require additional memory for the iteration - we'll use a named let, and notice that this generates an iterative process, going from n-1 to zero:

(define (makelistsq2 n)
  (let loop ((i (sub1 n)) (acc '()))
    (if (negative? i)
        acc
        (loop (sub1 i) (cons (* i i) acc)))))

No matter which implementation you pick, the result is now as expected:

(makelistsq2 5)
=> '(0 1 4 9 16)

Upvotes: 4

Related Questions