total - sumar elementos de una matriz python

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

Question

He estado haciendo algo de programación funcional y tenía 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 opción en python o F #,

Como 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 miramos a Python, por ejemplo, podría intentar algo como

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

Esto me da la respuesta correcta 6, pero ¿cómo encuentro que había agregado 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 usar un bucle for o usar una función que pueda almacenar estado, etc. Pero cuál sería la manera funcional de hacer / pensar sobre esto. Reduce () quiere funcionar hasta el final, pero en algún punto de esta línea de procesamiento, o queremos detenerlo (porque no nos importa procesar el resto de los elementos) o al menos anotar el lugar donde dejó de preocuparse.

Answer 1

Aquí hay una pequeña variación del código de Stephen, usando foldl lugar de foldr (espero) y no requiriendo 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 2

Creo que esto hace lo que está buscando, usando funciones incorporadas en el módulo 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)

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 debe manejar con lo anterior es el caso en el que nunca se cumple la condición de "búsqueda", 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 un estado anterior que coincida con la condición, salvo el cálculo previo 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 3

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

O bien, ya sabes, escribe una función recursiva simple, como la respuesta de @JaredPar. Por alguna razón, a menudo tengo 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 recursivamente

>>> 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ías así:

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

Answer 5

Estoy de acuerdo con JaredPar en que escribir su propia función recursiva que se comporta de manera similar al fold , pero le permite detener el cálculo antes, es el mejor enfoque. La forma en que lo escribiría es un poco más general (para que pueda usar la función para cualquier situación en la que necesite doblar y que pueda detenerse 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 ]

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

Tenga en cuenta que puede usar foldStop para implementar fold al envolver siempre el resultado de la función de acumulación en ''Some'' (así que es más general):

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

Answer 6

La única forma de salir del edificio integrado es reduce parte. Afortunadamente, no es difícil obtener 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

Pruebe lo siguiente

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    

Resultado interactivo F #

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

Answer 8

Reducir se usa a menudo 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, debe asignar las variables de input [2, 1, 3, 4, 5] a algo así como:

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

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

Lo siguiente, entonces, es 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 retornará (3, 6) , lo que significa que la suma parcial es 6 usando 3 elementos.

Espero que tengas la idea detrás de los algoritmos map-reduce-algorithms.

Saludos,
Christoph

Answer 9

Otro enfoque funcional podría ser el uso de una versión basada en la "continuación" de reducir / doblar:

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

Llamar con ''id'' (diversión x -> x) como ''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ás tu ''6''.

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

Answer 10

Sé que estás específicamente interesado en Python, pero pensé que me gustaría hablar de cómo Clojure logra esto, ya que resuelve el problema de manera bastante elegante y directa.

Clojure tiene una función reduced que devuelve una versión de lo que sea que se pase, de modo que esta versión terminará inmediatamente dentro de una llamada para reducir. Esto hace que sea trivialmente simple 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 o igual a cien, o la suma más grande alcanzada si ninguna excede. 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-funcional". Este podría 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 lenguaje. La clave es que reduce sabe para buscar valores reduced , y los objetos pueden llevar esa información con ellos (ya sea como un valor envuelto de metadatos, no estoy seguro de qué es realmente ...).

Sin duda, es una característica útil que me alegré cuando la necesité.

Answer 11

Imaginemos que Python tiene dos funciones, ireduce (similar a reducir, pero daría valores intermedios, se llama scanl en algunos idiomas) y ilast (obtiene el ú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))