recursive definition of map in common lisp

Question

I was expecting the Scheme approach:

(defun mmap (f xs)
  (if (equal xs NIL)
      '()
      (cons (f (car xs)) (mmap f (cdr xs)))))

but i get a compiler warning

;Compiler warnings for ".../test.lisp" :
;   In MMAP: Undefined function F

I can see that I need to make the compiler aware that f is a function. Does this have anything to do with #'?

@lurker if you stick that as an answer I can mark it as accepted. Thanks! — beoliver, Aug 20 '14 at 20:57
Please note that your `mmap` definition is _not_ tail-recursive, so it is unlikely to be compiled to a loop and thus might overflow the stack on relatively small lists. — sds, Aug 20 '14 at 21:28
@sds ...Am far too used to Haskell - `| map _ [] = [] | map f (x:xs) = f x : map f xs |` — beoliver, Aug 20 '14 at 21:54

Sylwester · Accepted Answer · 2014-08-20T22:27:27.427

Common Lisp is a LISP2. It means variables that are in the first element of the form is evaluated in a function namespace while everything else is evaluated from a variable namespace. Basically it means you can use the same name as a function in your arguments:

(defun test (list)
  (list list list))

Here the first list is looked up in the function namespace and the other two arguments are looked up in the variable namespace. First and the rest become two different values because they are fetched from different places. If you'd do the same in Scheme which is a LISP1:

(define (test list)
  (list list list))

And pass a value that is not a procedure that takes two arguments, then you'll get an error saying list is not a procedure.

A function with name x in the function namespace can be fetched from other locations by using a special form (function x). Like quote function has syntax sugar equivalent so you can write #'x. You can store functions in the variable namespace (setq fun #'+) and you can pass it to higher order functions like mapcar (CL version of Scheme map). Since first element in a form is special there is a primitive function funcall that you can use when the function is bound in the variable namespace: (funcall fun 2 3) ; ==> 5

(defun my-mapcar (function list)
  (if list
      (cons (funcall function (car list))
            (my-mapcar function (cdr list)))
      nil))

(my-mapcar #'list '(1 2 3 4)) ; ==> ((1) (2) (3) (4))

A version using loop which is the only way to be sure not to blow the stack in CL:

(defun my-mapcar (function list)
  (loop :for x :in list 
        :collect (funcall function x)))

(my-mapcar #'list '(1 2 3 4)) ; ==> ((1) (2) (3) (4))

Of course, mapcar can take multiple list arguments and the function map is like mapcar but it works with all sequences (lists, arrays, strings)

;; zip
(mapcar #'list '(1 2 3 4) '(a b c d)) ; ==> ((1 a) (2 b) (3 c) (4 d))

;; slow way to uppercase a string
(map 'string #'char-upcase "banana") ; ==> "BANANA"

functions in CL that accepts functions as arguments also accept symbols. Eg. #'+ is a function while '+ is a symbol. What happens is that it retrieves #'+ by fetching the function represented by + in the global namespace. Thus:

(flet ((- (x) (* x x)))
  (list (- 5) (funcall #'- 5) (funcall '- 5))) ; ==> (25 25 -5)

Trivia: I think the number in LISP1 and LISP2 refer to the number of namespaces rather than versions. The very first LISP interpereter had only one namespace, but dual namespace was a feature of LISP 1.5. It was he last LISP version before commercial versions took over. A LISP2 was planned but was never finished. Scheme was originally written as a interpreter in MacLisp (Which is based on LISP 1.5 and is a LISP2). Kent Pittman compared the two approaches in 1988.

@ThemanontheClaphamomnibus You're welcome. I think Haskell is probably closer to Scheme but I do love some CL features not found in Scheme. — Sylwester, Aug 20 '14 at 22:35

recursive definition of map in common lisp

1 Answers1