Calculating type of polymorphism haskell

Question

I need to calculate types of following expressions:

curry fst
foldr const
(foldr const) . (curry fst)

First I have:

curry :: ((a, b) -> c) -> a -> b -> c
fst :: (d, e) -> d 

{}                      |   (a,b)-> c = (d,e) -> d 
{}                      |   (a,b) = (d,e) , c = d
c -> d                  |   (a,b) = (d,e)
c -> d , a ->d          |   b = e
c -> d , a ->d, b -> e  |   {}

then replace the result in a -> b -> c and you get d -> e -> d

Now similar to this I do:

foldr :: (f -> g -> g) -> g -> [f] -> g
const :: h -> i -> h



{}                      |    (f -> g -> g) =  h -> i -> h 
{}                      |    f = h , g = i, g = h
f -> h                  |    g = i, g = h
f -> h, g -> i          |    i = h
f -> h, g -> i  i->h    |    {}

then replace the result in g -> [f] -> g and you get i -> [h] -> i

Next, i have to do (foldr const) . (curry fst) but i am not sure if these results are correct. I tried anyway but got stuck. So:

(foldr const) :: i -> [h] -> i and (curry fst) :: d -> e -> d
(.) :: (j -> k) -> (l -> j) -> l -> k

then i start with:

d = (j -> k) -> (l -> j) -> l -> k, e = d -> e -> d

e = (j -> k) -> (l -> j) -> l -> k -> e -> (j -> k) -> (l -> j) -> l -> k

but it feels wrong and i cannot continue... Are my first two results correct? If they are, how should i solve the last one?

You can check this with :type in ghci. Is the purpose of the exercise to work it out for yourself? — Davislor
– Davislor, Commented May 23, 2017 at 20:09

pigworker · Accepted Answer · 2017-05-23 20:23:18Z

4

The first result is correct.

The calculation for the second result is correct until you make the substitution in the last step. Easily missed. You had (using =, rather than ->, as the latter constructs function types and thus might cause confusion)

f = h, g = i, i = h

so substituting in g -> [f] -> g gives

h -> [h] -> h

not i -> [h] -> i, because although g = i, it's also the case that i = h, so together, g = h. That is, you need either to normalise your substitution (applying each new solution to instantiate the old substitution as well as extend it, giving f = h, g = h, i = h), or to apply your substitution carefully one step at a time:

g -> [f] -> g
  -- f = h
g -> [h] -> g
  -- g = i
i -> [h] -> i
  -- i = h
h -> [h] -> h

Now, for the final step of the calculation, you have all the pieces, but you have missed the way . is an infix operator. Its first argument is foldr const which must have type j -> k. Its second argument is curry fst which must have type l -> j. The whole thing has type l -> k. So, the equations you must solve are

j -> k  =  h -> [h] -> h   -- from the first argument
l -> j  =  d -> e -> d     -- from the second argument

Now, -> associates to the right, so the first gives

j = h
k = [h] -> h

and the second gives

l = d
j = e -> d

Combining the two gives

h = e -> d

so we end up with (normalised)

h = e -> d
j = e -> d
k = [e -> d] -> e -> d
l = d

and instantiating l -> k gives the type

d -> [e -> d] -> e -> d

The function takes a default d, then a list of functions, then an input e: if the list of functions is empty, you get the default as the result; if the list is nonempty, you get the result of applying the first function to the input.

answered May 23, 2017 at 20:23

pigworker

43.6k18 gold badges124 silver badges214 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Davislor Over a year ago

Example: ((foldr const) . (curry fst)) 0 [ceiling, floor, round] 0.1

Davislor Over a year ago

Another example: ((foldr const) . (curry fst)) undefined [ceiling, undefined] 0.9

Collectives™ on Stack Overflow

Calculating type of polymorphism haskell

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related