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

Я думаю, что это делает то, что вам нужно, используя встроенные функции модуль F # Seq:

let answer =
    [1; 2; 3; 4; 5]
    |> Seq.scan (fun (count,sum) x -> (count+1, sum + x) ) (0,0)
    |> Seq.find (fun (_,x) -> x > 8)

Функция «сканирование» похожа на «свернуть», но возвращает последовательность, содержащую промежуточные (и конечные) состояния, а не только конечное состояние. В этом случае состояние представляет собой кортеж, содержащий количество и сумму элементов, обработанных на данный момент, начиная с (0,0). Это вычисляется и передается по одному в функцию «find», которая возвращает первый элемент, который соответствует заданному условию (v> 8), в данном случае (4,10).

Единственная проблема, с которой вам нужно будет справиться, - это случай, когда условие «найти» никогда не выполняется, и в этом случае генерируется KeyNotFoundException. Вы можете использовать «tryFind», который возвращает значение параметра. Однако я не вижу изящного способа вернуть последний вычисленный элемент, если никакое более раннее состояние не соответствует условию, за исключением предварительного вычисления длины последовательности:

let xs = [1; 2; 3; 4; 5]
let len = Seq.length xs
let answer =
    xs
    |> Seq.scan (fun (count,acc) v -> (count+1, v + acc) ) (0,0)
    |> Seq.find (fun (count,v) -> v > 99 || count = len)

Другой функциональный подход может заключаться в использовании версии reduce / fold, основанной на «продолжении»:

let rec foldC fn acc cont = function
    | []      -> acc
    | x :: xs -> fn x acc (fun acc -> foldC fn acc cont xs) 

Вызов с 'id' (fun x -> x) в качестве 'начального продолжения':

foldC (fun x sum c -> 
           if (sum + x) > 8 
           then sum 
           else c (sum + x))
      0
      (fun x -> x) 
      [1; 2; 3; 4; 5]

И вы получите «6».

Обратите внимание, что эта версия foldC не является хвостовой рекурсивной - или иным образом рекомендованной - мыслью ...

Единственный способ выйти из встроенной функции reduce на полпути - это вызвать исключение. К счастью, получить желаемый результат несложно:

def interruptible_reduce(fn, *args):
    try:
        return reduce(fn, *args)
    except StopIteration, e:
        return e.args[0]

def reducefn(a, b):
    total = a[1] + b[1]
    if total > 8:
        raise StopIteration(a)
    return (a[0]+b[0], total)

input = [2, 1, 3, 4, 5]

>>> from itertools import imap
>>> interruptible_reduce(reducefn, imap(lambda x: (1,x), input))
(3, 6)

Вот небольшая вариация кода Стивена, использующая 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))

Я думаю, что "наиболее функциональный" способ сделать это, вероятно, через ленивую оценку. Если вы работаете на ленивом языке, таком как Haskell, или на нетерпеливом языке, но используете структуру данных ленивого списка (как LazyList в F# PowerPack), вы можете создать, например, "сканирование" выполняющихся сумм, а затем оставить в руках потребителя списка решение о том, сколько она хочет/нуждается в оценке.

Или, знаете, написать простую рекурсивную функцию, как в ответе @JaredPar. По какой-то причине у меня часто возникает ментальный блок на этом, мешающий мне заметить, что "не все должно быть fold, на самом деле вы можете писать свои собственные рекурсивные функции" :)

Попробуйте следующее

let sumUntil list stopAfter = 
    let rec inner list sum = 
        if sum >= stopAfter then sum
        else 
            match list with
            | [] -> sum
            | h::t-> inner t (sum + h)
    inner list 0    

F# interactive result

> sumUntil [1;2;3;4;5] 8;;
val it : int = 10

Я согласен с 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

Представим, что у 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))

Это функция, которая реализует эту функциональную программу:

>>> def limited_reduce(reducer, pred, lst):
...  i = 0
...  y = lst[0]
...  while pred(y) and i < len(lst):
...    i += 1
...    y = reducer(lst[i], y)
...  return (i, y)

или рекурсивно:

>>> def limited_reduce(reducer, pred, lst):
...   def helper(i, accum, rest):
...     if not rest or not pred(accum): return (i, accum)
...     return helper(i+1, reducer(rest[0], accum), rest[1:])
...   return helper(0, lst[0], lst[1:])

Возможно, есть способ немного очистить это, но вы будете использовать это следующим образом:

>>>> limited_reduce(lambda x,y: x+y, lambda r: r < 6, [1,2,1,3,2])
(3, 7)