4

次のバージョンの flatten の実行順序を正確に分類するのを手伝ってくれる人はいますか? ラケットを使用しています。

バージョン 1 はラケット自体からのものですが、バージョン 2 はより一般的ですか? 実装。

(define (flatten1 list)
  (let loop ([l list] [acc null])
    (printf "l = ~a acc = ~a\n" l acc)
    (cond [(null? l) acc]
          [(pair? l) (loop (car l) (loop (cdr l) acc))]
          [else (cons l acc)])))

(define (flatten2 l)
  (printf "l = ~a\n" l)
  (cond [(null? l) null]
        [(atom? l) (list l)]
        [else (append (flatten2 (car l)) (flatten2 (cdr l)))]))

ここで、最初の例を '(1 2 3) で実行すると、以下が生成されます。

l = (1 2 3) acc = ()
l = (2 3) acc = ()
l = (3) acc = ()
l = () acc = ()
l = 3 acc = ()
l = 2 acc = (3)
l = 1 acc = (2 3)
'(1 2 3)

2番目は次を生成します：

l = (1 2 3)
l = 1
l = (2 3)
l = 2
l = (3)
l = 3
l = ()
'(1 2 3)

実行順序が異なるようです。(loop (cdr l) acc)最初の例では、'(2 3) がすぐに印刷されるため、最初のループの前に2 番目のループが起動しているように見えます。一方、2 番目の例では、'(2 3) の前に 1 が出力されます。これは、append 内の flatten への最初の呼び出しが最初に評価されるように見えます。

私は Little Schemer を使用していますが、これらはより難しい例であり、実際に助けを借りることができます。

どうもありがとう。

4

2 に答える 2

5

実際にはあなたの質問に対する答えではありませんが（クリスはすでに優れた答えを提供しています！）、完全を期すためにflatten、これに似てflatten2いますがもう少し簡潔な実装方法があります。

(define (atom? x)
  (and (not (null? x))
       (not (pair? x))))

(define (flatten lst)
  (if (atom? lst)
      (list lst)
      (apply append (map flatten lst))))

flatten1そして、標準のラケット手順を使用して、左折りバージョンを実装する別の方法（より多くの共通点があります）：

(define (flatten lst)
  (define (loop lst acc)
    (if (atom? lst)
        (cons lst acc)
        (foldl loop acc lst)))
  (reverse (loop lst '())))
于 2012-11-25T04:22:29.110 に答える
4

主な違いは次のとおりです。

  • flatten1出力要素を (最初にcdr側面から、次に側面からcar) アキュムレータに格納することによって機能します。これは、リストが右から左に作成されるため機能するため、cdr最初にサイドで作業するのが正しいです。
  • flatten2carとのcdr辺を再帰的に平坦化し、appendそれらを ing することで機能します。

flatten1特にツリーが重い場合は高速ですcar。アキュムレータを使用すると、何があっても余分なリストのコピーがないことを意味します。一方、appendin の呼び出しflatten2により、 の左側appendがコピーされます。これは、ツリーの左側が重い場合、余分なリストのコピーが大量に発生することを意味しますcar。

要約するとflatten2、フラット化の初心者向けの実装とflatten1、より洗練されたプロフェッショナルなバージョンを検討します。私の実装である flattenも参照してください。これは と同じ原則を使用して動作しますflatten1が、使用する右折りの代わりに左折りをflatten1使用します。

(左折りのソリューションは、使用するスタック スペースが少なくなりますが、ヒープ スペースが増える可能性があります。右折りのソリューションは、より多くのスタックを使用し、通常はより少ないヒープをflatten1使用します。 )

于 2012-11-25T03:50:51.367 に答える