Haskell Recursion - finding largest difference between numbers in list

Question

Here's the problem at hand: I need to find the largest difference between adjacent numbers in a list using recursion. Take the following list for example: [1,2,5,6,7,9]. The largest difference between two adjacent numbers is 3 (between 2 and 5).

I know that recursion may not be the best solution, but I'm trying to improve my ability to use recursion in Haskell.

Here's the current code I currently have:

largestDiff (x:y:xs) = if (length (y:xs) > 1) then max((x-y), largestDiff (y:xs)) else 0

Basically - the list will keep getting shorter until it reaches 1 (i.e. no more numbers can be compared, then it returns 0). As 0 passes up the call stack, the max function is then used to implement a 'King of the Hill' type algorithm. Finally - at the end of the call stack, the largest number should be returned.

Trouble is, I'm getting an error in my code that I can't work around:

Occurs check: cannot construct the infinite type:
  t1 = (t0, t1) -> (t0, t1)
In the return type of a call of `largestDiff'
Probable cause: `largestDiff' is applied to too few arguments
In the expression: largestDiff (y : xs)
In the first argument of `max', namely
  `((x - y), largestDiff (y : xs))'

Anyone have some words of wisdom to share?

Thanks for your time!

EDIT: Thanks everyone for your time - I ended up independently discovering a much simpler way after much trial and error.

largestDiff [] = error "List too small"
largestDiff [x] = error "List too small"
largestDiff [x,y] = abs(x-y)
largestDiff (x:y:xs) = max(abs(x-y)) (largestDiff (y:xs))

Thanks again, all!

Answer 1

Another solution to this problem, which circumvents your error, can be obtained by just transforming lists and folding/reducing them.

import Data.List (foldl')

diffs :: (Num a) => [a] -> [a]
diffs x = zipWith (-) x (drop 1 x)

absMax :: (Ord a, Num a) => [a] -> a
absMax x = foldl' max (fromInteger 0) (map abs x)

Now I admit this is a bit dense for a beginner, so I will explain the above. The function zipWith transforms two given lists by using a binary function, which is (-) in this case.

The second list we pass to zipWith is drop 1 x, which is just another way of describing the tail of a list, but where tail [] results in an error, drop 1 [] just yields the empty list. So drop 1 is the "safer" choice.

So the first function calculates the adjacent differences.

The name of the second function suggests that it calculates the maximum absolute value of a given list, which is only partly true, it results in "0" if passed an empty list.

But how does this happen, reading from right to left, we see that map abs transforms every list element to its absolute value, which is asserted by the Num a constraint. Then the foldl'-function traverses the list and accumulates the maximum of the previous accumulator and the current element of the list traversal. Moreover I'd like to mention that foldl' is the "strict" sister/brother of the foldl-function, where the latter is rarely of use, because it tends to build up a bunch of unevaluated expressions called thunks.

So let's quit all this blah blah and see it in action ;-)

> let a = diffs [1..3] :: [Int]
>>> zipWith (-) [1,2,3] (drop 1 [1,2,3])
<=> zipWith (-) [1,2,3] [2,3]
<=> [1-2,2-3] -- zipWith stops at the end of the SHORTER list
<=> [-1,-1]

> b = absMax a
>>> foldl' max (fromInteger 0) (map abs [-1,-1])
-- fromInteger 0 is in this case is just 0 - interesting stuff only happens
-- for other numerical types
<=> foldl' max 0 (map abs [-1,-1])
<=> foldl' max 0 [1,1]
<=> foldl' max (max 0 1) [1]
<=> foldl' max 1 [1]
<=> foldl' max (max 1 1) []
<=> foldl' max 1 [] -- foldl' _ acc [] returns just the accumulator
<=> 1

Answer 2

So the reason why your code is throwing an error is because

max((x-y), largestDiff (y:xs))

In Haskell, you do not use parentheses around parameters and separate them by commas, the correct syntax is

max (x - y) (largestDiff (y:xs))

The syntax you used is getting parsed as

max ((x - y), largestDiff (y:xs))

Which looks like you're passing a tuple to max!

However, this does not solve the problem. I always got 0 back. Instead, I would recommend breaking up the problem into two functions. You want to calculate the maximum of the difference, so first write a function to calculate the differences and then a function to calculate the maximum of those:

diffs :: Num a => [a] -> [a]
diffs [] = []                            -- No elements case
diffs [x] = []                           -- One element case
diffs (x:y:xs) = y - x : diffs (y:xs)    -- Two or more elements case

largestDiff :: (Ord a, Num a) => [a] -> a
largestDiff xs = maximum $ map abs $ diffs xs

Notice how I've pulled the recursion out into the simplest possible case. We didn't need to calculate the maximum as we traversed the list; it's possible, just more complex. Since Haskell has a handy built-in function for calculating the maximum of a list for us, we can also leverage that. Our recursive function is clean and simple, and it is then combined with maximum to implement the desired largestDiff. As an FYI, diffs is really just a function to compute the derivative of a list of numbers, it can be a very useful function for data processing.

EDIT: Needed Ord constraint on largestDiff and added in map abs before calculating maximum.

Answer 3

Here's my take at it.

First some helpers:

diff a b = abs(a-b)
pick a b = if a > b then a else b

Then the solution:

mdiff :: [Int] -> Int
mdiff [] = 0
mdiff [_] = 0
mdiff (a:b:xs) = pick (diff a b) (mdiff (b:xs))

You have to provide two closing clauses, because the sequence might have either even or odd number of elements.