中途停止Reduce()操作。实现部分求和的函数式方法

Question

我最近在做一些函数式编程，遇到了一个问题。也许我遗漏了什么，但有没有办法在“reduce()”函数执行到一半时停止？比如说，当我达到某个条件时？这个想法似乎有点违背函数式编程的原则。我在Python或F#中没有看到这样的选项。

举个例子，假设我有一个列表，比如说[1,2,3,4,5]。我想把这个列表中的元素相加，直到总和不超过某个数字（比如8），然后返回/标记/存储/识别一下，我实际上加了多少个元素。

如果我们看Python的话，我可能会尝试这样的代码：

reduce(lambda a,b : a if a + b > 8 else a + b, input)

这段代码给了我正确的答案6，但我怎么知道我加了3个元素才能得到这个结果呢？没有计数器之类的东西。我不能在lambda表达式里做赋值。我觉得F#的情况也是一样。

我知道我可以使用for循环或者用一个可以存储状态的函数等等。但从函数式编程的角度来看，应该怎么做/怎么想呢？reduce()函数想一直执行到最后，但在这个处理过程中，我们有时想停止它（因为我们不在乎处理剩下的元素），或者至少记下我们停止的地方。

Answer 1

假设Python有两个函数，ireduce（这个函数和reduce类似，但它会返回中间的值；在某些语言中叫做scanl）和ilast（用来获取可迭代对象的最后一个元素）：

from itertools import takewhile
from operator import add
xs = [1, 2, 3, 4, 5]
pair = ilast(enumerate(takewhile(lambda x: x < 8, ireduce(add, xs, 0))))
# (3, 6)

在Haskell语言中：

last $ zip [0..] (takeWhile (< 8) (scanl (+) 0 xs))

Answer 2

我同意JaredPar的看法，自己写一个递归函数，功能类似于fold，但可以提前停止计算，这样做是最好的方法。我写的这个函数会更通用一些（这样你可以在任何需要折叠并且可以提前停止的情况下使用它）：

// Generalized 'fold' function that allws you to stop the execution earlier
// The function 'f' has a type 'State -> 'T -> Option<'State>
// By returning 'None' we can stop the execution (and return the 
// current state), by returning Some(newState), we continue folding
let rec foldStop f state input = 
  match input with
  | x::xs -> 
      match f state x with
      | None -> state
      | Some(newState) -> foldStop f newState xs
  | [] -> state

// Example that stops folding after state is larger than 10
foldStop (fun st n -> if st > 10 then None else Some(st + n)) 0 [ 1 .. 10 ]

这个函数非常通用，你可以在所有类似的场景中使用它。写这个函数的好处是，你以后再也不需要写类似的递归代码了（因为有了foldStop，你可以直接用它）。

需要注意的是，你可以用foldStop来实现fold，方法是总是把累加函数的结果包裹在'Some'里面（这样它就更通用了）：

let fold f state input = 
  foldStop (fun st n -> Some(f st n)) state input

Answer 3

在编程中，"reduce"通常和"map"一起使用。比如，谷歌开发了一种叫做map-reduce的框架，用来查询他们的数据库，这种map-reduce的模式现在也被用在其他一些项目中，比如CouchDB和Hadoop等。

首先，你需要把输入的变量[2, 1, 3, 4, 5]映射成类似这样的东西：

[(1, 2), (1, 1), (1, 3), (1, 4), (1, 5)]

在这个例子中，x[0]表示要计算的元素数量，而x[1]则是这些元素的和。当然，一开始每个单独的元素的数量都是1。

接下来，就是对这些元组进行操作：

reduce(
    lambda a, b: a if a[1] + b[1] > 8 else (a[0] + b[0], a[1] + b[1]),
    map(lambda x: (1, x), input))

这会返回(3, 6)，意思是用3个元素得到了部分和6。

希望你能理解map-reduce算法背后的概念。

祝好，
Christoph