Detener una operación Reducir() a mitad de camino. Forma funcional de ejecutar la suma de ejecución parcial

Question

He estado haciendo algunos programas funcionales y tengo una pregunta. Tal vez me esté perdiendo algo, pero ¿hay alguna manera de detener una función "reduce()" a mitad de camino? Digamos cuando llego a una cierta condición? La idea de alguna manera parece anti funcional. No he visto ninguna de esas opciones en Python o F #,

A modo de ejemplo, digamos que tengo una lista como [1,2,3,4,5]. Quiero sumar los elementos en esta lista hasta que la suma no sea mayor que un número (digamos 8), y devolver/marcar/almacenar/identificar de alguna manera, la cantidad de elementos que realmente he agregado.

Si nos fijamos en Python, por ejemplo, para la que podría intentar algo así como

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

Esto me da la respuesta correcta 6, pero ¿cómo puedo encontrar que me había añadido 3 elementos para llegar aquí. No hay un contador como tal. No puedo hacer asignaciones dentro de lambdas. Creo que F # tiene la misma situación.

Sé que puedo utilizar un bucle o utilizar una función que puede almacenar el estado, etc. Pero lo que sería la forma funcional de hacer/pensar en esto. Reduce() quiere funcionar hasta el final, pero en algún lugar a lo largo de esta línea de procesamiento, o queremos detenerlo (porque no nos importa procesar el resto de los elementos) o al menos tomar nota del lugar donde dejó de preocuparse.

Answer 1

Reduce a menudo se usa en combinación con el mapa . Google, por ejemplo, ha desarrollado un marco de reducción de mapas para consultar sus bases de datos y este patrón de reducción de mapas ahora se usa en muchos otros proyectos (por ejemplo, CouchDB, Hadoop, etc.).

En primer lugar, es necesario mapear las variables de input[2, 1, 3, 4, 5] a algo como:

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

En ese caso, x[0] representará el número de los elementos para obtener la suma x[1]. Por supuesto, el número de elementos es 1 al principio para cada elemento individual.

La siguiente cosa a continuación, es para operar en esas tuplas:

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

Esto devolverá (3, 6), es decir, la suma parcial es 6 usando 3 elementos.

Espero que tenga la idea detrás de algoritmos map-reducir-algorithms.

Saludos,
Christoph

Answer 2

Prueba el siguiente resultado interactiva

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 3

Creo que la manera 'más funcional' de hacer esto es probablemente a través de la evaluación perezosa. Si está en un lenguaje lento como Haskell, o en un lenguaje entusiasta, pero con una estructura de datos de lista diferida (como LazyList en el F # PowerPack), puede crear, p. un 'escaneo' de las sumas corrientes, y luego déjelo en las manos del consumidor de la lista para decidir cuánto quiere/necesita evaluar.

O, sabes, escribir una simple función recursiva, como respuesta de @ JaredPar. Por alguna razón, a menudo obtengo un bloqueo mental en eso, impidiéndome notar que "no todo tiene que ser un fold, de hecho puedes escribir tus propias funciones recursivas" :)

Answer 4

Esta es una función que implementa ese programa funcional:

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

o de forma recursiva:

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

Probablemente hay una manera de limpiarlo un poco , pero lo usaría así:

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

Answer 5

Aquí es una ligera variación del código de Stephen, utilizando foldl en lugar de foldr (espero) y que no requieren una secuencia:

#!/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)) 

Answer 6

La única forma de salir de la orden interna manera reduce parte a través de es lanza una excepción Afortunadamente, no es difícil de conseguir el resultado deseado de esta manera:

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) 

Answer 7

Estoy de acuerdo con JaredPar que escribir su propia función recursiva que se comporta de manera similar a fold, pero le permite detener el cálculo anterior es el mejor enfoque. La forma en que iba a escribir que es un poco más general (por lo que se puede utilizar la función para cualquier situación en la que necesita plegable que puede parada antes):

// 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 ] 

Ésta es una función muy general y puedes usarlo para todos los escenarios similares. Lo bueno de escribirlo es que nunca más tendrás que volver a escribir recursiones explícitas similares (porque puedes usar foldStop una vez que lo tienes).

Tenga en cuenta que puede utilizar foldStop para implementar fold por siempre envolviendo el resultado de la función de acumulación en 'Algunas' (lo que es más general):

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

Answer 8

Otra approch funcional podría ser el uso de un "continution "versión basada de reducir/doble:

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

llamada 'id' (diversión x -> x) como 'la continuación inicial':

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

Y obtendrá su '6'.

Tenga en cuenta que esta versión de foldC no es recursiva de cola, ni recomendada de otro modo, pensó ...

Answer 9

Imaginemos Python tiene dos funciones, ireduce (similares a reducir pero sería producir valores intermedios, se llama scanl en algunos idiomas) y ilast (get último elemento de un iterable):

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) 

en Haskell:

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

Answer 10

Creo que esto hace lo que está después, usando funciones incorporadas al módulo F # Sec:

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) 

La función "escanear" es similar a "plegar", pero devuelve una secuencia que contiene estados intermedios (y finales), en lugar de solo el estado final. En este caso, el estado es una tupla que contiene un recuento y la suma de los elementos procesados ​​hasta el momento, comenzando con (0,0). Esto se calcula y alimenta, uno a la vez, en la función "buscar", que devuelve el primer elemento que coincide con la condición suministrada (v> 8), en este caso (4,10).

El único problema que tendría que manejar con lo anterior es el caso donde nunca se cumple la condición "buscar", en cuyo caso se produce una excepción KeyNotFoundException. Puede usar "tryFind" que devuelve un valor de opción. Sin embargo, no puedo ver una forma elegante de devolver el último elemento calculado si no hay estado anterior coincide con la condición, por debajo de pre-cálculo de la longitud de la secuencia:

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 11

Sé que está especialmente interesado en Python, pero pensé que iba a sonar con respecto a cómo Clojure logra esto, ya que resuelve el problema de manera bastante elegante y directa.

Clojure tiene un reduced function que devuelve una versión de lo que se pasa, de modo que esta versión terminará inmediatamente dentro de una llamada para reducir. Esto hace que sea trivialmente simple de hacer algo como esto:

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

Esto devuelve la primera suma que es mayor que o igual a cien, o la mayor suma alcanzado si ninguno supera. Y vale la pena señalar que lo hace sin consumir/iterar a través de la totalidad de la colección que se está reduciendo, lo que podría ser una secuencia vaga muy grande o incluso infinita. Además, esto tiene una ventaja definitiva sobre la aplicación de alguna operación de filtro, ya que puede hacer que su condición de terminación dependa del valor que se está construyendo, no solo por los valores individuales en la colección que se está reduciendo.

Usted menciona que esta idea parece de alguna manera "anit-functional". Este podría ser, parece ser el caso en Python, donde no está claro cómo lo lograrías sin recurrir a un estado exterior desordenado (o en el mejor de los casos una versión alternativa de reduce). Sin embargo, esto funciona limpia y funcionalmente (incluso puramente) en Clojure porque ha sido horneado en el idioma. La clave es que reduce sabe buscar reduced valores, y los objetos pueden llevar esa información con ellos (ya sea como un valor envuelto de metadatos, no estoy seguro de qué en realidad ...).

Ciertamente es una característica útil que he estado contento de tener cuando la he necesitado.