在中途停止Reduce()操作.做部分运行总和的功能方式

Question

我一直在做一些函数式编程并且有一个问题.也许我可能会遗漏一些东西,但有没有办法在中途停止"减少()"功能？让我说当我达到一定条件？这个想法似乎有点反功能.我没有在python或F#中看到任何这样的选项,

举个例子,假设我有一个列表,如[1,2,3,4,5].我想总结这个列表中的元素,直到总和不大于某个数字(比方说8),并以某种方式返回/标记/存储/识别我实际添加的元素数量.

如果我们以python为例,我可能会尝试类似的东西

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

这给了我正确答案6,但我怎么发现我已经添加了3个元素来到这里.没有这样的反击.我不能在lambdas里面做任务.我认为F#具有相同的情况.

我知道我可以使用for循环或使用可以存储状态等的函数.但是这样做的功能方式是什么.Reduce()想要一直运行到最后,但是在这个处理线的某个地方,我们要么想要停止它(因为我们不关心处理其余的元素)或至少记下我们所在的地方停止关怀.

Answer 1

减少通常与地图结合使用.例如,谷歌开发了一个map-reduce框架来查询他们的数据库,这个map-reduce模式现在用于其他几个项目(例如CouchDB,Hadoop等).

首先,您需要将input变量映射[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),这意味着部分和6使用3元素.

我希望你有了map-reduce-algorithms背后的想法.

此致,
Christoph

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由总包的累积函数的结果在"某些"(所以它是更普遍的):

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

Answer 3

让我们假设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 4

我认为"最实用"的方法可能是通过懒惰的评估.如果您使用的是像Haskell这样的懒惰语言,或者使用懒惰的列表数据结构(例如LazyListF#PowerPack),您可以创建例如运行总和的"扫描",然后将其保留在列表消费者的手来决定她想要/需要评估多少.

或者,你知道,写一个简单的递归函数,比如@JaredPar的答案.出于某种原因,我常常对此产生心理障碍,阻止我注意到"并非一切都必须是一个fold,你实际上可以编写自己的递归函数":)