如何在函数式编程中计算未知大小列表中相邻元素的差异？

Question

在一种纯粹的函数式编程语言（如Haskell）或仅以函数式方式使用它的语言（例如clojure）中，假设你有一个整数列表/序列/可枚举集合（大小未知），并且想要生成一个新的列表/序列/可枚举集合，其中包含相邻项目之间的差异，你会怎么做？

在函数式编程中，通常采用“映射”和“累加器”两种方法来解决这类问题。具体而言，在本例中，您可以通过将“map”函数应用于输入列表/序列/可枚举集合中的每个元素，并对相邻元素进行差异计算来获得所需的输出列表/序列/可枚举集合。

下面是一个Clojure示例代码：

```clojure (defn diff [lst] (let [pairs (partition 2 1 lst)] (map #(apply - %) pairs))) ```

该函数接受一个列表 `lst`，并使用`partition`函数将列表拆分为两个一组的子列表，然后将`apply`函数应用于每个子列表上，以计算它们之间的差异。最后，`map`函数将应用于所有这些差异值，以生成输出列表。

需要注意的是，与C#中的“fold”不同，这里使用了Clojure中的“map”和“reduce”函数的组合来实现累加器的效果。这种方法允许我们以一种更为函数式和声明性的方式来处理数据，而不是手动管理状态并进行可变更新。

希望以上翻译对您有所帮助。

- Pieter Breed

---

它是什么类型的列表？它是一个链接列表，你可以遍历列表直到达到NIL吗？如果是这样，为什么不从第二个项目开始迭代，在每次迭代中保存前一个元素的值并计算差异并将其推送到新列表中？ - Odinn

@Odinn 能否把它写成代码形式？ - Pieter Breed

我对看到C#的方法进行比较很感兴趣，尤其是如果你使用LINQ来完成这个任务。 - eternalmatt

请注意，Haskell中的Data.List包含了一个特定情况下（在生成新列表的同时跟踪状态）的函数mapAccum[LR]。使用它，您的函数将被写成diffs = drop 1 . snd . mapAccumL (\x y -> (y, y-x)) 0。尽管在我看来，在这种特定情况下，使用zipWith的惯用代码更易读。 - Jedai

@eternalmatt 为您单独添加了一个答案。 - Pieter Breed

Answer 1

在 Haskell 中，你可能会使用一些高阶函数，比如 zipWith。因此，你可以像这样做：

diff [] = []
diff ls = zipWith (-) (tail ls) ls

注意我是如何单独处理[]的情况的——如果你向tail传递一个空列表，就会出现运行时错误，而Haskeller们非常、非常讨厌运行时错误。但是，在我的函数中，我保证ls不为空，所以使用tail是安全的。（参考一下，tail只返回列表中除第一个项外的所有项。它与Scheme中的cdr相同。）

这只需要将列表及其尾部组合起来，并使用(-)函数组合所有项。

给定列表[1,2,3,4]，这将会像这样进行：

zipWith (-) [2,3,4] [1,2,3,4]
[2-1, 3-2, 4-3]
[1,1,1]

这是一个常见的模式：你可以巧妙地使用标准的高阶函数计算出令人惊讶的许多东西。你也不用担心向函数传递列表及其自身的尾部——没有变异会使你犯错，编译器通常非常聪明，可以优化这样的代码。

巧合的是，如果你喜欢列表推导并且不介意启用ParallelListComp扩展，你可以这样写zipWith(-)(tail ls)ls:

[b - a | a <- ls | b <- tail ls]

- Tikhon Jelvis

---

或者 diff xs = zipWith (-) (drop 1 xs) xs。 - augustss

或者 diff ls = zipWith (flip (-)) ls (tail ls) - Landei

当传递一个空列表时，is7s的版本会崩溃，并且由于它是无参数的，因此无法单独处理“[]”情况，就像Tikhon所做的那样。augustss和Landei的版本都可以正确处理“[]”情况，而无需单独处理它。我认为，以上五个版本中最清晰的是augustss的版本。 - dave4420

@dave4420 是的，应该使用 drop 1 来确保安全。 - is7s

我不认为这比augustss的更好，但为了完整起见：diff ls@(~(_:tls)) = zipWith subtract ls tls - 这基本上和使用tail一样邪恶，只是如果你搞砸了，你会得到稍微好一点的错误消息。 - Ben Millwood

