foldを使う

簡単にまとめると、明示的な再帰を用いるプログラミングスタイルはよろしくないと言うこと。Haskellwikiにもそう書かれている。良い関数型プログラマは再帰を用いず再帰をパターン化した高階関数を使うのだそうだ。

maoeのブログ

ということで，OnLispを少しやっている中で，remove-ifがでてきたので，foldを使って書いてみた．

(define (remove-if pred lst)
  (define (rec x acc)
    (and (not (pred x))
         (set! acc (cons x acc)))
    acc)
  (fold-right rec '() lst))

ちなみにこの前，combinationを，foldとかを使って書いてみようと思ったけれど，書けなくて結局再帰になってしまった．(コードは汚いので載せられません...)
そこで，util.combinationsを見てみると，

(define (combinations set n)
  (if (not (positive? n))
      (list '())
      (pair-fold-right
       (lambda (pr acc)
         (fold-right (cut acons (car pr) <> <>)
                     acc
                     (combinations (cdr pr) (- n 1))))
       '()
       set)))

一部再起にはなっているが，やはりfoldを使っている．permutationなどでも同じ．
リスト操作にfoldは重要で，普段からfold系の関数を使えるようにする．
(pair-foldとかは使ったことがない...)