3

解決したい問題のコードを作成しようとすると問題が発生します。こんなふうになります：

~ 目標: ネストされたリストを 1 つの数値にフラット化する

  1. オブジェクトがリストの場合、リストをそのアトムの合計に置き換えます。
  2. ネストされたリストでは、最初に最も内側のリストを平坦化し、そこから作業します。

例：

  (CONDENSE '(2 3 4 (3 1 1 1) (2 3 (1 2)) 5))

       (2 3 4 (6) (2 3 (3)) 5)

       (2 3 4 (6) (8) 5)

       (28) 

  => 28

この問題に対してフラット化リスト機能を実装しようとしましたが、最終的には次のようになりました。

(defun condense (lst)
  (cond
    ((null lst) nil)
    ((atom lst) (list lst)))
    (t (append  (flatten (apply #'+ (cdr lst))))))

しかし、それは私にエラーを与えます:(

誰かが私の処理/コードの何が問題なのか説明してもらえますか? どうすれば改善できますか？

更新: 2012 年 6 月 5 日

(defun condense(lxt)
  (typecase lxt
    (number (abs lxt))
    (list
        (if (all-atoms lxt)
           (calculate lxt)
           (condense (mapcar #'condense lxt))))))

ですから、このコードでは、私の真意が示されています。calculateリストの値に基づいて計算を実行する関数があります。毎回同じ操作とは限りません。また、数値の絶対値を返していることも承知しています。数値自体を返す別の方法が見つからなかったため、これを行いました。が数値の場合、数値を返す方法を見つける必要がありますlxt。これは、単一の数値を計算するまで無限にループする 1 つの方法であるためです。注: この関数はフラット化関数を実装しておらず、そこから何かを使用することもありません。

4

5 に答える 5

2

関数が既にあると想像してください。それは何を得るのですか？それは何を生み出す必要がありますか？

与えられたアトムは何を返しますか? アトムの単純なリストが与えられた場合、何を返す必要がありますか?

(defun condense (x)
  (typecase x
    (number  
       ; then what?
       (condense-number x))
    (list
       ; then what?
       (if (all-atoms x)
         (condense-list-of-atoms x) ; how to do that?
         (process-further-somehow
            (condense-lists-inside x))))
    ; what other clauses, if any, must be here?
    ))

何をしなければなりcondense-lists-insideませんか？あなたの説明によると、内部のネストされたリストをそれぞれnumberに凝縮し、アトムをそのままにしておくことです。したがって、数字のリストが残ります。どういうわけかそれをさらに処理するために、私たちはすでに関数を「持っています」、そうですか？condense-list-of-atoms

さて、実装方法はcondense-lists-inside？簡単だ、

(defun condense-lists-inside (xs)
  (mapcar #'dowhat xs))

何をしますか？もちろんcondense！覚えておいてください、私たちはすでにそれを持っていると想像しています. 意図されたものを手に入れる限り、意図した通りに生産する。つまり、アトムまたはリスト (内部にリストがネストされている可能性があります) を指定すると、 numberが生成されます。

では、空欄を埋めて単純化してください。特に、all-atomsチェックが本当に必要かどうかを確認してください。

編集:実際にtypecaseは、NIL を LIST として扱うため、使用は残念な選択でした。代わりに「ゼロ値」を返すために、NIL を別の方法で処理する必要があります。したがって、通常の(cond ((null x) ...) ((numberp x) ...) ((listp x) ...) ... )構成を使用することをお勧めします。

新しいコードについて: エラーが発生しました: の後に返されたアトムのリストを処理するために(mapcar #'condense x)、それを行う関数calculateがあり、それ自体まで戻る必要はありませんcondense。そこに置き換えると、チェックがまったく必要ないcalculateことが明らかになります。all-atomsそれは、コードの開発を容易にするための教育的な装置に過ぎませんでした。:)正確さの目​​標を達成した後、それらを単純化して、開発時に余分な選択をしても問題ありません!

ただし、all-atomsチェックを削除すると、要件 2 が壊れます。すると以下のように計算が進みます

(CONDENSE '(2 3 4 (3 1 1 1) (2 3 (1 2)) 5))
==
(calculate (mapcar #'condense '(2 3 4 (3 1 1 1) (2 3 (1 2)) 5)))
== 
(calculate (list 2 3 4 (condense '(3 1 1 1)) (condense '(2 3 (1 2))) 5))
== 
(calculate (list 2 3 4 (calculate '(3 1 1 1)) 
                         (calculate (list 2 3 (calculate '(1 2)))) 5))
== 
(calculate (list 2 3 4 6 (calculate '(2 3 3)) 5))
== 
(calculate (list 2 3 4 6 8 5))
==
28

つまり、最も深くネストされたレベルからではなく、左から右に進みます。入れ子になったリストをツリー (ツリー) として想像すると、これはツリーの最も深い左隅から右へと「むしゃむしゃ」になります。チェック付きのコードはall-atoms、レベルアップによって厳密に続行されます。

したがって、最終的な単純化されたコードは次のとおりです。

(defun condense (x)
  (if (listp x)
    (reduce #'+ (mapcar #'condense x))
    (abs x)))

備考:リダクション シーケンスの最後の図を見ると、引数ツリーの各ノードを計算アプリケーションに置き換えるという明確な図が浮かび上がります。これは、そのままの単純なリストではなく、ツリーに対して行われる折りたたみの明確なケースです。reduce

これは、「car-cdr 再帰」と呼ばれるもので直接コーディングできます。各セルを、セルのコンポーネントへの再帰呼び出しの 2 つの結果に対するcons結合関数のアプリケーションに置き換えます。fcarcdr

(defun condense (x) (reduce-tree x #'+ 0))
(defun reduce-tree (x f z)
  (labels ((g (x)
            (cond
             ((consp x) (funcall f (g (car x)) (g (cdr x))))
             ((numberp x) x)
             ((null x) z)
             (T (error "not a number")))))
    (g x)))

ご覧のとおり、このバージョンは非常に再帰的であり、あまり良くありません。

于 2012-06-05T08:12:22.693 に答える
2

これは宿題ですか？もしそうなら、そのようにマークしてください。いくつかのヒント:

  1. の空のリストの「凝縮」はnilよろしいですか? (多分あなたは数を返す必要がありますか?)
  2. condensation1 つの要素の がリストであると確信していますか? (多分あなたは数を返す必要がありますか?)
  3. condensation最後のケースの がリストであると確信していますか? （数字を返すべきではありませんか）？

要するに、返される値がすべてリストである場合、どのようcondenseに返されるのでしょうか?28

于 2012-06-05T07:51:41.227 に答える
0

ここに、発生したエラーの説明を追加しました。実際には、問題の解決に近づいており、もう少し努力すれば、問題を正しく解決できます。

; compiling (DEFUN CONDENSE ...)

; file: /tmp/file8dCll3
; in: DEFUN CONDENSE
;     (T (APPEND (FLATTEN (APPLY #'+ (CDR LST)))))
; 
; caught WARNING:
;   The function T is undefined, and its name is reserved 
;   by ANSI CL so that even
;   if it were defined later, the code doing so would not be portable.
; 
; compilation unit finished
;   Undefined function:
;     T
;   caught 1 WARNING condition
;STYLE-WARNING: redefining CONDENSE in DEFUN

(defun condense (lst)
  (cond
    ((null lst) nil)
    ((atom lst) (list lst)))
  ;.------- this is a function call, not a condition
  ;|         (you closed the parens too early)
  (t (append  (flatten (apply #'+ (cdr lst))))))

;; Argument Y is not a NUMBER: (3 1 1 1)
;;    [Condition of type SIMPLE-TYPE-ERROR]

(defun condense (lst)
  (cond
    ((null lst) nil)
    ((atom lst) (list lst));             .-- not a number!
    ;You are calling #'+ -------.        |
    ;on something, which        |  '(3 4 (3 1 1 1) (2 3 (1 2)) 5)
    ; is not a number.          |   |
    (t (append  (flatten (apply #'+ (cdr lst)))))))

;; You probably wanted to flatten first, and then sum

(defun condense (lst)
  (cond
    ((null lst) nil);          .--- returns just the 
    ((atom lst) (list lst));  /     atom 28, you can
    ;  .---------------------/      just remove it.
    (t (append (apply #'+ (flatten lst))))))

;; Now, you are lucky that append would just return the 
;; atom if it's not a list

(defun condense (lst)
  (cond
    ((null lst) nil)
    ((atom lst) (list lst))
    (t (apply #'+ (flatten lst)))))

;; Again, you are lucky because (apply can take enough arguments
;; while your list is reasonably small - this will not always be
;; the case, that is why you need to use something more durable,
;; for example, reduce.

(defun condense (lst)
  (cond
    ((null lst) nil)
    ((atom lst) (list lst))
    (t (reduce #'+ (flatten lst)))))

;; Whoa!

(condense '(2 3 4 (3 1 1 1) (2 3 (1 2)) 5))

これはすべて、flatten関数が実際に機能することを前提としています。

于 2012-06-05T12:07:03.207 に答える
0

タスク:ネストされたリストでは、最初に最も内側のリストを平坦化し、そこから作業します

sum
   flatten lists

和用ではREDUCEあり ませ んAPPLY.

フラット化リストの場合、ループが必要です。Lisp はすでに特殊なマッピング関数を提供しています。

もう少し高度: への呼び出しによって、合計と平坦化の両方を行うことができますREDUCE。

APPLY、REDUCE などの高階関数を使用せずに再帰を書き留めることもできます。これはもう少し手間がかかります。

于 2012-06-05T08:28:10.010 に答える
0

あなたの Lisp がすでに実装flattenしてreduceいる機能 (ここで使用する Clojure など) の場合は、次のようにすることができます。

user=> (defn condense [l] (reduce + 0 (flatten l)))
#'user/condense
user=> (condense [1 [2 [[3 4] 5]]])
15
user=>

それができない場合、これらの関数の単純な実装は次のようになります。

(defn flatten [l]
  (cond (nil?  l) l
        (coll? l) (let [[h & t] l]
                    (concat (flatten h) (flatten t)))
        true      [l]))

と：

(defn reduce [op initial-value [h & t]]
  (if (nil? t)
    (op initial-value h)
    (op initial-value (reduce op h t))))

ただし、使用している特定の Lisp のセマンティクスを必ず確認してください。reduceまた、 andを実装している場合はflatten、明確さを維持するために、それらを末尾再帰にすることをお勧めします。

Common Lisp では、次のようにします。

(defun flatten (l)
    (cond ((null l) l)
          ((atom l) (list l))
          (t        (append (flatten (car l))
                            (flatten (cdr l))))))

reduce の代わりに apply を使用します。

(defun condense (l) (apply #'+ (flatten l)))
于 2012-06-05T13:30:04.227 に答える