2

我有一个列表列表和一个值。我的目标是一个新的列表列表，其中的值（新的第一项）与谓词匹配的第一个列表（例如 > 到列表的第一项）。如果没有列表与谓词匹配，我希望我的值在列表末尾“开始”一个新列表。

if my list is: ['(2 3 4) '(4 5 6 7) '(5 6 7)]
and my value: 3
and my predicate: (comp (partial < my-value) first)
then my result should be: ['(2 3 4) '(3 4 5 6 7) '(5 6 7)]

if my value was: 10
my result should be: ['(2 3 4) '(4 5 6 7) '(5 6 7) '(10)]

这个问题让我感到困惑，因为我的命令式思维一直告诉我它应该是多么容易，但我找不到一个简单的（好吧，说实话：任何）解决方案。这是我迄今为止的尝试：

(defn add-to-first-list-that-matches [func value]
  (loop [result []
         remaining-lists list-of-lists
         value-to-add value]
    (if (empty? remaining-lists)
      result
      (let [current-list (first remaining-lists)
            value-matches? (func value-to-add current-list)
            new-list (if value-matches? (conj value-to-add current-list) current-list)]
        (recur (conj new-list result)
               (rest remaining-lists)
               (if-not value-matches? value-to-add nil))))))

（它崩溃了）请用一些 clojure 表达式魔法启发我:)

顺便提一句。我想将其作为最长递增子序列问题的一部分来解决。

4

4 回答 4

4

这使用循环递归。

(defn add-to-ll
  [ll pred value]
  (loop [[current & unprocessed] ll
         processed []]
    (cond
     (pred current) (concat processed
                            [(cons value current)]
                            unprocessed)
     (empty? unprocessed) (concat processed
                                  [current]
                                  [[value]])
     :else (recur unprocessed
                  (conj processed current)))))


 (def l-l1 [[2 3 4] [4 5 6 7] [5 6 7]])
 (add-to-ll l-l1 (comp (partial < 10) first) 10)
 => ([2 3 4] [4 5 6 7] [5 6 7] [10])

 (add-to-ll l-l1 (comp (partial < 3) first) 3)
 => ([2 3 4] (3 4 5 6 7) [5 6 7])

你也可以使用 split-with

(defn add-to-ll
  [ll pred value]
  (let [[first-lists [to-change & rest-lists]] (split-with (complement pred) ll)]
    (if to-change
      (concat first-lists [(cons value to-change)] rest-lists)
      (concat ll [[value]]))))

性能方面，第一个解决方案应该运行得更快一些。

于 2013-07-30T13:07:39.430 回答
3

Ye olde 懒惰序列：

(defn add-to-first-match
  [pred x coll]
  (lazy-seq
    (if-let [s (seq coll)]
      (let [fst (first s)]
        (if (pred fst)
          (cons (conj fst x) (rest s))
          (cons fst (add-to-first-match pred x (rest s)))))
      (cons (list x) nil))))

注意：可以进一步提取list到参数中并允许例如vector作为元素构造函数。

于 2013-07-30T13:58:19.343 回答
1

这是我尝试使用 reduce 更简洁地回答的尝试：

(defn add-to-first-list-that-matches
  [value lists]
  (let [pred (comp (partial < value) first)
        [found result] (reduce (fn [[found result] el]
                                 (if (and (not found) (pred el))
                                   [true (conj result (cons value el))]
                                   [found (conj result el)]))
                               [false []]
                               lists)]
    (if found
      result
      (conj result (list value)))))

我在 reduce 中使用向量的习语来携带多个值（一个布尔值，表示是否找到匹配项，以及我们正在构建的修改后的数据结构）。我还能够将各种条件组合成一个 if 每个元素，加上一个最终的后置条件，而不是嵌套条件或多分支条件。

以下是它与您的示例一起使用的方式：

user> (add-to-first-list-that-matches 3 ['(2 3 4) '(4 5 6 7) '(5 6 7)])
[(2 3 4) (3 4 5 6 7) (5 6 7)]
user> (add-to-first-list-that-matches 10 ['(2 3 4) '(4 5 6 7) '(5 6 7)])
[(2 3 4) (4 5 6 7) (5 6 7) (10)]
于 2013-07-30T21:16:30.307 回答
1 
(defn find-index
  "find index of the first item in s matching predicate `pred`"
  [pred s]
  (first (keep-indexed (fn [index item]
                         (if (pred item)
                           index
                           nil))
                       s)))

(defn update-first-match
  "update first item in s that matches `pred` using (f item args*)"
  [s pred f & args]
  (apply update-in s [(or (find-index pred s)
                          (count s))]
         f args))


(def my-lists
  ['(2 3 4) '(4 5 6 7) '(5 6 7)])

(defn add-to-first-list-less-than
  [l n]
  (update-first-match l #(< n (first %)) conj n))

;; usage:

(update-first-match my-lists #(< 5 (first %)) conj 5)

;; or
(add-to-first-list-less-than my-lists 5)
于 2013-07-30T13:19:08.713 回答