0

Clojureでディープリバースを実装しようとしています。lst が (1 (2 (3 4 5)) (2 3)) の場合、((3 2) ((5 4 3) 2) 1) を返す必要があります。
これは私がこれまでに持っているものです:

defn dRev [lst]
    ( if (= lst ())
        nil
        ( if (list? (first lst))
            ( dRev (first lst) )
            ( concat
                ( dRev (rest lst)) (list (first lst))
            )
        )
   )
)

ただし、私の実装は、ネストされたリストが最後の要素である場合にのみ機能しますが、結果のリストもフラット化されます。

例: (dRev '(1 2 (3 4)) は (4 3 2 1) を返します。
そうでない場合、例: (dRev '(1 (2 3) 4)) は (3 2 1) のみを返します。

しばらくの間、このレンガの壁にぶつかりましたが、コードの問題を見つけることができません。
誰でも私を助けてもらえますか？

4

3 に答える 3

7

clojure.walk/postwalkもう 1 つの回答は、コレクションのすべての要素に関数を深く適用する問題を一般化する関数を使用するため、Clojure でのディープ リバースの可能な限り最良の実装を提供しました。ここでは、代わりに、投稿した実装の問題について説明します。

第 1 に、通常とは異なる書式設定により、何が起こっているのかを特定するのが難しくなります。これは、固定書式設定と同じです。

(defn dRev [lst]
  (if (= lst ())
    nil
    (if (list? (first lst))
        (dRev (first lst))
        (concat (dRev (rest lst))
                (list (first lst))))))

次に、動作をまだ修正していない他のいくつかの小さな修正:

  • 関数名を Clojure の規則に準拠するように変更します (キャメルケースの代わりにハイフンを使用)。
  • collの代わりにlst、コレクション パラメーターに通常の Clojure の既定の名前を使用します。
  • empty?空のコレクションをチェックするために使用し、
  • ()他の種類の seq の代わりにリストを返したいことがわかっているため、デフォルトの場合に戻ります。
  • リストだけでなく、コレクションを逆にすることもできるため、coll?代わりに使用します。list?

(本当にリストだけを逆にして他のすべてのコレクションをそのままにしたい場合は、最後の変更を元に戻します。)

(defn d-rev [coll]
  (if (empty? coll)
    ()
    (if (coll? (first coll))
        (d-rev (first coll))
        (concat (d-rev (rest coll))
                (list (first coll))))))

これで、フォーマットの修正により、実装の主な問題が明らかになりました。再帰呼び出し ( (d-rev (first coll))resp. (dRev (first lst))) では、その再帰の結果のみを返しますが、リストの残りを処理するのを忘れています。基本的に、必要なことは、コレクションの残りの部分を常に同じように処理し、最初の要素がリスト resp であるかどうかに基づいて、最初の要素の処理方法のみを変更することです。コレクションかどうか:

(defn d-rev [coll]
  (if (empty? coll)
    ()
    (concat (d-rev (rest coll))
            (list (if (coll? (first coll))
                    (d-rev (first coll))
                    (first coll))))))

これは実用的なソリューションです。

concatただし、すべての要素のリストを完全に再構築するため、非常に非効率的です。非常に簡単な末尾再帰アルゴリズムを使用することで、はるかに良い結果を得ることができます (要素の順序を逆にするシーケンスの末尾再帰が自然であるため)。

(defn d-rev [coll]
  (loop [coll coll, acc ()]
    (if (empty? coll)
      acc
      (recur (rest coll)
             (cons (if (coll? (first coll))
                     (d-rev (first coll))
                     (first coll))
                   acc)))))

最後の提案として、より高いレベルで問題を解決することにより、他の回答からの解決策の途中にある解決策がありますが、コア関数のみを使用し、シーケンスのすべての要素に関数reverseをmap適用しますが、深くはしません-それ自体を再帰します。

(defn deep-reverse [coll]
  (reverse (map #(if (coll? %) (deep-reverse %) %) coll)))
于 2013-10-03T12:26:37.193 に答える
5

clojure.walk/postwalkとで書いているものを構築できますclojure.core/reverse。これは、ツリー入力の深さ優先トラバーサルを実行し、見つかったすべての seq を逆にします。

(defn dRev [lst]
  (clojure.walk/postwalk #(if (seq? %) (reverse %) %) lst))
于 2013-10-03T03:37:31.590 に答える