5

数字のリストが昇順であるかどうかを判断するために、ラケットに2つの異なる関数を記述しました。

(define (ascending list)
  (if (<= (length list) 1)
      #t
      (and (< (car list) (car (cdr list))) (ascending (cdr list)))))

(define (ascending-tail list)
  (ascending-tail-helper #t list))

(define (ascending-tail-helper prevBool rest)
  (if (<= (length rest) 1)
      prevBool
      (ascending-tail-helper (and prevBool (< (car rest) (car (cdr rest)))) (cdr rest))))

最初の昇順が末尾再帰であるかどうかを判断するのに最も苦労したので、末尾再帰であると信じているものを使用して書き直しました。

最初の引数が末尾再帰ではないと遡及的に信じる理由は、再帰の各レベルで、関数がブール式を評価する前に、「and」ステートメントの2番目の引数が戻るのを待っているためです。逆に、ascending-tail-helperの場合、再帰呼び出しを行う前に、より少ない式を評価することができます。

これは正しいですか、それとも私は以前よりもさらに混乱しましたか？

4

4 に答える 4

7

DrRacketは、コールがテールポジションにあるかどうかを判断するのに役立ちます。「構文チェック」ボタンをクリックします。次に、マウスポインタを問題の式の左括弧に移動します。あなたの例では、私はこれを取得します：

ここに画像の説明を入力してください

紫色の矢印は、式がテール位置にあることを示しています。

マニュアルから：

末尾呼び出し：それを囲むコンテキストに対して（構文的に）テール位置にあるサブ式は、テール式からその周囲の式に薄紫色の矢印を描くことによって注釈が付けられます。

于 2012-10-17T11:49:29.930 に答える
6

正解です。最初のバージョンでは再帰呼び出しはに戻りますがand、2番目のバージョンでは再帰呼び出しは末尾呼び出しです。

ただし、andこれはマクロであり、通常はif

(define (ascending list)
  (if (<= (length list) 1)
      #t
      (if (< (car list) (car (cdr list)))
          (ascending (cdr list))
           #f)))

これは末尾再帰です。

于 2012-10-17T00:25:56.373 に答える
0

関数がテール位置にあるための要件の1つは、その戻り値が変更や検査なしで親関数の戻り値として使用できることです。つまり、親関数は、テール位置ステートメントを評価した後、すぐに戻ることができるはずです。

最初の出現時に、最初の関数は昇順の戻り値を検査します。昇順の値を返すのではなく、それから派生した値を返すようです。 ただし、R5RS仕様の関連セクションによると、andステートメントの最後の式はテール位置にあります。（私がきちんと目覚めているとき、私はこれを知っています）

だからあなたは間違っています。

http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-ZH-6.html#%_sec_3.5

（注：私の最初の急いで答えを修正するために編集されました）。

于 2012-10-17T00:26:39.983 に答える
0

テールポジションに関するラケットのドキュメントによると、テールポジションにあるものとそうでないものをチェックする場所は、特定のフォームのドキュメントです。

テール位置の仕様は、計算の漸近的なスペース消費についての保証を提供します。一般に、テール位置の指定は、のような各構文形式に対応しifます。

ラケットのドキュメントと言う（強調が追加されました）：

(and expr ...)

exprsが指定されていない場合、結果は#tになります。

単一のexprが指定されている場合、それはテール位置にあるため、および式の結果はexprの結果になります。

それ以外の場合は、最初のexprが評価されます。#fが生成される場合、and式の結果は#fになります。それ以外の場合、結果はand式と同じになり、残りのexprsは元のフォームに対してテール位置になります。

于 2015-11-17T18:11:41.593 に答える