If I write:
> let xs = [1,5,19,2,-3,5]
> foldr max 0 xs
19
> foldr1 max xs
19
And if I write (I know, the initial value is incorrect here for a generic maximum function...):
> let maximum' = foldr max 0
> maximum' xs
19
But if I write:
> let maximum2' = foldr1 max
> maximum2' xs
the response is:
<interactive>:61:11:
Couldn't match expected type `()' with actual type `Integer'
Expected type: [()]
Actual type: [Integer]
In the first argument of maximum2', namely `xs'
In the expression: maximum2' xs
I am new to Haskell. What am I doing wrong? (Can't decipher the error message...) How to use foldr1
with max
? Thanks.
EDIT (AFTER ACCEPTING ANSWER):
Just to show some more examples of the defaulting rules' effect (the answer explains these, too):
Example 1:
> let max' = max
> :t max
max :: Ord a => a -> a -> a
> :t max'
max' :: () -> () -> ()
Example 2:
> let plus = (+)
> :t (+)
(+) :: Num a => a -> a -> a
> :t plus
plus :: Integer -> Integer -> Integer
Haskell Wiki compares foldr , foldl and foldl' and recommends using either foldr or foldl' . foldl' is the more efficient way to arrive at that result because it doesn't build a huge thunk.
From HaskellWiki. The foldr function applies a function against an accumulator and each value of a Foldable structure from right to left, folding it to a single value. foldr is a method of the Foldable typeclass: foldr (++) [] [[0, 1], [2, 3], [4, 5]] -- returns [0, 1, 2, 3, 4, 5]
Difference Between foldl and foldr The difference is that foldl is tail-recursive, whereas foldr is not. With foldr and non-optimized patterns, proc is applied to the current value and the result of recursing on the rest of the list. That is, evaluation cannot complete until the entire list has been traversed.
foldr1 is a variant of foldr that has no starting value argument, and thus must be applied to non-empty lists. Note that unlike foldr, the accumulated value must be of the same type as the list elements.
In Haskell, foldl' is way more efficient than foldl because you don’t have to first build up a huge thunk chain before you can finally start reducing the expression. As I said, with foldl you have to first allocate memory on the heap for every single list item until you have the finished thunk chain.
The other very useful fold is foldl'. It can be thought of as a foldr with these differences: foldl' conceptually reverses the order of the list. One consequence is that a foldl' (unlike foldr) applied to an infinite list will be bottom; it will not produce any usable results, just as an express reverse would not.
One consequence is that a foldl' (unlike foldr) applied to an infinite list will be bottom; it will not produce any usable results, just as an express reverse would not. Note that foldl' (flip (:)) []==reverse. foldl' often has much better time and space performance than a foldr would for the reasons explained in the previous sections.
Here are a few rules of thumb on which folds to use when. foldr is not only the right fold, it is also most commonly the right fold to use, in particular when transforming lists (or other foldables) into lists with related elements in the same order. Notably, foldr will be effective for transforming even infinite lists into other infinite lists.
The problem is to do with the polymorphism of the types and GHCi's defaulting. The type of max
is polymorphic:
> :t max
max :: Ord a => a -> a -> a
In the case of maximum'
, the compiler can see that a
is some sort of number, and GHCi defaults the number to Integer:
> :t maximum'
maximum' :: [Integer] -> Integer
In the case of maximum2'
it has less clues, and defaults a
to the unit type:
> :t maximum2'
maximum2' :: [()] -> ()
If you provide a type signature, all is well:
> let maximum3' :: Ord a => [a] -> a ; maximum3' = foldr1 max
> :t maximum3'
maximum3' :: Ord a => [a] -> a
I think GHCi's defaulting rules are there to make certain other cases where the types are omitted easier -- see http://www.haskell.org/ghc/docs/7.6.2/html/users_guide/interactive-evaluation.html#id484837
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With