CODEWITHSUNDEEP
haskell
user342673
user342673

Reputation: 674

unclear about foldl type definition

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl step zero (x:xs) = foldl step (step zero x) xs
foldl _    zero []     = zero

I don't quite understand why does (a -> b -> a) return a, also (a -> b -> a) -> a -> [b] -> a return a. I would think it should be like: (a -> b -> c) -> a -> [b] -> c. Can someone explain that to me based on the example below. Thanks!

foldl (+) 0 (1:2:3:[])
foldl (+) (0 + 1) (2:3:[])
foldl (+) ((0 + 1) + 2) (3:[])
foldl (+) (((0 + 1) + 2) + 3) ([])
foldl (+) (((0 + 1) + 2) + 3)

Upvotes: 8

Views: 576

Answers (2)

Chris Barrett
Chris Barrett

Reputation: 3375

a represents the type of the accumulator value, and b represents the type of each element in the input. (a -> b -> a) is a function that takes an accumulator value, some item in the list, and returns a new accumulator value that can be passed onto the next step.

The type of the initial value must be a so that the first invocation of the function can receive an accumulator value. The accumulator function must take an a and return an a so that an accumulator value can be passed to each step of the fold. The final value of the fold must necessarily be an a, because that is the type of the accumulator that will be returned by the final call the fold function.

(a -> b -> c) -> a -> [b] -> c cannot represent a fold, because the folding function does not take a c. The input and output of the folding function must be the same type so the accumulator can be passed to the next fold step.

Let's see an example of what would happen if the fold function returned a c.

f :: Integer -> Integer -> Bool   -- this is a valid (a -> b -> c)
f acc n = (acc + n) > 0

Pretend we're using a dynamic language and we try to fold with f. What happens at runtime?

foldl f 0 [1]     ~ (0 + 1) > 0            == True :: Bool

foldl f 0 [1, 2]  ~ ((0 + 1) > 0) + 2) > 0 == error - no instance of (+) for Bool
                     \_________/   \
                          |         \
                         Bool      + Integer

You can see that you can't make a fold work if you try to accumulate with incompatible types.

Upvotes: 15

user1020786
user1020786

Reputation:

The return type of the folding function (of type (a -> b -> a)) must be the same as the type of its first input. This is because, looking at the (almost correct, except for the last line, which should not have the foldl (+)) evaluation you gave, the result of a previous invocation of the folding function is passed as the first input to the next invocation. Thus, the types must match. in (a -> b -> c)the types of the first argument and result only match if a ~ c (equality for types), but in this case as a and c are equal we may as well call them both a. Given that the folding function returns something of type a, the result of the whole foldl call will also be type a, as it simply returns the result of the last call to the folding function.

Upvotes: 2

Related Questions