Остановка операции 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

Уменьшение часто используется в сочетании с картой. Например, Google разработал каркас уменьшения карт для запросов к своим базам данных, и этот паттерн уменьшения карт теперь используется в нескольких других проектах (например, 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.

С уважением,
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, всегда заключая результат функции накопления в 'Some' (так что это более общее значение):

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

Answer 3

Давайте представим, что в Python есть две функции: ireduce (аналогично уменьшению , но он даст промежуточные значения; в некоторых языках он называется 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, или нетерпеливый язык, но используете ленивую структуру данных списка (например, LazyList в F # PowerPack), вы можете создать, например, «сканирование» текущих сумм, а затем оставление его в руках потребителя списка, чтобы решить, сколько он хочет / должен оценить.

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

Answer 5

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

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 # интерактивный результат

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

Answer 6

Я думаю, что это делает то, что вам нужно, используя функции, встроенные в модуль 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)

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

Единственная проблема, с которой вам нужно разобраться, - это случай, когда условие "find" никогда не выполняется, и в этом случае выдается исключение 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)

Answer 7

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

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

Вызов с «id» (веселье 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 не является хвостовой рекурсивной - или иным образом рекомендованной - думала ...

Answer 8

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

>>> 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)

Answer 9

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

Clojure имеет reduced функцию , которая возвращает версию того, что ей было передано, так что эта версия будет немедленно завершена в вызове для сокращения. Это позволяет легко сделать что-то вроде этого:

(reduce (fn [a v]
          (if (< a 100) 
            (+ a v)
            (reduced a)))
        (range 20))
;; => 105

Возвращает первую сумму, которая больше или равна сотне, или наибольшую сумму, достигнутую, если ни одна из них не превышает. И стоит отметить, что он делает это без использования / итерации по всей сокращаемой коллекции, которая может быть очень большой или даже бесконечной ленивой последовательностью. Более того, это имеет определенное преимущество перед применением какой-либо операции фильтрации в первую очередь, поскольку вы можете иметь условие завершения, зависящее от создаваемого значения, а не только от уменьшения отдельных значений в коллекции.

Вы упоминаете, что эта идея кажется чем-то "анит-функциональной". Это может показаться имевшим место в python, где неясно, как бы вы достигли этого, не прибегая к некоторому грязному внешнему состоянию (или в лучшем случае альтернативной версии reduce). Тем не менее, это работает чисто и функционально (даже чисто так) в Clojure, потому что он был встроен в язык. Ключ в том, что reduce знает, как искать значения reduced, и объекты могут нести эту информацию вместе с ними (либо в виде обернутого значения в виде метаданных; не уверен, какой именно ...).

Это, безусловно, удобная функция, которой я был рад, когда мне это было нужно.

Answer 10

Единственный способ выбраться из встроенного 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)