Haskell - last filter element

Question

I want to filter out the last element of a list that does not satisfy the property. Example:

smallerOne :: a->Bool smallerOne x = x < 1 

The function filter Last should give

 filterLast smallerOne [1, -2, -3, -4, 5] [1, -2, -3, -4] //Filters the last element that is not smaller than 1 

Here is my code (I start so sorry for the failed attempt)

 filterLast :: (a -> Bool) -> [a] -> [a] filterLast p [] = [] filterLast p xs | p (last xs) = filterLast p (init xs) : last xs | otherwise = init xs 

thanks for the help

Answer 1

 smallerOne :: (Ord a, Num a) => a -> Bool smallerOne x = x < 1 filterLast :: (a -> Bool) -> [a] -> [a] filterLast p (x:[]) = if (px) then x:[] else [] filterLast p (x:xs) = x : filterLast p xs 

This is the solution to your problem. Now, also some explanation:

lessOne :: (Ord a, Num a) => a → Bool

you must enable the class restriction of Ord and Num , because you are trying to order numbers through this comparison operator < . You can read here: http://learnyouahaskell.com/types-and-typeclasses#typeclasses-101

filterLast is implemented through pattern matching , Haskell is pretty smart and will go into a branch that will correspond to this list, so it will go into this branch:

filterLast p (x: []) = if (px) then x: [] else []

only if one element remains, i.e. your last element .

You said you are a beginner, I really recommend you this tutorial, http://learnyouahaskell.com/chapters , which is pretty cool.

Answer 2

The minimal change that will lead to filterLast compiling is to use (++) instead of (:) , as in:

 filterLast p xs | p (last xs) = filterLast p (init xs) ++ [last xs] 

(The remaining lines remain unchanged.) The function (:) designed specifically to place one additional element at the top of the list, which you do not want to do here. For smallerOne you can simply change the type signature as suggested in the error message, like this:

 smallerOne :: (Num a, Ord a) => a->Bool 

Answer 3

Here is one possible implementation of filterLast :

 filterLast :: (a -> Bool) -> [a] -> [a] filterLast p = go [] where go chunk xs = case span p xs of (left, []) -> left (left, (r:right)) -> chunk ++ left ++ go [r] right 

The idea is to reuse the span to split the sequence into two parts: the left half, which all satisfies the predicate, and then the right half, starting with the first element that does not satisfy it. If there is no right half, then we can simply return the left half untouched. Otherwise, we must:

• Save the first element of the right half as a candidate element, which will be included only if we can find a later element that does not satisfy the predicate
• Include the previous candidate element, if any, as a result.

This is significantly more efficient for large lists (and especially endless lists!) Than the approach used in your question with repeated calls to last and init . But if this is not important to you, then simply applying the corrections proposed in the answer of Daniel Wagner, you will get a function that will be easier for you to understand.

Change As suggested in the comments, you can fix one corner case (an endless list of elements that satisfy the predicate) by renaming this function to filterLast' and then defining a new filterLast that delegates to it:

 filterLast :: (a -> Bool) -> [a] -> [a] filterLast p xs = left ++ filterLast' p right where (left, right) = span p xs 

Note that there are still some sequences where this diverges without generating output, for example filterLast (< 1) $ 10 : repeat -1 . But I think that for any implementation this is impossible, since you will never know whether to include 10 in the output list, since you will never find another element greater than 1.

Answer 4

What you want to do is reverse the list and take elements until they satisfy this property. At that moment, when the element satisfies the property, you drop it and take the rest of the list. This translates the haskell code quite naturally.

 filterLast :: (a -> Bool) -> [a] -> [a] filterLast p = reverse . uncurry (++) . dropHeadSnd . span p . reverse where dropHeadSnd (x, y) = (x, tail' y) tail' [] = [] tail' (x:xs) = xs 

(++) reduces the efficiency of your code, and although its asymptotic efficiency does not eliminate, eliminating (++) will improve your performance.

 filterLast :: (a -> Bool) -> [a] -> [a] filterLast p = reverse . helper . reverse where helper [] = [] helper (x:xs) | px = xs | otherwise = x:helper xs 

Both of these functions use two iterations over the list. However, remember that with recursion you can get information both behind and in front. We use a recursive call to find out if there are any subsequent elements for which "p" is executed.

 f :: (a -> Bool) -> [a] -> [a] fp = snd . helper where helper [] = (False, []) helper (a:as) | pa && flag = (flag, a:as') | pa = (True, as') | otherwise = (flag, a:as') where (flag, as') = helper as