CODEWITHSUNDEEP
haskell
teasy teasy
teasy teasy

Reputation: 11

Implementing a Haskell function from a signature

Im trying to wrap my head around Haskell and I'm having trouble trying to implement the following signature as a function. Could you guys give me an example using lambda expressions?

(b -> c) -> (a -> b) -> a -> c

Upvotes: 1

Views: 103

Answers (2)

sshine
sshine

Reputation: 16145

Try with simpler examples first. For example,

f :: a -> a
f = ...

Since f is a function of one argument, we can extend this without thinking much into:

f :: a -> a
f = \x -> ...

Picking a return value for this function, we have exactly one good candidate, x, so:

f :: a -> a
f = \x -> x

although we could also have picked undefined or error "meh", or f x, which are less useful.

Here's another simple example:

g :: (a, b) -> (b, a)
g = ...

The only pattern that matches the function's input is a pair, so:

g :: (a, b) -> (b, a)
g = \(x, y) -> ...

This doesn't have to be equivalent to swap, but it's a good candidate because it terminates.

A last example that is more complicated:

h :: ((a, b) -> c) -> a -> b -> c
h = ...

This is a function of three arguments of types (a, b) -> c, a and b, so without thinking much we can extend the answer partially:

h :: ((a, b) -> c) -> a -> b -> c
h = \f -> \x -> \y -> ...
h = \f x y -> ...

(The lower line is just a convenient way to stack curried arguments.)

Now, I gave them names f, x and y because I think f is a good, generic name for a value that contains an ->, and x and y are good, generic names for arbitrary values. I could also have picked a and b to strengthen the connection between the types of the same name, but it'd also be a little confusing. So here, x :: a and y :: b.

As for filling out the function body, I can either go by asking "How do I apply the things I've got so the types align", or I can look at the return type, c, and look at what I have available to make a value of type c. f returns c if I feed it a pair of type (a, b). I have an x :: a and a y :: b, so (x, y) :: (a, b):

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

This is incidentally curry. I don't think you can find any other solution that terminates?

For simple functions there is often only one good candidate. When you have type signatures with multiple values of the same type, you have to consider what happens if you pick one over the other. The first case I can think of is when you implement the >>= operator for the state monad.

Upvotes: 4

leftaroundabout
leftaroundabout

Reputation: 120751

Let's rename our type variables:

  • a becomes oil
  • b becomes petrol
  • c becomes co₂

Now, you already recognised what the arguments to your function are:

implementation (x :: petrol -> co₂)
               (y :: oil -> petrol)
               (z :: oil)
            = (? :: co₂)

It's sort of conventional to name functions f, g... and values a, b... _if we know nothing about the underlying types. Ok, but after we named the types, let's pick appropriate names accordingly:

implementation (car :: petrol -> co₂)
               (refinery :: oil -> petrol)
               (tankship :: oil)
            = (? :: co₂)

Or, in lambda form without the local signatures:

 implementation = \car refinery tankship -> ?

I'll leave the rest to you.

Upvotes: 2

Related Questions