Haskell: Map function with tuples

Question

I have to write a Haskell program that does the following:

Main> dotProduct [(1,3),(2,5),(3,3)]  2
[(2,3),(4,5),(6,3)]

I have to do it both with and without map function. I already did it without map, but I have no clue to do it with map.

My dotProduct without map function:

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct [] _ = []
dotProduct [(x,y)] z = [(x*z,y)]
dotProduct ((x,y):xys) z = (x*z,y):dotProduct (xys) z

So I really need help with the map version.

Answer 1

Rather than starting by trying to fit map in somehow, consider how you might simplify and generalize your current function. Starting from this:

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct [] _ = []
dotProduct [(x,y)] z = [(x*z,y)]
dotProduct ((x,y):xys) z = (x*z,y):dotProduct (xys) z

First, we'll rewrite the second case using the (:) constructor:

dotProduct ((x,y):[]) z = (x*z,y):[]

Expanding the [] in the result using the first case:

dotProduct ((x,y):[]) z = (x*z,y):dotProduct [] z

Comparing this to the third case, we can see that they're identical except for this being specialized for when xys is []. So, we can simply eliminate the second case entirely:

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct [] _ = []
dotProduct ((x,y):xys) z = (x*z,y):dotProduct (xys) z

Next, generalizing the function. First, we rename it, and let dotProduct call it:

generalized :: [(Float, Integer)] -> Float -> [(Float, Integer)]
generalized [] _ = []
generalized ((x,y):xys) z = (x*z,y):generalized (xys) z

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct xs z = generalized xs z

First, we parameterize it by the operation, specializing to multiplication for dotProduct:

generalized :: (Float -> Float -> Float) -> [(Float, Integer)] -> Float -> [(Float, Integer)]
generalized _ [] _ = []
generalized f ((x,y):xys) z = (f x z,y):generalized f (xys) z

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct xs z = generalized (*) xs z

Next, we can observe two things: generalized doesn't depend on arithmetic directly anymore, so it can work on any type; and the only time z is used is as the second argument to f, so we can combine them into a single function argument:

generalized :: (a -> b) -> [(a, c)] -> [(b, c)]
generalized _ [] = []
generalized f ((x,y):xys) = (f x, y):generalized f (xys)

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct xs z = generalized (* z) xs

Now, we note that f is only used on the first element of a tuple. This sounds useful, so we'll extract that as a separate function:

generalized :: (a -> b) -> [(a, c)] -> [(b, c)]
generalized _ [] = []
generalized f (xy:xys) = onFirst f xy:generalized f (xys)

onFirst :: (a -> b) -> (a, c) -> (b, c)
onFirst f (x, y) = (f x, y)

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct xs z = generalized (* z) xs

Now we again observe that, in generalized, f is only used with onFirst, so we again combine them into a single function argument:

generalized :: ((a, c) -> (b, c)) -> [(a, c)] -> [(b, c)]
generalized _ [] = []
generalized f (xy:xys) = f xy:generalized f (xys)

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct xs z = generalized (onFirst (* z)) xs

And once again, we observe that generalized no longer depends on the list containing tuples, so we let it work on any type:

generalized :: (a -> b) -> [a] -> [b]
generalized _ [] = []
generalized f (x:xs) = f x : generalized f xs

Now, compare the code for generalized to this:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

It also turns out that a slightly more general version of onFirst also exists, so we'll replace both that and generalized with their standard library equivalents:

import Control.Arrow (first)

dotProduct :: [(Float, Integer)] -> Float -> [(Float, Integer)]
dotProduct xs z = map (first (* z)) xs