CODEWITHSUNDEEP
haskell
keepitreal
keepitreal

Reputation: 45

Haskell - Filter Last Element

I want to filter the last element of a list that does not satisfy a property. An example would be 

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

The function filterLast 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 am a beginner so sorry for the bad attempt) 

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

Thank you for your help

Upvotes: 4

Views: 1031

Answers (4)

amalloy
amalloy

Reputation: 91857

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 repeatedly use span to split the sequence into two parts: a left half that all satisfy the predicate, and then a right half starting with the first element that doesn't satisfy it. If there is no right half, then we can just return the left half untouched. Otherwise, we have to:

  1. Save off the first element of the right half as a "candidate" item that will only be included if we can find a later element that doesn't satisfy the predicate
  2. Include the previous candidate element, if any, in the result.

This is substantially more efficient for large lists (and especially infinite lists!) than the approach used in your question, with repeated calls to last and init. But if this is not an important concern for you, then simply applying the fixes suggested in Daniel Wagner's answer will get you a function that you will find easier to understand.

Edit: As suggested in the comments, you can fix one corner case (an infinite list of items that all 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 ever producing output, such as filterLast (< 1) $ 10 : repeat -1. But I think it's impossible for any implementation to address that, because you never find out whether or not to include the 10 in the output list, since you never find another element greater than 1.

Upvotes: 4

user5199947
user5199947

Reputation: 57

What you want to do is reverse the list and take elements while they dont satisfy the property. The moment an element satisfies a property, you drop it and take the rest of the list. This translates pretty naturally into haskell code.

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

The (++) reduces the efficiency of your code and while its not the asymptotic efficiency, eliminating the (++) will improve your performance.

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

Both of the above functions use two iterations over the list. However remember with recursion you can get information from both behind and ahead. We use the recursive call to figure out if there are any subsequent elements for which 'p' is satisfied.

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

Upvotes: -1

Daniel Wagner
Daniel Wagner

Reputation: 152707

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

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

(Other lines remain the same.) The (:) function is specifically for putting a single extra element at the beginning of a list, which is not what you wanted to do here. For smallerOne, you may simply change the type signature in the way suggested by the error message, thus:

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

Upvotes: 5

flore77
flore77

Reputation: 41

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

filterLast :: (a -> Bool) -> [a] -> [a]
filterLast p (x:[]) = if (p x) then x:[] else []
filterLast p (x:xs) = x : filterLast p xs

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

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

you must include the class constraint Ord and Num, because your are trying to ordonate numbers through this < comparison operator. You can read more here: http://learnyouahaskell.com/types-and-typeclasses#typeclasses-101

filterLast is implemented through pattern matching, Haskell is pretty smart and will enter the branch that will match the given list, so he will enter this branch:

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

only when there is one element left, i.e your last element.

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

Upvotes: -4

Related Questions