パターンマッチによる再帰

CL-USER> (defmethod my-fold (f e (ls (eql nil))) e)
CL-USER> (defmethod my-fold (f e ls)
           (my-fold f (funcall f e (car ls)) (cdr ls)) )

CL-USER> (my-fold #'(lambda (x y) (cons y x)) '() '(5 4 3 2 1))
(1 2 3 4 5)

思いつきでmultimethodsでやってみたけど、Haskellほど綺麗には見えないね。
ifで書いた方がはやいか。

追記(09/01/26)

あとはこんなのとか・・・

CL-USER> (defun my-map (f ls)
           (case ls
             ((nil) nil)
             (otherwise (destructuring-bind (x . xs) ls
                          (cons (funcall f x) (my-map f xs)) ))))
MY-MAP

CL-USER> (my-map #'1+ '(1 2 3))
(2 3 4)

やっぱり微妙でございますね(´ω｀)