Problem using map with a list of lists in Haskell

Question

Hi

I am using Haskell to solve problem 99 in euler project, where I must find the maximum result from a list of base exponent pairs.

I came up with this:

prob99 = maximum $ map ((fst)^(snd)) numbers

Where the numbers are in the form:

numbers = [[519432,525806],[632382,518061],[78864,613712]..

Why doesn't this work? Do I need to change the format of the numbers? Is there a simple optimisation here I am not thinking of, like a more efficient method of exponentiation?

Answer 1

Because fst and snd are defined on pairs (types fst :: (a,b) -> a and snd :: (a,b) -> b). And second problem is with (fst)^(snd), you cannot power function on function.

prob99 = maximum $ map (\xs -> (head xs)^(head (tail xs))) numbers

or

prob99 = maximum $ map (\xs -> (xs !! 0)^(xs !! 1)) numbers

Answer 2

What's not working is your program's type consistency. You're trying to apply function (^), simplified type Int -> Int -> Int, to arguments of type (a,a) -> a (not an Int).

The easiest way would probably be to directly generate a list of pairs instead of a list of lists. You can then (almost) directly appply the (^) function to them, uncurrying it first.

numbers = [(519432,525806),(632382,518061),(78864,613712)...
prob99 = maximum $ map (uncurry (^)) numbers

If you're stuck with your sublists, you could pattern-match them directly, improving a bit on Matajon's solution:

prob99 = maximum $ map (\[x,y] -> x^y) numbers

Or, if you're into point-free style all the way, you can make good use of the operators in Control.Arrow. (which in this case doesn't help much as far as verbosity goes)

prob99 = maximum $ map ((!!0) &&& (!!1) >>> uncurry (^)) numbers

Answer 3

Give a man a fish, and you'll feed him for a day, teach a man to fish, and you'll feed him for a lifetime.

Jonno, you should learn how to let GHC's error messages help you, and the "undefined drop in" method (let's focus on that for now).

ghci> let numbers = [[519432,525806],[632382,518061]]
ghci> -- so far so good..
ghci> let prob99 = maximum $ map ((fst)^(snd)) numbers

<Bam! Some type error>

ghci> -- ok, what could have gone wrong?
ghci> -- I am pretty sure that this part is fine:
ghci> let prob99 = maximum $ map undefined numbers
ghci> -- yes, it is fine
ghci> -- so the culprit must be in the "((fst)^(snd))" part
ghci> let f = ((fst)^(snd))

<Bam! Some type error>

ghci> -- whoa, so this function never makes sense, not just where I used it..
ghci> -- is it doing what I think it is doing? lets get rid of those braces
ghci> let f = fst ^ snd

<Bam! Same type error>

ghci> -- yeah I got my syntax right alright
ghci> -- well, can I exponent fst?
ghci> let f = fst ^ undefined

No instance for (Num ((a, b) -> a))
  arising from a use of '^' at <interactive>:1:8-22
Possible fix: add an instance declaration for (Num ((a, b) -> a))
In the expression: fst ^ undefined
In the definition of 'f': f = fst ^ undefined

ghci> -- duh, fst is not a Num
ghci> -- this is what I wanted:
ghci> let f x = fst x ^ snd x
ghci> -- now lets try it
ghci> let prob99 = maximum $ map f numbers

<Bam! Some type error>

ghci> -- still does not work
ghci> -- but at least f makes some sense now
ghci> :t f

f :: (Num a, Integral b) => (a, b) -> a

ghci> -- lets find an example input for it
ghci> head numbers

[519432,525806]

ghci> :t head numbers

head numbers :: [Integer]

ghci> -- oh, so it is a list of two integers and not a tuple!
ghci> let f [a, b] = a ^ b
ghci> let prob99 = maximum $ map f numbers
ghci> -- no error?
ghci> -- finally I got the types right!