Answer 2

在 Clojure 中，你可以使用 map 函数：

(defn diff [coll]
  (map - coll (rest coll)))

- Jonas

---

一个好的例子，点赞！值得注意的是这种方法很懒惰，因此差异只会在需要时计算。coll甚至可以是一个无限序列。 - mikera

我不得不将这个代码粘贴到Clojure REPL中，以确信它是有效的Clojure代码。盯着它看了一会儿后，我开始理解它了。太棒了，谢谢！ - Pieter Breed

它能够工作是因为map将所有序列参数截断为最短序列的长度。因此，coll被截断以包含元素[0 .. N-2]，而(rest coll)包含元素[1 .. N-1]。然后，map将每个序列中对应的元素应用于-函数，如(- xi yi)。 - Alan Thompson

请注意，如果您不想要一个惰性结果（返回一个向量），则可以使用mapv。 - Alan Thompson

Answer 3

您还可以对连续的元素进行模式匹配。在OCaml中：

let rec diff = function
  | [] | [_]       -> []
  | x::(y::_ as t) -> (y-x) :: diff t

以下是通常的尾递归版本：

let diff =
  let rec aux accu = function
  | [] | [_]       -> List.rev accu
  | x::(y::_ as t) -> aux ((y-x)::accu) t in
  aux []

- Thomas

---

@Fabrice，你的编辑不符合本站的编辑精神。我认为你的建议是一种改进，但如果原回答者不同意呢？如果他认为这会使他的回答变得更糟呢？ - Pascal Cuoq

Answer 4

如果您需要另一种Clojure解决方案，请尝试

(map (fn [[a b]] (- b a))
     (partition 2 1 coll))

- Retief

Answer 5

补充一下前面的回答：在函数式语言中，使用状态对象处理列表是可能的，就像您所描述的那样。但是，在存在更简单的解决方案的情况下，这种做法肯定不被鼓励，但是仍然是可行的。

下面的示例通过计算新的“状态”并将其递归地传递给自身来实现迭代。

(defn diffs
  ([coll] (diffs (rest coll) (first coll) []))
  ([coll prev acc]
     (if-let [s (seq coll)]
       ; new 'state': rest of the list, head as the next 'prev' and
       ; diffs with the next difference appended at the end:
       (recur (rest s) (first s) (conj acc (- (first s) prev)))
       acc)))

状态由列表中先前的 (prev) 值、到目前为止计算出的差异 (acc) 和剩余待处理的列表 (coll) 表示。

- Rafał Dowgird

---

你可能可以使用累加器和reduce操作来完成相同的事情？ - Pieter Breed

@PieterBreed 是的，这个例子实际上是通过递归实现的“reduce”。 - Rafał Dowgird

Answer 6

这是在Haskell中不使用任何标准函数，只使用递归和模式匹配来实现的方法：

diff :: [Int] -> [Int]
diff []     = []
diff (x:xs) = hdiff xs x


hdiff :: [Int] -> Int -> [Int]
hdiff []     p = []
hdiff (x:xs) p = (x-p):hdiff xs x

- nist

---

虽然惯用的方式是使用 zipWith。 - dave4420

Answer 7

好的，对于那些感兴趣的人，这里有两个C#版本：

首先是不好的版本，或者说是之前命令式编程（换句话说就是我）学习函数式编程时可能会尝试编写的版本：

  private static IEnumerable<int> ComputeUsingFold(IEnumerable<int> source)
  {
     var seed = new {Result = new List<int>(), Previous = 0};
     return source.Aggregate(
        seed,
        (aggr, item) =>
           {
              if (aggr.Result.Count > 0)
              {
                 aggr.Result.Add(item - aggr.Previous);   
              }
              return new { Result = aggr.Result, Previous = item };
           }).Result;
  }

然后使用其他答案中表达的习语，得到更好的版本：

  private static IEnumerable<int> ComputeUsingMap(IEnumerable<int> source)
  {
     return source.Zip(source.Skip(1), (f, s) => s - f);
  }

我不确定，但可能是真的，在这个版本中源可枚举对象被迭代了两次。

- Pieter Breed