RankNTypes: apply the same function to pairs of different types

Question

I tried to define this function to rearrange three lists of pairs:

{-# LANGUAGE RankNTypes #-} mapAndZip3 :: (forall x. x -> fx) -> [a] -> [b] -> [c] -> [(fa, fb, fc)] mapAndZip3 f la lb lc = zipWith3 (\abc -> (fa, fb, fc)) la lb lc main = do let x = mapAndZip3 (fst) [(1,"fruit"), (2,"martini")] [("chips","fish"),("rice","steak")] [(5,"cake"),(4,"pudding")] print x -- was expecting [(1,"chips",5), (2,"rice",4)] 

At first I did not include RankNTypes or forall , but after defining this , namely the definition of liftTup , I thought that this should be enough.

But obviously this is not the case since I am still getting the error message:

 mapAndZip3.hs:8:25: Couldn't match type `x' with `(f0 x, b0)' `x' is a rigid type variable bound by a type expected by the context: x -> f0 x at mapAndZip3.hs:8:13 Expected type: x -> f0 x Actual type: (f0 x, b0) -> f0 x In the first argument of `mapAndZip3', namely `(fst)' 

I have a clearly limited understanding of the forall keyword, but from what I understood, in this case, let f accept any type. I do not understand: once in this context and used once, does the definition define “fixed” for the remaining context?

This is not like because if I replace the “chips” and “rice” with Ints, the compiler still complains, so I assume that I am assuming something is wrong (of course, if I delete the annotation like mapAndZip3 in this last case, everything works because the signature is simplified to mapAndZip3 :: (a -> t) -> [a] -> [a] -> [a] -> [(t, t, t)] , but that’s not what I want).

I also found this question , but I can’t do it if this is the same problem or not, since the function I'm trying to apply is not id , but fst or snd , functions that actually return different types (a -> b) .

Answer 1

The problem with your signature is f . Let's decompose it a bit:

 mapAndZip3 :: forall (a :: *) (b :: *) (c :: *) (f :: *->*) => (forall x. x -> fx) -> [a] -> [b] -> [c] -> [(fa, fb, fc)] 

f here is supposed to be "any level level function", in your instance it will be type f (a,b) = a . But Haskell does not allow you to abstract from type level functions, only over type constructors such as Maybe or IO . Thus, mapAndZip3 Just really will be possible, but fst does not create, but deconstructs the type of the tuple.

Type functions do not actually exist in Haskell98, they are only possible with TypeFamilies . The problem is mainly that the Haskell native language is untyped ^1, but type level functions must be full ² functions. But then you cannot define any non-trivial function (i.e., except id or type constructors) that are defined for all types. The type-type fst , of course, is not complete; it only works with tuple types.

So, to work with such functions, you obviously need to specify their context in some other way. With TypeFamilies it can work as follows:

 class TypeFunctionDomain d where type TypeFunction d :: * instance TypeFunctionDomain (a,b) where type TypeFunction (a,b) = a mapAndZip3 :: (forall x. TypeFunctionDomain x => x -> TypeFunction x) -> [a] -> [b] -> [c] -> [(TypeFunction a, TypeFunction b, TypeFunction c)] 

However, this is not quite what you want: it would be impossible to define an instance of TypeFunctionDomain in the same TypeFunctionDomain that is responsible for snd , which means that mapAndZip3 will not actually be polymorphic at all, but they work with only one function.

These problems can only be solved in type-dependent languages ​​such as Agda , where views are really just types of types, and you can define type level functions as well as value level functions. But it’s like a price: all functions must be full functions! This is not very bad, but it means that these languages ​​are not really Turing at all (which will require the possibility of an infinite loop / recursion, but, nevertheless, ⟂ regarding a complete evaluation of the result).

---

¹ Things have changed a bit with the appearance of a kind of polymorphism, etc. .

² . Unlike, for example, C ++, which allows - albeit with a very terrible syntax - to perform functions of the type at the duck level using templates. This may be a pretty nice feature, but one of the consequences is that you often get completely unreadable error messages (with even less relevance to the real problem than the worst “GHC” “Possible fixes”) when you try to create a template using an argument of type outside the implicit domain.

Answer 2

The problem is that fst does not have the required type

 (forall x. x -> fx) 

Type fst -

 fst :: (a, b) -> a 

and a does not have the form f (a,b) . f there is a variable that must be created using a type constructor, something like [] , Maybe , Either Bool . f cannot stand behind any "type function", such as Λ (a,b) -> a , it must be a type constructor.

It works if we provide it with a function of the required type (sorry, stupid example):

 {-# LANGUAGE RankNTypes #-} mapAndZip3 :: (forall x. x -> fx) -> [a] -> [b] -> [c] -> [(fa, fb, fc)] mapAndZip3 f la lb lc = zipWith3 (\abc -> (fa, fb, fc)) la lb lc fst0 x = (True,x) main = do let x = mapAndZip3 (fst0) [(1 :: Int,"fruit"), (2,"martini")] [("chips","fish"),("rice","steak")] [(5 :: Int,"cake"),(4,"pudding")] print x 

since here fst0 is of type a -> ((,) Bool) a , which has the form x -> fx .