如何在功能上计算未知大小列表的连续元素之间的差异？

Question

在纯函数式编程语言(如Haskell)中,或者只是以函数方式使用它(例如clojure); 假设你有一个整数的list/seq/enumerable(未知大小),你想要生成一个包含连续项之间差异的新list/seq/enumerable,你会怎么做？

我之前在C#中所做的是折叠列表并将状态对象保留为记录"上一个"项目的聚合值,以便您可以从当前项目对其进行差异处理.结果列表也必须进入状态对象(对于未知大小的列表,这是一个问题)

在功能上做这种事情的一般方法是什么？

Answer 1

在Haskell中你可能只是使用一些更高阶的函数zipWith.所以你可以这样做:

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

请注意我是如何处理的[]单独情况下-如果你传递一个空列表,tail你会得到一个运行时错误,并Haskellers 真的,真的讨厌运行时错误.但是,在我的功能中,我保证ls不是空的,所以使用tail是安全的.(作为参考,tail只返回除列表的第一项之外的所有内容.它与cdrScheme中的相同.)

这只是获取列表及其尾部,并使用该(-)功能组合所有项目.

给出一个列表[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]

Answer 2

在clojure中,您可以使用以下map功能:

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

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 []

Answer 4

对于另一个Clojure解决方案,请尝试

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

Answer 5

只是为了补充惯用的答案:在函数式语言中,可以使用状态对象处理列表,就像您描述的那样.在存在更简单的解决方案但可能的情况下,绝对不鼓励这种情况.

以下示例通过计算新的"state"并将其递归地传递给self来实现迭代.

(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在列表的previous()值中表示,到目前为止计算的差异(acc)和列表的其余部分留给process(coll).