Recursion over lists in Haskell

Tag: list , haskell , recursion , fold Author: wjy2006218 Date: 2011-02-28

For instance, i have a list like ['a','b','c','d','e'].
I want to do something like this:
First do something with the first 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?

You may need to be a lot clearer about what your functions actually do: what would a type signature for f look like? Take the example ['a','b','c']: can you write out exactly what the end result should look like? Is it going to be (f (f 'a' 'b') 'c') or something different? What does this imply for the signature for f, and once you know that, can you adapt the fold answers below to help you finish it up?
Normally I would talk you through to the type signature, and then "Stop. Hoogle time!" But for this case I felt you might appreciate a little more hand-holding in understanding folds. See also LYAH # folds

Best Answer

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.

comments:

Thanks, this is what i was trying to understand.

Other Answer1

Sounds like homework. Take a look at folds.

comments:

Since i'm a newbie in functional programming, and there is no looping in haskell, its a little bit hard to get used to it. well folds may work, thanks.
Folds are in fact the basic "looping" mechanism in functional languages. Learn them and it'll take you a long way.
-1 While I agree that homework questions should not be answered outright, I also think that answers should be helpful and try to dig into the problem a little.

Other Answer2

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.

comments:

Ok i got this. But i have another problem here. Inside the fold the return value of f(x y) is not the same type as in the list. For instance i have chars in the list, but f returns int type.
Ah! I kind of misinterpreted your question. I thought you want to feed two elements at a time into f. Oops... I'm going to remove this answer then.
Actually the scenario is like this: f (g x) (g y) -> i first send the two elements x and y to g then their result to f. Then i want to send third element also like g head(xs). and its like f( (f (g x) (g y) ) head(xs) ).