I was trying to simulate church numerals and primitive recursion in second rank polymorphism of Haskell. However, polymorphic types in Haskell can only be instantiated with monomorphic types.
We can even define primitive recursion, only that it does not have the desired type
primrec :: (N -> b -> b) -> b -> N -> b. Therefore, predecessor does not get the type
pred :: N a -> N a either.
Given a list, zip its first half with the reverse of its second half, in only “one and a half” traversals of the list.
A Haskell quine. That is, a program whose output is itself.