Остановка операции Reduce () на полпути. Функциональный способ выполнения частичной промежуточной суммы

Question

Я занимался функциональным программированием и у меня возник вопрос. Возможно, я что-то упускаю, но есть ли способ остановить функцию «redu ()» на полпути? Скажем, когда я достигну определенного состояния? Идея почему-то кажется антифункциональной. Я не видел такой опции в Python или F #,

В качестве примера, скажем, у меня есть список, такой как [1,2,3,4,5]. Я хочу суммировать элементы в этом списке, пока сумма не станет больше некоторого числа (скажем, 8), и вернуть / пометить / сохранить / идентифицировать каким-либо образом количество элементов, которые я фактически добавил.

Если мы посмотрим на Python, например, я мог бы попробовать что-то вроде

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

Это дает мне правильный ответ 6, но как мне найти, что я добавил 3 элемента, чтобы попасть сюда. Там нет счетчика как такового. Я не могу выполнять задания в лямбдах. Я думаю, что у F # такая же ситуация.

Я знаю, что могу использовать цикл for или использовать функцию, которая может хранить состояние и т. Д. Но каков будет функциональный способ делать / думать об этом. Reduce () хочет работать до конца, но где-то вдоль этой линии обработки мы либо хотим остановить его (потому что нам не нужны обработки остальных элементов), либо, по крайней мере, отметить место, где мы перестал заботиться.

Answer 1

Во-первых, в F #. Какой номер первого треугольника больше 100?

> [1..1000] |> Seq.scan (+) 0 |> Seq.find (fun x -> x > 100);;
val it : int = 105

Обратите внимание, что Seq.scan является ленивым, поэтому числа треугольников за пределами решения никогда не рассчитываются.

Чтобы найти порядковый номер решения, мы обменяем find на findIndex

> [1..1000] |> Seq.scan (+) 0 |> Seq.findIndex (fun x -> x > 100);;
val it : int = 14

---

В Python аналогом List.scan для F # является itertools.accumulate , представлен Python 3.2 (2011).

>>> from itertools import accumulate
>>> next(x for x in accumulate(range(0,1000)) if x > 100)
105
>>> next(i for (i,x) in enumerate(accumulate(range(0,1000))) if x > 100)
14

Answer 2

Если вы хотите избежать ненужных вычислений (что вы все еще будете делать с алгоритмом уменьшения карты), напишите свое собственное уменьшение и поймайте StopIteration:

from functools import reduce as _reduce

def stop_iter(rv=None):
    raise StopIteration(rv)

def reduce(*args):
    try: return _reduce(*args)
    except StopIteration as e: return e.args[0]

Затем напишите пошаговую функцию, которая переносит возвращаемое значение в вызове на stop_iter, когда вы достигнете определенного условия. Используя вашу оригинальную лямбду:

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

Аналогично ответу Дункана, но позволяет использовать лямбда-выражения (исключений вручную не возникает).

Answer 3

Вот небольшое изменение кода Стивена, использующего foldl вместо foldr (я надеюсь) и не требующего последовательности:

#!/usr/bin/env python

import operator
import functools

def limited_reduce(op, it, start, pred):
    if not pred(start):
        return 0, start
    for i, x in enumerate(it):
        y = op(start, x)
        if pred(y):
            start = y
        else:
            break
    return i, start

print limited_reduce(operator.add, xrange(1, 6), 0,
                     functools.partial(operator.gt, 8))