Comparing List Elements in Haskell

Question

I'm just learning Haskell and am kind of stuck. I'd like to compare list elements and measure the difference between them and return the highest one. Unfortunatly, I do not know how to approach that problem. For usual, I'd just iterate the list and compare the neighbours but that does not seem to be the way to go in Haskell. I already tried using map but as I said I do not really know how you can solve that problem. I'd be thankful for every kind of advice!

Best wishes

Edit: My idea is to first zip all pairs like this pairs a = zip a (tail a). Then I'd like to get all differences (maybe with map?) and then just chose the highest one. I just can't handle the Haskell syntax.

Answer 1

I don't know what you mean by "measure the discrepancy" between list elements, but if you want to calculate the "largest" element in a list, you'd use the built-in maximum function:

maximum :: Ord a => [a] -> a

This function takes a list of values that can be ordered, so all numbers, chars, and strings, among others.

If you want to get the difference between the maximum value and the minimum value, you can use the similar function minimum, then just subtract the two. Sure, there might be a slightly faster solution whereby you only traverse the list once, or you could sort the list then take the first and last elements, but for most cases doing diff xs = maximum xs - minimum xs is plenty fast enough and makes the most sense to someone else.

---

So what you want to do is compute a difference between successive elements, not calculate the minimum and maximum of each element. You don't need to index directly, but rather use a handy function called zipWith. It takes a binary operation and two lists, and "zips" them together using that binary operation. So something like

zipWith (+) [1, 2, 3] [4, 5, 6] = [1 + 4, 2 + 5, 3 + 6] = [5, 7, 9]

It is rather handy because if one of the lists runs out early, it just stops there. So you could do something like

diff xs = zipWith (-) xs ???

But how do we offset the list by 1? Well, the easy (and safe) way is to use drop 1. You could use tail, but it'll throw an error and crash your program if xs is an empty list, but drop will not

diff xs = zipWith (-) xs $ drop 1 xs

So an example would be

diff [1, 2, 3, 4] = zipWith (-) [1, 2, 3, 4] $ drop 1 [1, 2, 3, 4]
                  = zipWith (-) [1, 2, 3, 4] [2, 3, 4]
                  = [1 - 2, 2 - 3, 3 - 4]
                  = [-1, -1, -1]

This function will return positive and negative values, and we're interested only in the magnitude, so we can then use the abs function:

maxDiff xs = ??? $ map abs $ diff xs

And then using the function I highlighted above:

maxDiff xs = maximum $ map abs $ diff xs

And you're done! If you want to be fancy, you could even write this in point-free notation as

maxDiff = maximum . map abs . diff

Now, this will in fact raise an error on an empty list because maximum [] throws an error, but I'll let you figure out a way to solve that.

Answer 2

As mentioned by bheklilr, maximum is the quick and easy solution.

If you want some of the background though, here's a bit. What we're trying to do is take a list of values and reduce it to a single value. This is known as a fold, and is possible with (among others) the foldl function, which has the signature foldl :: (a -> b -> a) -> a -> [b] -> a.

The (a -> b -> a) section of foldl is a function which takes two values and returns one of the first type. In our case, this should be our comparison function:

myMax :: Ord a => a -> a -> a
myMax x y | x > y     = x
          | otherwise = y

(note that Ord a is required so that we can compare our values).

So, we can say

-- This doesn't work!

myMaximum :: Ord a => [a] -> a
myMaximum list = foldl myMax _ list

But what is _? It doesn't make sense to have a starting value for this function, so we turn instead to foldl1, which does not require a starting value (instead it takes the first two values from the list). That makes our maximum function

myMaximum :: Ord a => [a] -> a
myMaximum list = foldl1 myMax list

or, in pointfree format,

myMaximum :: Ord a => [a] -> a
myMaximum = foldl1 myMax

If you look at the actual definition of maximum in Data.List, you'll see it uses this same method.

Answer 3

map maps a function over a list. It transforms each thing1 in a list to a thing2.

What you want is to find the biggest difference between two neighbours, which you can't do with map alone. I'll assume you're only looking at numbers for now, because that's just easier.

diffs :: (Num a) => [a] -> [a]
diffs [] = []
diffs [x] = []
diffs (x1:x2:xs) = abs(x1-x2) : (diffs$x2:xs)

mnd :: (Num a, Ord a) => [a] -> a
mnd [] = 0
mnd [x] = 0
mnd xs = maximum$diffs xs

So diffs takes each list item one at a time and gets the absolute difference between it and its neighbour, then puts that at the front of a list it creates at it goes along (the : operator puts an individual element at the front of a list).

mnd is just a wrapper around maximum$diffs xs that stop exceptions being thrown.