haskell - tabla - ¿Cómo calcula la diferencia funcional entre los elementos sucesivos de una lista de tamaño desconocido?

protones electrones y neutrones del hidrogeno

Question

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

Lo que hice anteriormente en C # fue plegar la lista y mantener un objeto de estado como el valor de agregación que registró el elemento ''anterior'' para que pudiera hacer una diferencia con respecto al elemento actual. La lista de resultados también tuvo que ir al 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

Así es como se puede hacer en Haskell sin ninguna función estándar, solo recursión 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 2

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

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

Observe cómo manejé el caso [] separado: si pasa una lista vacía para seguir, obtiene un error de tiempo de ejecución, y los Haskeller realmente odian los errores de tiempo de ejecución. Sin embargo, en mi función, tengo la garantía de que ls no está vacío, por lo que usar tail es seguro. (Para referencia, tail solo devuelve todo excepto el primer elemento de la lista. Es lo mismo que cdr en Esquema).

Esto solo toma la lista y su cola y combina todos los elementos usando la función (-) .

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

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

Este es un patrón común: puede calcular sorprendentemente muchas cosas mediante el uso inteligente de funciones estándar de orden superior. Tampoco tiene miedo de pasar una lista y su propia cola a una función: no hay una mutación que lo arruine y el compilador a menudo es muy inteligente en la optimización de código como este.

Casualmente, si te gustan las comprensiones de listas y no te importa habilitar la extensión ParallelListComp , puedes escribir zipWith (-) (tail ls) ls como esto:

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

Answer 3

En clojure, puede utilizar la función de map :

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

Answer 4

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

Primero, se aprende la versión incorrecta, o la que el imperativo anterior (en otras palabras, I) podría tratar de escribir como programación funcional:

  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;
  }

Luego, una versión mejor que usa los modismos expresados ​​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 itera dos veces.

Answer 5

Para otra solución de Clojure, intente

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

Answer 6

Solo para complementar las respuestas idiomáticas: es posible en los lenguajes funcionales procesar una lista usando un objeto de estado, tal como lo describió. Se desaconseja definitivamente 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 de forma recursiva 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 se representa en el valor anterior ( prev ) de la lista, las diferencias calculadas hasta el momento ( acc ) y el resto de la lista se deja procesar ( coll ).

Answer 7

También puede hacer un patrón de elementos consecutivos. En OCaml:

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

Y la versión habitual de cola recursiva:

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