¿Cómo se calcula la diferencia entre los elementos sucesivos de una lista de tamaño desconocido, funcionalmente?

Question

En un lenguaje de programación que es puramente funcional (como Haskell) o donde solo lo está usando de una manera funcional (por ejemplo, clojure); supongamos que tiene una lista/seq/enumerable (de tamaño desconocido) de enteros y desea generar una nueva lista/seq/enumerable que contenga las diferencias entre los elementos sucesivos, ¿cómo lo haría?

Lo que hice anteriormente en C# fue doblar sobre la lista y mantener un objeto de estado como el valor agregado que grabó el elemento 'anterior' para que pueda hacer una diferencia sobre el elemento actual. La lista de resultados también tuvo que entrar en el objeto de estado (que es un problema para una lista de tamaño desconocido)

¿Cuál es el enfoque general para hacer este tipo de cosas funcionalmente?

Answer 1

En Haskell probablemente solo usarías alguna función de orden superior como zipWith. Por lo que podría hacer algo como esto:

diff [] = [] 
diff ls = zipWith (-) (tail ls) ls 

Nota cómo he manejado el caso [] separado - si se pasa una lista vacía a tail obtiene un error de tiempo de ejecución, y Haskellers realmente, realmente tiempo de ejecución odio errores Sin embargo, en mi función, tengo garantizado que el ls no está vacío, por lo que usar tail es seguro. (Como referencia, tail sólo devuelve todo excepto el primer elemento de la lista. Es lo mismo que en el Esquema cdr.)

Esto sólo toma la lista y su cola y se combinan todos los elementos utilizando la función (-).

Dada una lista [1,2,3,4], esto sería algo como esto:

zipWith (-) [2,3,4] [1,2,3,4] 
[2-1, 3-2, 4-3] 
[1,1,1] 

Este es un patrón común: se puede calcular sorprendentemente muchas cosas utilizando hábilmente funciones de orden superior estándar. Tampoco tiene miedo de pasar una lista y su propia cola a una función: no hay mutación que lo desordene y el compilador a menudo es muy hábil para optimizar un código como este.

Casualmente, si te gusta listas por comprensión y no les importa que permite la extensión ParallelListComp, se podría escribir zipWith (-) (tail ls) ls así:

[b - a | a <- ls | b <- tail ls] 

Answer 2

En clojure, puede utilizar la función map:

(defn diff [coll] 
    (map - coll (rest coll))) 

Answer 3

Así es como se puede hacer en Haskell sin ninguna función estándar, solo recursividad y coincidencia de patrones:

diff :: [Int] -> [Int] 
diff []  = [] 
diff (x:xs) = hdiff xs x 


hdiff :: [Int] -> Int -> [Int] 
hdiff []  p = [] 
hdiff (x:xs) p = (x-p):hdiff xs x 

Answer 4

Simplemente para complementar las respuestas idiomáticas: es posible en los lenguajes funcionales procesar una lista usando un objeto de estado, tal como lo describió. Definitivamente se desaconseja en los casos en que existen soluciones más simples, pero posibles.

El siguiente ejemplo implementa la iteración calculando el nuevo 'estado' y pasándolo recursivamente a sí mismo.

(defn diffs 
    ([coll] (diffs (rest coll) (first coll) [])) 
    ([coll prev acc] 
    (if-let [s (seq coll)] 
     ; new 'state': rest of the list, head as the next 'prev' and 
     ; diffs with the next difference appended at the end: 
     (recur (rest s) (first s) (conj acc (- (first s) prev))) 
     acc))) 

El estado está representado en la (prev) valor anterior de la lista, los diferenciales calculados hasta el momento (acc) y el resto de la lista de la izquierda para procesar (coll).

Answer 5

También puede hacer coincidir elementos consecutivos. En OCaml:

let rec diff = function 
    | [] | [_]  -> [] 
    | x::(y::_ as t) -> (y-x) :: diff t 

Y la cola recursiva habitual versión:

let diff = 
    let rec aux accu = function 
    | [] | [_]  -> List.rev accu 
    | x::(y::_ as t) -> aux ((y-x)::accu) t in 
    aux [] 

Answer 6

Por otra solución Clojure, tratan

(map (fn [[a b]] (- b a)) 
    (partition 2 1 coll)) 

Answer 7

OK, aquí hay dos versiones de C# para los que están interesados :

En primer lugar, la versión incorrecta, o la que anteriormente era imperativa (en otras palabras, I) podría intentar escribir e la programación funcional se aprende:

private static IEnumerable<int> ComputeUsingFold(IEnumerable<int> source) 
    { 
    var seed = new {Result = new List<int>(), Previous = 0}; 
    return source.Aggregate(
     seed, 
     (aggr, item) => 
      { 
       if (aggr.Result.Count > 0) 
       { 
       aggr.Result.Add(item - aggr.Previous); 
       } 
       return new { Result = aggr.Result, Previous = item }; 
      }).Result; 
    } 

A continuación, una versión mejor uso de los idiomas expresaron en otras respuestas en esta pregunta:

private static IEnumerable<int> ComputeUsingMap(IEnumerable<int> source) 
    { 
    return source.Zip(source.Skip(1), (f, s) => s - f); 
    } 

No estoy seguro, pero podría ser cierto que en esta versión la fuente enumerable se repite dos veces.