Как вы вычисляете разницу между последовательными элементами списка неизвестного размера, функционально?

Question

На языке программирования, который является чисто функциональным (например, Haskell) или где вы используете его только функциональным образом (например, clojure); Предположим, у вас есть список / seq / enumerable (с неизвестным размером) целых чисел, и вы хотите создать новый список / seq / enumerable, который содержит различия между последовательными элементами, как бы вы это сделали?

То, что я делал ранее в C #, заключалось в том, чтобы свернуть список и сохранить объект состояния в качестве агрегирующего значения, в котором записан «предыдущий» элемент, чтобы вы могли выполнить различие по нему из текущего элемента. Список результатов также должен был перейти в объект состояния (что является проблемой для списка неизвестного размера)

Каков общий подход к функциональным действиям такого рода?

Answer 1

В Haskell вы, вероятно, просто использовали бы функцию более высокого порядка, такую ​​как zipWith.Таким образом, вы можете сделать что-то вроде этого:

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

Обратите внимание, как я обработал случай [] отдельно - если вы передадите пустой список в tail, вы получите ошибку времени выполнения и Haskellers действительно , действительно ненавижу ошибки времени выполнения.Однако в моей функции я гарантирую, что ls не пустой, поэтому использование tail безопасно.(Для справки tail просто возвращает все, кроме первого элемента списка. Он такой же, как cdr в Схеме.)

Это просто берет список и его хвост и объединяет все элементы, используя(-) функция.

При наличии списка [1,2,3,4] это будет выглядеть примерно так:

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

Это обычная модель: вы можете удивительно много вычислять, умно используястандартные функции высшего порядка.Вы также не боитесь передавать список и свой собственный хвост функции - нет никакой мутации, которая могла бы вас испортить, и компилятор часто очень умен в оптимизации кода, подобного этому.

По совпадению, если вынапример списочные выражения и не против включения расширения ParallelListComp, вы можете написать zipWith (-) (tail ls) ls так:

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

Answer 2

В ближайшем будущем вы можете использовать функцию map:

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

Answer 3

Вы также можете сопоставить шаблон последовательных элементов. В OCaml:

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

И обычный хвост-рекурсивный вариант:

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

Answer 4

Для другого решения Clojure, попробуйте

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

Answer 5

Просто для дополнения идиоматических ответов: на функциональных языках можно обрабатывать список с использованием объекта состояния, как вы описали.Это определенно не рекомендуется в тех случаях, когда существуют более простые решения, но они возможны.

В следующем примере реализована итерация путем вычисления нового «состояния» и его рекурсивной передачи самому себе.

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

Состояниеотображается в предыдущем (prev) значении из списка, вычисленные до сих пор разности (acc), а остальная часть списка оставлена ​​для обработки (coll).

Answer 6

Вот как это можно сделать в Haskell без каких-либо стандартных функций, только рекурсия и сопоставление с образцом:

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 7

ОК, вот две версии C # для тех, кому интересно:

Во-первых, плохая версия или та, которую ранее императив (другими словами, я) мог бы попытаться написать по мере изучения функционального программирования:

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

Тогда лучше вариант с использованием идиом, выраженных в других ответах на этот вопрос:

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

Я не уверен, но может быть и так, что в этой версии перечисляемый источник повторяется дважды.