Lispのreduceをちょっと理解した
map関数は理解しやすいけど、reduce関数とかfold関数っていまいち動作が追えなくないですか。
> (mapcar (lambda (x) (* 2 x)) '(1 2 3 4))
(2 4 6 8)
> (reduce (lambda (a x) (* a x)) '(1 2 3 4))
24
特に、引数の関数にどんなものを与えるべきなのかよく分からない。まぁこの例だったら#'*で良いくらいは分かるんですけど。
ずっとモヤモヤしてたのですが、あるときこのaが累積変数なのだと知ったら、ただの末尾再帰に見えるようになりました。
(defun product-by-recursion (list &optional (result 1))
(if (null list) ^^^^^^ accumulator
result
(product-by-recursion (cdr list) (* result (car list)))))
(defun product-by-reduction (list)
(reduce (lambda (result x) (* result x)) list :initial-value 1))
^^^^^^ accumulator!
末尾再帰に見えるようになったら、99 Lisp ProblemsのP10もreduceで解けるようになりました。
(defun encode (list)
(reverse
(reduce (lambda (result x)
(if (eql x (cadar result))
(cons (list (1+ (caar result)) (cadar result))
(cdr result))
(cons (list 1 x) result)))
list
:initial-value '())))
> (encode '(a a a a b c c a a d e e e e))
((4 A) (1 B) (2 C) (2 A) (1 D) (4 E))