Writing a high order function to capture common pattern haskell

Question

f1 [] = 1
f1 (x:xs) = x * f1 xs

f2 [] = 0
f2 (x:xs) = 1 + f2 xs

f3 [] = 0
f3 (x:xs) = x + f3 xs

f4 [] = []
f4 (x:xs) = x ++ f4 xs

These all have a common behavior, how exactly can I identify the pattern and write a high order function to capture it?

Answer 1

All* your functions have the form:

fn [] = P_0
fn (x:xs) = P_1 x (fn xs)

Where P_0 and P_1 are some constants. I'll call P_0 zero, and P_1 combine, and add them to the function:

-- P_0  P_1     list   = result
fn zero _       []     = zero
fn zero combine (x:xs) = combine x (fn zero combine xs)

There we go. Now we have f1 = fn 1 (*), f3 = fn 0 (+), and f4 = fn [] (++). f2 is a little weird, but you can work it out: f2 = fn 0 (\_ b -> b+1).

Asking GHCi the type gives us that fn :: b -> (a -> b -> b) -> [a] -> b, and Hoogling shows us that this function fn is actually the function foldr:

foldr :: (a -> b -> b) -> b -> [a] -> b
--       ^combine         ^zero

So there you go: folds, or particularly right folds (the r in foldr means right) is the general pattern you're looking for.

By the way, there are also left folds. I'll leave you to try to work out what those might be. Hoogle could also help you here.

There's another pattern you could see here, called Monoids, but I'll also leave that to you, since it seems out of scope for this question.

---

* This may look weird for f2 (x:xs) = 1 + f2 xs, because there isn't an x involved in the result, but this is just the case where P_1 a b = 1 + b, which is still technically the same form.

Answer 2

It looks like you can use foldr to represent all of them.

foldr (*) 1 [1,2,3]  --f1

foldr (\_ a-> 1 + a) 0 [1,2,3]  --f2

foldr (+) 0 [1,2,3]  --f3

foldr (++) [] ["a","b","c"]  --f4

They all need a list, an init value and an operator. They all apply the operator from right to left: e.g f1 [1,2,3] = 1*2*(3*1) So you can use foldr to parameterize the operator and the init value.