CODEWITHSUNDEEP
haskellfold
SilentDev
SilentDev

Reputation: 22757

Making filter using foldr

I'm trying to make filter using foldr. I have a solution, but don't know why my version does not work.

foldr works like this:

>>>foldr op z (xs:x)
x op z

then repeats, correct? When x is the last element in the list.

Now, I have

myFilter pred = foldr op z
  where
    z = []
    op x xs = if pred x then x

this does not work, gives a parse error (possibly incorrect indentation or mismatched brackets) error.

The operation just gives x to pred and if it is true, returns x, otherwise skips it. The way foldr works is that it keeps looping on the xs list that is passed. So why do I need to do 

 op x xs = if pred x then x : xs else xs

and tell it to continue with xs even if foldr already does the continuing?

Upvotes: 3

Views: 950

Answers (3)

chepner
chepner

Reputation: 531938

foldr encapsulates the recursion involved in combining an element from the list with the result of folding the rest of the list. xs is not the tail of your input; it's the result of folding the tail of your input.

You can emphasize this a bit by focusing on what you want op to do, and de-emphasizing what it operates on, by refactoring 

op x xs = if pred x then x : xs else xs

to 

-- (x:) xs == x:xs
-- id xs == xs
op x xs = (if pred x then (x:) else id) xs

which can be eta-reduced to

op x = if pred x then (x:) else id

In other words, given the first element of the list, what will you do with it: prepend x it to the recursive result, or return that result as-is?

Upvotes: 5

Benjamin Hodgson
Benjamin Hodgson

Reputation: 44634

foldr :: (a -> b -> b) -> b -> [a] -> b loops over an input list of as and manipulates a b (representing the loop's state). op's job is to take an a from the input list, the current state b, and compute a new state. foldr makes sure that op is called for every item in the list.

In the case of your filter, b happens to also be a list of as. So your code is talking about two different lists of as — the input list and the output list. Your op has to decide should I put this x in the output list or not?

To clarify, here is your code with the variables named a bit more suggestively.

filter :: (a -> Bool) -> [a] -> [a]
filter pred = foldr addToOutputIfNecessary initialOutput
  where
    initialOutput = []
    addToOuputIfNecessary itemFromInput currentOutput =
      if pred itemFromInput
      then itemFromInput:currentOutput
      else currentOutput

So when we return currentOutput from addToOutputIfNecessary, it's not about telling foldr to continue. (foldr will always continue to the next input element by itself — you don't need to tell it to continue.) It's just saying that the loop's state hasn't changed this iteration; we've decided not to add an item to the output list.

Hope this helps! Let me know in the comments if there's anything you don't understand.

Upvotes: 5

Code-Apprentice
Code-Apprentice

Reputation: 83557

Let's take a look at the type of foldr for a list:

foldr :: (a -> b -> b) -> b -> [a] -> b

Now you are using it like this:

foldr op z

From the type signature of foldr we see that the function op must return something of type b which is the same type as z. Since you do z = [], this must be a list. So the result of op x xs must be a list.

Additionally, keep in mind that if...else in Haskell is an expression. This means that it must evaluate to some value no matter if the condition is true or false. In other languages, the else is optional because if is a statement. In Haskell, the else is not optional.

So why do I need to do

op x xs = if pred x then x : xs else xs

and tell it to continue with xs even if foldr already does the continuing?

One reason is that op must always return a value. This value will be used by foldr to continue its calculation. Without it, foldr is unable to continue, and in fact your code won't even compile as you saw.

Upvotes: 3

Related Questions