5

foldrラケットでの 2 つの素朴な実装を提示します。

この最初のものは適切な末尾呼び出しがなく、大きな値の場合に問題がありますxs

(define (foldr1 f y xs)
  (if (empty? xs)
      y
      (f (car xs) (foldr1 f y (cdr xs)))))

(foldr1 list 0 '(1 2 3))
; => (1 (2 (3 0))

この 2 番目のものは、継続を伴う補助関数を使用して適切なテール コールを実現し、大きな値で安全に使用できるようにします。xs

(define (foldr2 f y xs)
  (define (aux k xs)
    (if (empty? xs)
        (k y)
        (aux (lambda (rest) (k (f (car xs) rest))) (cdr xs))))
  (aux identity xs))

(foldr2 list 0 '(1 2 3))
; => (1 (2 (3 0)))

見てみるracket/controlとラケットは一流の継続に対応していることが分かります。andをfoldr使用して 2 番目の実装を表現することが可能/有益であるかどうか疑問に思っていました。しばらくいじっていたら、脳が裏返しになってしまいました。shiftreset

答えがあれば十分な説明を提供してください。私はここで大局的な理解を求めています。

4

1 に答える 1