Scheme/Racket: most idiomatic way to append single

问题:

I want to append the element b to the list a (let's say (a1, a2, ... an)), e.g. appending the number 3 to (1 2) gives (1 2 3)

So far I've been doing (append a (list b)), which is kind of long and inelegant, so I wonder if there's a "better" way...

回答1:

Are you building a list piecemeal, an item at a time? If so, the idiomatic way to do this is to build the list backward, using cons, and then reversing the final result:

(define (map-using-cons-and-reverse f lst)
  (let loop ((result '())
             (rest lst))
    (if (null? rest)
        (reverse result)
        (loop (cons (f (car rest)) (cdr rest))))))

Alternatively, if your list-building is amenable to a "right-fold" recursive approach, that is also idiomatic:

(define (map-using-recursion f lst)
  (let recur ((rest lst))
    (if (null? rest)
        '()
        (cons (f (car rest)) (recur (cdr rest))))))

---

The above code snippets are just for illustrating the solution approach to take in the general case; for things that are directly implementable using fold, like map, using fold is more idiomatic:

(define (map-using-cons-and-reverse f lst)
  (reverse (foldl (lambda (item result)
                    (cons (f item) result))
                  '() lst)))

(define (map-using-recursion f lst)
  (foldr (lambda (item result)
           (cons (f item) result))
         '() lst))

回答2:

How frequent do you have to append to the end?

If you want to do it a lot (more than cons'ing to the front), then you are doing it wrong. The right way is to flip things around: think that cons put things to the back, first retrieves the last element, rest retrieves everything but last, etc. Then, you can use list normally.

However, if you want to put things to the end of the list as frequent as to cons things to the front, then this is the best that you can do with one list. You could write a function to wrap what you consider "inelegant". Traditionally it's called snoc (backward cons)

(define (snoc lst e) (append lst (list e)))

Or if you prefer to implement the whole thing by yourself:

(define (snoc lst e)
  (cond
    [(empty? lst) (list e)]
    [(cons? lst) (cons (first lst) (snoc (rest lst) e))]))

Note that both approaches have the same time complexity: O(n) where n is length of the list.

But if you want it to be efficient, you can use a data structure called double-ended queue, which is very efficient (constant time per operation). See http://www.westpoint.edu/eecs/SiteAssets/SitePages/Faculty%20Publication%20Documents/Okasaki/jfp95queue.pdf for more details.