Recursion over lists in Haskell

For instance, i have a list like ['a','b','c','d','e'].

I want to do something like this:

First do something with the firs开发者_Python百科t two elements, f 'a' 'b'

Then do the same thing with the return value of f and next element in the list, result = f 'a' 'b', lets say like f result 'c'. Then f resultof(result 'c') 'd' and so on.

How can i do something like this?

First let's consider that function f that you have. It takes some sort of accumulated value, a plain value, and combines them into a result. So, in the type signature, we'll say a for the type of the accumulated value, v for the type of the value, and r for the type of the result.

f :: a -> v -> r

Now we want to create a folding function that uses f and a list of values.

someFold :: (a -> v -> r) -> [v] -> ?

What should it return? It should yield something of the resultant type r, right? Notice now that a and r should actually be the same type, since we keep feeding the result of f into it's first argument again.

someFold :: (a -> v -> a) -> [v] -> a

Now one thing's missing. How do you get the very first a? There are two ways to look at that. Either you just pick the first value, in which case a is the same type as v, or you specify a base value, so a could actually be different than v. Let's go with the latter, since that's more interesting. Let's also decide to move left to right in this list. (That's what you need, right?)

someFold :: (a -> v -> a) -> a -> [v] -> a

So...how do we implement it? It'll be recursive, so let's start with the base cases.

someFold f acc [] = acc

If we hit the end of the list, then we've accumulated enough, right? That was easy. So how about the recursive case? From what you said, at each step we should apply f to the "accumulated value so far" as the first argument, and the "first value of the list" as the second. f acc x. Then we keep folding, using that as our new "accumulated" value.

someFold f acc (x:xs) = someFold f (f acc x) xs

Easy, right? But...what if we want to do like you said and start the function by taking the first two values of the list? Also easy. Just take the first element, and call it the original "base" accumulator!

someFold1 :: (v -> v -> v) -> [v] -> v
someFold1 f (x:xs) = someFold f x xs

Notice that since a is the same type as v for this special case, the function someFold1 has a very amusing type signature. If you understood this explanation, then congrats. We've just implemented foldl and foldl1.

Prelude> foldl1 min "abcde" -- "abcde" is sugar for ['a','b','c','d','e']
'a'

In real code, you should actually use foldl' and friends.

Sounds like homework. Take a look at folds.

In this case, the problem with a fold is, that it usually processes on element at a time. You could try to manually roll a fold.

Assume, you have your function f, that gets two elements at a time and the accumulator (the result of the last iteration) fed. Then you function looks like this:

fold2 :: (a -> a -> b -> b) -> [a] -> b -> b
fold2 f accum (x:y:zs) = fold2 f (f x y) zs
fold2 _ accum []       = accum
fold2 _ _     _        = error "odd number of elements"

Try to understand this. fold2 shaves the top two elements of the list of and feeds it into f. The result this is then passed as the new accumulator to the recursive call. This is done until the list is empty.