Haskell, Create a function given a specific type

Question

I read many similar topics and still don't understand. So the question is to create a function that has a specific type for example given type Integer-> Integer a function that has that type is \x-> x+1. How to find lambda functions for the following types:

(((Int → a) → a) → b) → b
(a -> b) -> c
a → (a → a)
(b -> c) -> (a -> b) -> a -> c

I solved 4. by guessing:

\f g a -> f (g a)

Three variables after lambda, f which has type b->c, g has type a->b, and a has type a.

:t \f g a -> f (g a)

I don't really get the steps just that there are inputs of type b->c, a->b and a. Then I guessed the order.

For 1. there is just one input so it should be \f-> \g->....

chi · Accepted Answer · 2022-05-17 17:27:55Z

One of the best ways to solve these exercises in practice is to use holes: write _ for a hole to be filled and read from GHCi about the type of that hole

> foo :: (((Int -> a) -> a) -> b) -> b ; foo = _
    * Found hole: _ :: (((Int -> a) -> a) -> b) -> b

The hole is a function. Let's use a lambda then.

> foo :: (((Int -> a) -> a) -> b) -> b ; foo = \f -> _
    * Found hole: _ :: b
    * Relevant bindings include
        f :: ((Int -> a) -> a) -> b

The hole must have type b. No more lambdas. We can't create a value of type b, unless we somehow apply f (note the printed type of f).

> foo :: (((Int -> a) -> a) -> b) -> b ; foo = \f -> f _
    * Found hole: _ :: (Int -> a) -> a

Ah, now the hole is a function again. Another lambda.

> foo :: (((Int -> a) -> a) -> b) -> b ; foo = \f -> f (\g -> _)
    * Found hole: _ :: a
    * Relevant bindings include
        g :: Int -> a

Well, now we need to produce a. With g :: Int -> a at our disposal it looks easy.

> foo :: (((Int -> a) -> a) -> b) -> b ; foo = \f -> f (\g -> g 42)

No more holes -- done.

Note that your 2) (a -> b) -> c is impossible to realize properly -- there is no way to produce a c from that input. You can only write non-terminating (or crashing) programs with that type.

Guru Stron · Accepted Answer · 2022-05-17 15:20:41Z

0

(b -> c) -> (a -> b) -> a -> c represents a function with 3 polymorphic parameters, first 2 parameters are also functions, first one is b -> c (function accepting b and returning c) and second one is a -> b (function accepting a and returning b) (see higher order functions). Lambda \f g a -> f (g a) has three parameters and is implemented by result of calling g with parameter a passed to f.

answered May 17, 2022 at 15:20

Guru Stron

150k11 gold badges186 silver badges232 bronze badges

Collectives™ on Stack Overflow

Haskell, Create a function given a specific type

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related