Haskell using foldr

Question

Hi I am new to Haskell and I am a little lost. I have been given this to do but can't work it out.

---

Using only foldr, the Boolean operation (||) and False, define a function

or_list :: [Bool] -> Bool

so that

or_list [b1, b2,...,bn] = b1 || b2 ||...|| bn

Note that

or_list [] = False

---

I come up with something like this

or_list :: [Bool] -> Bool
or_list [0..n] = foldr False (||) [0..n] 

But don't really get how foldr works. If anyone could point me down the right road it would be a big help.

Answer 1

You've almost got the definition right, but your syntax is a bit off. You can't have a pattern match like

or_list [0..n] = ...

this just isn't valid syntax. In fact, you don't need to pattern match at all, you could just do

or_list bs = foldr False (||) bs

The next problem can be revealed by looking at foldr's type:

foldr :: (Bool -> Bool -> Bool) -> Bool -> [Bool] -> Bool
-- Simplified from its more general type

Notice that its first argument is a function that takes two boolean values, and the second argument is simply a boolean. You have

foldr False (||) bs

But False isn't a function and (||) isn't a boolean. If you swap them you'd get

foldr (||) False bs

And then your definition would be correct!

---

How does this work? Folds are a generalization of a simple recursion, it's quite often that you have a function that you're applying to an argument that also depends on the last value computed. These sorts of recursions are useful for turning a list of values into a single value. The definition of foldr is pretty simple and I think it helps explain how the fold works

foldr f initial [] = initial
foldr f initial (x:xs) = f x (foldr f initial xs)

So if we were to plug in some values and expand it

  foldr (||) False [False, False, True]
= False || (foldr (||) False [False, True])
= False || (False || (foldr (||) False [True]))
= False || (False || (True || (foldr (||) False [])))
= False || (False || (True || (False)))
= False || (False || True)
= False || True
= True

Another way to look at it is that it replaces : by f and [] by initial in a list, so if you have

False : False : True : []

And you apply foldr (||) False to it, you would replace every : by || and the [] with False, associating right (the r part of foldr), so

False || (False || (True || (False)))

Which is the same as the expansion we got above. A foldl works in the opposite association, so foldl (||) False looks like

(((False) || False) || False) || True
-- ^ initial

So the difference is basically what end the initial value gets stuck on and where the parenthesis are.

Answer 2

The foldr function from the Prelude is a higher order function that takes a function f of type (a -> b -> b) and applies it to a list of type [a] resulting in a list of type [b]. It also takes a initial element z that is applied to the first application of f

Symbolically the reduction like this in pseudocode:

foldr f z [a,b,c,...,n] == f a (f b (f c (... (f n z)...)))

So for your function you need something like this:

foldr (||) False [a,b,c,...,n] = a || (b || (c ... (n || False)))

Hope that helps with intuition for foldr.

Answer 3

You have the definition of:

or_list :: [Bool] -> Bool

right.

Lets look at the second line:

or_list [0..n] = foldr False (||) [0..n]

So actually this is pretty close to what is needed, but there are a couple problems. First of let's look at the:

or_list [0..n] = ...

This should instead be probably something like:

or_list (x:xs) = ...

Refer to this as to why. Next, I will give you some hints. Pay close attention to the signature of foldr, You're not quite giving the correct order of parameters. Also, you need to handle the case of an empty list [] which is actually mentioned in the link I gave you.