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

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

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

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

Ответ 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]

Ответ 2

В clojure вы можете использовать функцию map:

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

Ответ 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 []

Ответ 4

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

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

Ответ 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).

Ответ 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

Ответ 7

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

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

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

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