How to check if next element in a list is greater than the previous in Haskell?-CodePudding

(I am currently doing an online course on Haskell and this is an exercise. I am not looking for answers, but simply for some pointers on how to proceed!)

I have trouble wrapping my head around this. In imperative languages I would simply use a loop, but since Haskell doesn't really have those I am left scratching my head.

I need to write a function nextIsGreater :: [Int] -> [Int] that, given a list of numbers, produces a list with all elements of the input list such that the element is followed by a greater number in the input list (the next number is greater).

Here is what I've managed to come up with so far.

nextIsGreater :: [Int] -> [Int]

nextIsGreater xs = [x | x <- init xs, y <- tail xs, x < y]

So far it works if I have only two numbers in the list. Say [0,5], it returns [0] as it is supposed to. If I have, say [0,5,6] then my code seems to check the 0 against both of the next numbers in the list and returns [0,0,5], when it should return [0,5]. How could I compare each adjacent number to eachother?

CodePudding user response：

Not a bad attempt, but

   [x | x <- init xs, y <- tail xs, x < y]

corresponds to a nested loop: you choose x from init xs, and then for each of these choices you pick all possible y from tail xs.

To make the idea work as intended, you'd need to use {-# LANGUAGE ParallelListComp #-} or equivalently zip the sources:

nextIsGreater xs = [x | (x,y) <- zip (init xs) (tail xs), x<y]

But there's a simpler way to obtain all choices of two consecutive elements, with tails:

nextIsGreater xs = [x | (x:y:_) <- tails xs, x<y]

CodePudding user response：

The intention of this exercise is almost certainly to have you write a standard recursive solution using pattern matching, not use list comprehensions or higher level functions or anything like that.

If the course is any good, you should already have covered some recursive list-to-list transformations, functions with definitions of the form:

foo :: [Int] -> [Int]
foo (x:xs) = ... something involving "x" and "foo xs" ...
foo [] = ...

or similar, and you're expected to write something along the same lines.

Here's a first hint, with further spoilers below.

A simple way of writing a recursive function that operates on adjacent elements of lists is to write a pattern that names the first two elements:

foo (x:y:zs) = ...

The "..." can operate on x and y, and then perform a recursive call to process the "rest" of the list. The recursive call might be either foo zs or foo (y:zs) (or switch between those based on some condition), depending on what the function is doing.

Because this pattern will only match lists with at least two elements, you will usually also need patterns to match both one-element and empty lists:

foo [x] = ...
foo [] = ...

If that's not clear enough, let me refresh your memory on basic recursive list-to-list transformations starting with an example that doesn't inspect adjacent elements.

SPOILERS

Suppose we want to filter out all even elements from a list. A recursive solution would consider the two cases:

evens (x:xs) = ...
evens [] = ...

For the first case, the extraction of all evens from x:xs either includes x plus all the evens from xs (i.e., evens xs) or excludes x and includes only evens xs, depending on whether or not x itself even:

evens (x:xs) | even x = ...
             | otherwise = ...

In particular, if x is even, the answer should include x together with evens xs:

evens (x:xs) | even x = x : evens xs

and if x is odd, the answer just should include evens xs:

             | otherwise = evens xs

The final case is the subset of even numbers from the empty list, which is just the empty list:

evens [] = []

giving the complete definition:

evens :: [Int] -> [Int]
evens (x:xs) | even x = x : evens xs
             | otherwise = evens xs
evens [] = []

The main difference in your example is that the decision to include x depends not only on x but on the element appearing after x, so let's consider a slightly different problem: take a list and output all elements that are followed by an even number.

We might consider starting with a similar structure:

beforeEvens (x:xs) | ... = x : beforeEvens xs     -- include x
                   | otherwise = beforeEvens xs   -- exclude x
beforeEvens [] = []

where "..." checks to see if the element after x (i.e., the first element of xs) is even. For example, we might call a separate function to check this:

beforeEvens (x:xs) | headIsEven xs = x : beforeEvens xs
                   | otherwise     = beforeEvens xs
beforeEvens [] = []

You ought to be able to write a decent definition of headIsEven to complete this. Bonus points if instead of using head, it uses pattern matching. Note the special case headIsEven [] should return False.

A more direct approach, though, is to take advantage of the fact that patterns can be used to examine multiple elements at the start of the list. Here, we match a pattern that names the first two elements x and y, plus the rest of the list zs:

beforeEvens (x:y:zs) | even y = x : beforeEvens (y:zs)
                     | otherwise = beforeEvens (y:zs)
beforeEvens [x] = []
beforeEvens [] = []

Note a couple of tricky points here. If we match against the pattern (x:y:zs), then we have to be careful about whether we recurse on y:zs or zs alone. It depends on whether y should or shouldn't be considered for inclusion in the output. Also, the pattern (x:y:zs) won't match a singleton list, so we need an extra pattern match on that.

Because the last two cases are the same, we can combine them into a single case:

beforeEvens (x:y:zs) | even y = x : beforeEvens (y:zs)
                     | otherwise = beforeEvens (y:zs)
beforeEvens _ = []

You should find it relatively straightforward to modify beforeEvens to write your nextIsGreater function.