¿Cómo se calcula la diferencia entre los elementos sucesivos de una lista de tamaño desconocido, funcionalmente?
En un lenguaje de programación que es puramente funcional (como Haskell) o donde solo lo está utilizando de una manera funcional (por ejemplo, clojure); supongamos 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 doblar la lista y mantener un objeto de estado como el valor agregado que registró el elemento 'anterior' para que podría hacer una diferencia en él desde el elemento actual. La lista de resultados también tenía que entrar en el objeto state (que es un problema para una lista de tamaño desconocido)
¿Cuál es el enfoque general para hacer este tipo de cosas funcionalmente?
7 answers
En Haskell probablemente usarías alguna función de orden superior como zipWith. Así que podrías hacer algo como esto:
diff [] = []
diff ls = zipWith (-) (tail ls) ls
Tenga en cuenta cómo manejé el caso [] por separado--si pasa una lista vacía a tail obtiene un error de tiempo de ejecución, y Haskelers realmente, realmente odio los errores de tiempo de ejecución. Sin embargo, en mi función, estoy garantizado que ls no está vacío, por lo que usar tail es seguro. (Como referencia, tail devuelve todo excepto el primer elemento de la lista. Es lo mismo que cdr en Scheme.)
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 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: puedes calcular sorprendentemente muchas cosas usando inteligentemente funciones estándar de orden superior. Tampoco tiene miedo de pasar una lista y su propia cola a una función no no hay ninguna mutación que lo arruine y el compilador a menudo es muy inteligente sobre la optimización de código como este.
Coincidentemente, si te gustan las comprensiones de listas y no te importa habilitar la extensión ParallelListComp, podrías escribir zipWith (-) (tail ls) ls así:
[b - a | a <- ls | b <- tail ls]
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-03-01 08:17:36
En clojure, puede utilizar el map función:
(defn diff [coll]
(map - coll (rest coll)))
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-03-01 08:03:43
También puede hacer coincidir patrones con elementos consecutivos. En OCaml:
let rec diff = function
| [] | [_] -> []
| x::(y::_ as t) -> (y-x) :: diff t
Y la versión recursiva de cola habitual:
let diff =
let rec aux accu = function
| [] | [_] -> List.rev accu
| x::(y::_ as t) -> aux ((y-x)::accu) t in
aux []
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-03-01 22:32:31
Para otra solución de Clojure, intente
(map (fn [[a b]] (- b a))
(partition 2 1 coll))
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-03-01 15:55:54
Solo para complementar las respuestas idiomáticas: es posible en lenguajes funcionales procesar una lista usando un objeto de estado, tal y como usted describió. Definitivamente se desaconseja en los casos en que existen soluciones más simples, pero posibles.
El siguiente ejemplo implementa la iteración computando el nuevo 'estado' y pasándolo recursivamente a self.
(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 el valor anterior (prev) de la lista, los diffs calculados hasta ahora (acc) y el resto del lista a la izquierda para procesar (coll).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-03-01 13:09:30
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
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-03-01 09:21:44
OK, aquí hay dos versiones de C# para aquellos que están interesados:
Primero, la versión mala, o la que el imperativo anterior (en otras palabras yo) podría intentar escribir como 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;
}
Entonces una mejor versión usando 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.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-03-05 05:53:51