How do you compute the difference between successive elements of a list of unknown size, functionally?

Question

In a programming language that is purely functional (like Haskell) or where you are only using it in a functional way (eg clojure); suppose you have a list/seq/enumerable (of unknown size) of integers and you want to produce a new list/seq/enumerable that contains the differences between successive items, how would you do it?

What I did previously in C# was to fold over the list and keep a state object as the aggregating value which recorded the 'previous' item so that you could do a diff on it from the current item. The the result list also had to go into the state object (which is a problem for a list of unknown size)

What is the general approach for doing this kind of thing functionally?

Answer 1

In Haskell you would probably just use some higher order function like zipWith. So you could do something like this:

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

Note how I handled the [] case separately--if you pass an empty list to tail you get a runtime error, and Haskellers really, really hate runtime errors. However, in my function, I'm guaranteed the ls is not empty, so using tail is safe. (For reference, tail just returns everything except the first item of the list. It's the same as cdr in Scheme.)

This just takes the list and its tail and combine all of the items using the (-) function.

Given a list [1,2,3,4], this would go something like this:

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

This is a common pattern: you can compute surprisingly many things by cleverly using standard higher-order functions. You are also not afraid of passing in a list and its own tail to a function--there is no mutation to mess you up and the compiler is often very clever about optimizing code like this.

Coincidentally, if you like list comprehensions and don't mind enabling the ParallelListComp extension, you could write zipWith (-) (tail ls) ls like this:

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

Answer 2

In clojure, you can use the map function:

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