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.