4

foldrとを使用して、Scheme でリストを反転する関数をどのように定義できますfoldlか?

必要なのは、Scheme で呼び出しを使用してリストを逆にする簡潔なソリューションと、定義されている呼び出しfoldlを使用した別のソリューションです。foldr

(define (foldl operation lst initial)
    (if (null? lst) initial
        (foldl operation 
               (cdr lst) 
               (operation (car lst) initial))))

と

(define (foldr operation lst initial)
    (if (null? lst) initial
        (operation 
            (car lst) 
            (foldr operation (cdr lst) initial))))

鋭い人はfoldl、各再帰ステップが呼び出されるたびに返される値が計算されるため、実装が末尾再帰であることに気付くでしょう。

このfoldr実装は末尾再帰ではありません。これは、再帰チェーンに戻された値を使用して戻り値を構築する必要があるためです。

したがって、関心のある 2 つの Scheme 実装は、次の形式である必要があります。

(define (rev1 lst)
    (foldl ___________________________

**Solution:**
(define (rev1 lst)
    (foldl cons lst '()))

と

(define (rev2 lst)
    (foldr ___________________________

**Solution 1:**
(define (rev2 lst)
    (foldr 
       (lambda (element accumulator) 
               (foldr cons accumulator (cons element '())))
       lst '())) 

**Solution 2:**
(define (rev2 lst)
    (foldr 
       (lambda (element accumulator) 
               (append accumulator (cons element '())))
       lst '()))

最終的な目標は、以下を呼び出すことができるようにすることです。

(rev1 '(1 2 3)) -> (3 2 1)
(rev2 '(1 2 3)) -> (3 2 1)

解決策は(foldl私たちの直感に基づいて) 比較的単純なものですが、foldr解決策にはおそらくもう少し検討が必要です。

この質問に似た (ただし文書化されていない) 以前の質問は、未回答またはクローズされました。

4

2 に答える 2

2

これは宿題のように思えるので、始めるためのヒントをいくつか紹介します。ケースは簡単です。foldl渡す適切な関数を見つける必要があるだけです。覚えておいてください:foldlリストを逆方向に処理する (最後の要素が最初、最初の要素が最後) として視覚化できるため、現在の要素を累積値のリスト:

(define (rev1 lst)
  (foldl <???> lst '()))

このfoldrケースは少し難しいだけですがfoldr、 がリスト内の要素を入力リストに表示されるのと同じ順序で処理することを思い出してください。繰り返しますが、呼び出す正しいプロシージャを見つける必要があります。

(define (rev2 lst)
  (foldr (lambda (e a)
           <???>)
         lst
         '()))

eどういうわけか（現在の要素）を累積値の最後に置く必要があります。aヒント: あなたはそれを見つけ、appendここlistで役に立ちます。

于 2013-11-05T01:42:34.337 に答える
1

あなたの「ソリューション」はコンパイルさrev1れません...listl

> (define (rev1 l) 
    (foldl cons l '()))
> (rev1 '(1 2 3))
(3 2 1)

あなたの場合、rev2これは本体として機能します：

> (foldr (lambda (a b) (append b (list a))) '(1 2 3) '())
(3 2 1)
于 2013-11-05T22:31:06.077 に答える