lee1234567890
lee1234567890

Reputation: 7

haskell function given type signature dealing with list

mapNew :: a -> (a -> b -> c) -> [b] -> [c]

Given this type signature, what kind of function should mapNew be?

I know the return type is list.

Upvotes: 0

Views: 98

Answers (1)

cassandracomar
cassandracomar

Reputation: 1519

This looks a lot like a homework question. If it is, I strongly recommend you try and answer this question for yourself. With that said, I'll walk you through how I would formulate an answer to this question and hopefully give you some insight into how you should approach questions like this.

We know that mapNew has type a -> (a -> b -> c) -> [b] -> [c]. This looks a lot like the existing Prelude function map :: (a -> b) -> [a] -> [b]. So we probably want to write our answer in terms of map.

mapNew :: a -> (a -> b -> c) -> [b] -> [c]
mapNew a f bs = ...

We always start by writing out the function with the arguments it takes so that we can see what pieces we have to work with. Knowing that we only have a single a and need to always pass it to f for each element b in bs, we can add a where clause for this partial application:

mapNew :: a -> (a -> b -> c) -> [b] -> [c]
mapNew a f bs = ...
    where fa :: b -> c
          fa = f a

Given this, we can now write our answer in terms of map.

mapNew :: a -> (a -> b -> c) -> [b] -> [c]
mapNew a f bs = map fa bs
    where fa :: b -> c
          fa = f a

Most haskell programmers would simplify this definition to:

mapNew :: a -> (a -> b -> c) -> [b] -> [c]
mapNew a f bs = map (f a) bs

since (f a) is exactly the partially applied function fa. Further, we can eta-reduce this expression to:

mapNew :: a -> (a -> b -> c) -> [b] -> [c]
mapNew a f = map (f a)

The crux of this answer is in the statement "Knowing that we only have a single a and need to always pass it to f for each element b in bs". How do I know this?

Because of parametric polymorphism we can't inspect any values of type a. This means that the only value of type a we have available to us is the one passed to mapNew. Further, since f takes a single b and produces a single c, we know that we must first get a b out of the provided list in order to apply f to it. This is exactly what map does, and by partially applying f to a we get the first argument we want to pass to map.

Upvotes: 5

Related Questions