开发者

Why foldl1 fails applying the (==) operator?

From prelude:

foldl1: it takes the first 2 items of the list and applies the function to them, then 开发者_开发技巧feeds the function with this result and the third argument and so on.

Why is not possible to write something like this?

foldl1 (==) [6, 6, 6]
foldl1 (\x y -> x == y) [6, 6, 6]


If you want to check if all of the elements of a list are equal, a quick solution is

allEqual [] = True --(edit: this case is not necessary as pointed out by sepp2k)
allEqual xs = all (== head xs) xs

Somebody will write a more elegant way to do this, I am sure, but this is serviceable.

Edit: Thanks to sepp2k for the suggestions.


EDIT: Antal points out that my reasoning was incorrect. Here is the relevant part of the comment that gives the real reasoning (I feel bad taking this verbatim, but this answer was accepted so I can't delete it):

The reason this doesn't work is that the type of foldl1 is (a -> a -> a) -> [a] -> a, but the type of (==) is Num a => a -> a -> Bool. Since Bool isn't a Num, (==) type doesn't match a -> a -> a, and so the application of foldl1 is rejected. If it were accepted, you'd end up with a situation where you were trying to do True == 6, but the type system never gets you get that far in the first place.

Original answer (latter reasoning incorrect):

== will take two Ints and return a Bool. After the first iteration your example list becomes [True, 6]. It then tries to compare True to 6 which fails.


Here is another version:

allEqual xs = and $ zipWith (==) xs (tail xs)


If you want to use a fold, I would suggest this modification:

allEqual xs = foldr (\x acc -> x == head xs && acc) True xs

This is very similar to the already-suggested all approach. Note that both this and the all approach can work on infinite lists (as long as the answer is False).

For very long finite lists, in very rare cases you might get better performance out of a strict left fold:

allEqual xs = foldl' (\acc x -> acc && x == head xs) True xs

But the right fold is generally better for this problem, since (in this implementation) it only performs a number of folding steps equal to length $ takeWhile (== head xs) xs. The left fold will perform length xs folding steps every time.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