Reputation: 91

Haskell function example

Can someone give an example of a function with the following signature:

f :: a -> b -> (a -> b)

f takes two arguments, of type a and b, and returns a function which takes an argument of type a and returns an element of type b.

Our teacher gave us today this extra exercise and said it is really hard. I tried to write it using lambda expressions but I failed.

It is a really interesting exercise and, if someone figures out how to do it, please respond to this question. Thank you!

Upvotes: 2

Answers (5)

Will Ness

Reputation: 71119

f a b c = const b (asTypeOf c a)      -- answer by md2perpe
        = const b (f c)
        = const b . f $ c
        = ((. f) . const) b c         -- answer by Sassa NF

this is a (recursive) definition, not an expression. So if you'd want to find an expression with this signature,

f  = const ((. f) . const) 
   = (const . (. const)) (. f)
   = ((const . (. const)) . flip (.)) f
   = fix ((const . (. const)) . flip (.))

fix is from Data.Function. asTypeOf is hardly a primitive combinator, as it is itself defined with the use of explicit type signatures, asTypeOf :: a -> a -> a ; asTypeOf = const. Use of [] was suggested:

f a b c = const b ( (a:) . (c:) )

i.e.¹

f   = flip ((.) . const) . (. (:)) . (.) . (:)

Pick you poison. :)

¹for some reason, lambdabot produces the wrong const const here (with the wrong, general signature). I tricked it by running @pl \a b c -> const const b ( (a:) . (c:) ) which produced flip ((.) . const const) . (. (:)) . (.) . (:).

Upvotes: 2

Sassa NF

Reputation: 5406

There recently has been a question like this. Since there is no other requirement about what that returned value is, you can return the same b that was given, and ignore both values of type a. b->a->b is const. So f _ = const is the shortest function that will ignore the first and the third arguments, and return a value of the same type as the second argument. Yet, it doesn't bind the types of the first and the third arguments to be the same. We can do that by feeding both of them as the same argument to f.

One of the shortest ways to do that is through composition: f _ = (.f).const Now because the third argument is fed into f as the first argument, the types of these arguments will be the same.

Upvotes: 3

bennofs

Reputation: 11973

Firstly, we can omit the parentheses, a -> b -> (a -> b) is the same as

a -> b -> a -> b

(This works because of currying)

Now look at this signature. We got the following inputs:

two things of type a
one thing of type b

We need to return something of type b. But now look, there is only one way to do this (if we ignore undefined for a moment), because we only got one value of type b! We just return that value:

f :: a -> b -> a -> b
f _ b _ = b -- We ignore both values of type a, because we cannot do anything with a's

So above I said that there is only just one solution if we ignore undefined, error ..., let v = v in v and similar (Those a called bottom values, because they either crash the program or won't terminate when evaluated). Can you find a definition that uses one of them?

Edit

As noted in the comments, this function actually has a more general type. I assumed that the exercise was to find a function which can be of that type, not a function whose inferred type is the given type. If that's not what you want, see @bheklilr's answer

If you're interrested in short, but nigh unreadable definitions, see a similar question on codegolf

Upvotes: 5