Implementing map using foldr in Emacs Lisp

Question

I'm starting to learn Emacs Lisp and as an exercise I'm trying to implement map using foldr. The code is the following:

(defun foldr (f z l)
   (if (null l)
       z
       (funcall f (car l)
                  (foldr f z
                           (cdr l)))))

(defun map (f l)
   (foldr (lambda (x z)
            (cons (funcall f x) z))
          nil
          l))

However, when I try to evaluate, for example,

(map (lambda (x) (+ x 1)) '(1 2 3 4 5))

in Emacs with eval-last-sexp (after evaluating both foldr and map), the result is the following:

Debugger entered--Lisp error: (wrong-number-of-arguments (lambda (x z) (cons (funcall f x) z)) 1)
  (lambda (x z) (cons (funcall f x) z))(5)
  funcall((lambda (x z) (cons (funcall f x) z)) 5)
  (cons (funcall f x) z)
  (lambda (x z) (cons (funcall f x) z))(5 nil)
  funcall((lambda (x z) (cons (funcall f x) z)) 5 nil)
  (if (null l) z (funcall f (car l) (foldr f z (cdr l))))
  foldr((lambda (x z) (cons (funcall f x) z)) nil (5))
  (funcall f (car l) (foldr f z (cdr l)))
  (if (null l) z (funcall f (car l) (foldr f z (cdr l))))
  foldr((lambda (x z) (cons (funcall f x) z)) nil (4 5))
  (funcall f (car l) (foldr f z (cdr l)))
  (if (null l) z (funcall f (car l) (foldr f z (cdr l))))
  foldr((lambda (x z) (cons (funcall f x) z)) nil (3 4 5))
  (funcall f (car l) (foldr f z (cdr l)))
  (if (null l) z (funcall f (car l) (foldr f z (cdr l))))
  foldr((lambda (x z) (cons (funcall f x) z)) nil (2 3 4 5))
  (funcall f (car l) (foldr f z (cdr l)))
  (if (null l) z (funcall f (car l) (foldr f z (cdr l))))
  foldr((lambda (x z) (cons (funcall f x) z)) nil (1 2 3 4 5))
  map((lambda (x) (+ x 1)) (1 2 3 4 5))
  eval((map (function (lambda (x) (+ x 1))) (quote (1 2 3 4 5))) nil)
  eval-last-sexp-1(nil)
  #[257 "\204\303!\207  \303!\n)B\211A  =\204\211A\211@\207" [eval-expression-debug-on-error eval-last-sexp-fake-value debug-on-error eval-last-sexp-1] 4 2471606 "P"](nil)
  ad-Advice-eval-last-sexp(#[257 "\204\303!\207 \303!\n)B\211A  =\204\211A\211@\207" [eval-expression-debug-on-error eval-last-sexp-fake-value debug-on-error eval-last-sexp-1] 4 2471606 "P"] nil)
  apply(ad-Advice-eval-last-sexp #[257 "\204\303!\207   \303!\n)B\211A  =\204\211A\211@\207" [eval-expression-debug-on-error eval-last-sexp-fake-value debug-on-error eval-last-sexp-1] 4 2471606 "P"] nil)
  eval-last-sexp(nil)
  call-interactively(eval-last-sexp nil nil)
  command-execute(eval-last-sexp)

I don't understand why this doesn't work, when the following super similar implementation in Haskell works fine:

foldr f z l = if (null l)
              then z
              else f (head l) (foldr f z (tail l))

map f l = foldr (\ x z -> (:) (f x) z) [] l

So why aren't the Lisp and Haskell programs equivalent? What's the nature of the problem in the Lisp implementation, i.e., why isn't map working?

Drew Drew · Accepted Answer · 2015-09-22T01:50:30

(setq lexical-binding t)

f is a free variable in the lambda form you pass to foldr.

With lexical binding, your example works fine:

(map (lambda (x) (+ x 1)) '(1 2 3 4 5)) ; ==> (2 3 4 5 6)

Implementing map using foldr in Emacs Lisp

1 Answers