3
\$\begingroup\$

The problem is to take a list of integers and map them to another list containing those integers added to their respective position in the list.

Example runs with required outputs:

> (pos+ '(1 1 1 1))
(1 2 3 4)
> (pos+ '(7 5 1 4))
(7 6 3 7)

We are required to develop three alternate solutions. One using recursion, one using iteration, and one using mapcar.

I present my solutions below and seek comments on style, best coding conventions & habits to adopt. Also the question of which solution is preferred for this particular case arises, including justification for the choice.

Observations (on which I seek discussion) are included as comments in the code.

;;; (1) Using recursion
(defun pos+ (lst)
  (pos-helper lst 0))
(defun pos-helper (lst n)
  (if (null lst)
      nil
      (cons (+ (first lst) n)
            (pos-helper (rest lst) (+ n 1)))))
;; Elegant, as recursion often is, but not a tail call (cant abandon stack frame), 
;; hence less efficient at scale (which may not matter).

;;; (2) With iteration
(defun pos+2 (lst)
  (do ((i 0 (+ i 1)))
      ((>= i (length lst)) lst)
      (setf (nth i lst) (+ (nth i lst) i))))
;; Fewer lines, but i have a feeling of disappointment to be learning lisp
;; and not be using a functional style. Q. Is that intuition well-placed?

;;; (3) With mapcar
(defun pos+3 (lst)
  (mapcar #'(lambda (x y) (+ x y))
          lst
          (range (length lst))))

;; This would be my 'most beautiful' solution except for one problem.
;; Could not find any built in range function. I found range [footnote 1] 
;; and pasted it here. The syntax doesn't look anything like CL to me!
(defun range (max &key (min 0) (step 1))
   (loop for n from min below max by step  ;; did the lisp alien write this?! :)
      collect n))

link to range function used above

\$\endgroup\$
5
\$\begingroup\$

For loop you can see the excellent book by P. Seibel “Practical Common Lisp”, available on-line, in particular chapter 7 and chapter 22.

Let’s start from the last function: the idea is ok, we can just simplify the function noting that (lambda (x y) (+ x y)) is nothing more than the original +:

(defun pos+3 (lst)
  (mapcar #'+ lst (range (length lst))))

For the first function, since an helper function is introduced, it could as well be used for tail-recursion, instead of normal recursion:

(defun pos-helper (lis n acc)
  (if (null lis)
      (reverse acc)
      (pos-helper (rest lis) (1+ n) (cons (+ (first lis) n) acc))))

(defun pos+ (lis)
  (pos-helper lis 0 nil))

where acc accumulates the result, which at the end must be reversed. Note that certain Common Lisp compilers transform the function in an iterative loop, so I do not know if this would be considered recursive. In that case, your version is ok (but note the idiomatic use of (1+ expression) instead of (+ expression 1)).

Then, for the second function, of course a loop version is much more readable (even if it is not so lispy :) :

(defun pos+2 (lis)
  (loop for i from 0 
        for x in lis
        collect (+ x i)))

If you prefer more parentheses, here is a variant (without modifying the original list):

(defun pos+2 (lis)
  (let ((result nil))
    (do ((i 0 (1+ i))
         (y lis (cdr y)))
        ((null y) (reverse result))
      (push (+ (car y) i) result))))

A final note about efficiency: the function pos3 is the less efficient one since it must generate a new list with the same length as the original one (and so the list must be scanned twice, in addition to doubling the memory footprint of the program). With a simple trick we could use mapcar and avoid creating a new list:

(defun pos+3 (lis)
  (let ((index -1))
    (mapcar (lambda (x) (+ x (incf index))) lis)))
\$\endgroup\$
  • \$\begingroup\$ Thank you @Renzo! May I ask a stylistic question on the 1+ function: I do want to use it and probably will, but first impression is it seems syntactically egregious, appearing to imply infix notation. Does one just get used to the functions 1+ & 1-, or is there some mitigating reason for them to be named that way which does make them aesthetically 'ok'? e.g. obviously 'inc' & 'dec' are just one more character, and don't 'look like a typo', which to me those do in a way, at least right now! \$\endgroup\$ – mwal Mar 19 at 13:13
  • 1
    \$\begingroup\$ I confess at first using 1+ and 1- was not always immediate for me, but after some time I was quite used to them. Maybe inc and dec were not used since they look too similar to incf and decf, that have a very different meaning, or maybe it was considered funny to prove that in CommonLisp symbols can have very peculiar names! Modern compiler optimization techniques of course make useless such specific operators, however, and I think they are still used just because of habit. \$\endgroup\$ – Renzo Mar 19 at 13:55
  • \$\begingroup\$ Your final example is something I now realise I'd wanted to express but didn't know how get an incrementing value into the function passed to the map function. Mutable state 'to the rescue' (?). (is this barski's "lisp alien" rearing its hand-trunk for us? :)) In sum, maybe that final three liner wins hands down for compactness, of all the versions we've considered. What do you think? So to conclude: Q. Are there any drawbacks of coding in this way? (i do yearn for more recursion on aesthetic grounds, but the mapcar with state version looks like it could be the winner :)) \$\endgroup\$ – mwal Mar 19 at 16:01
  • 1
    \$\begingroup\$ @mwal, yes, I love the barki's cartoon too. For the best version: for readability I am oriented towards the loop solution, but the last one is surely a good second for me. After so many years of programming, I tend to see recursion as just another tool to use when needed: the elegance for me is mostly a mix of readability, conciseness and efficiency. \$\endgroup\$ – Renzo Mar 20 at 9:21
4
\$\begingroup\$

General style remarks

  • lst is more of a Scheme idiom, in Common Lisp you don't eat vowels but write directly list if your variable is a list (to be honest, some CL standard functions have weird names too).
  • "Functional = Elegant" is somewhat true, but don't let purity blind you into ignoring perfectly good alternative approaches; it is often reasonable to have a purely functional interface implemented with local mutable state, for example. Building a fresh list and reversing it is a pure functional way to implement map, but that's not how you implement an efficient map function.

Tail-call elimination

For solution 1, you define a helper function; you can use a tail-recursive call if you add an accumulator parameter to hold the reversed result list. For example:

(defun pos+helper (list result position)
  (if list
      (pos+helper (rest list)
                  (cons (+ (first list) position) result)
                  (1+ position))
      result))

Note however that Lisp being dynamic, it is possible that you can at a later point redefine pos+helper to be another function, which prevents the compiler to automatically transform it as a loop. Consider for example the case where you want to trace an existing function: the original function is likely to be instrumented by wrapping it into another function, and then the recursive call is calling the resulting wrapper.

Whether I compile the above function with (optimize speed) declaration or not, I obtain different outputs with disassemble. When speed is not optimized, the recursive call is effectively a CALL, which grows the stack but allows for a redefinition of pos+helper. A simpler example:

(defun tester ()
  (sleep 2)
  (tester))

(ql:quickload :bordeaux-threads)
(bt:make-thread #'tester :name "tester")

I created a thread which calls tester, which contains a call to sleep to slow down the infinite recursion, to avoid stack overflows.

USER> (find "tester" (bt:all-threads) :test #'string= :key #'bt:thread-name)
#<SB-THREAD:THREAD "tester" RUNNING {100CC049F3}>

The thread is found in the list of all threads, which means it is alive and the function is effectively recursing infinitely. Now, if I redefine tester:

(defun tester () :done)

Then the thread is stopped:

USER> (find "tester" (bt:all-threads) :test #'string= :key #'bt:thread-name)
NIL

This is obviously implementation dependant, but if I declare the function to be optimized for speed, no amount of redefinition changes the behaviour of the function under test.

You have better control of this if you define your helper function locally:

(defun pos+ (list)
  (labels ((recurse (list result position)
             (if list
               (recurse (rest list)
                        (cons (+ (first list) position) result)
                        (1+ position))
               result)))
    (nreverse (recurse list nil 0))))

First, it hides the auxiliary function, which is after all an implementation detail; but most importantly, since the body of a function is static in the sense that you do not redefine parts of it at runtime, the compiler is able to infer that recurse is never going to change, and can do the tail-call elimination without additional hints (most compilers can do that easily, except on platforms like Java (ABCL) where this is not possible).

(opinion: tail-call elimination breaks the elegance of the purely functional approach by making you rearrange parameters to satisfy an implicit, particular case where calls can be converted as jumps; in other words, this is a hack. In languages that mandates tail-call elimination, this is less of a hack, but not necessarily elegant either.)

The portable way to implement a loop is to write a loop or higher-level functions.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.