[Haskell] Type of y f = f . f

Ben Rudiak-Gould Benjamin.Rudiak-Gould at cl.cam.ac.uk
Mon Feb 28 13:03:08 EST 2005


Pedro Vasconcelos wrote:
 >Jim Apple <japple at freeshell.org> wrote:
 >>Is there a type we can give to
 >>
 >>y f = f . f
 >>
 >>y id
 >>y head
 >>y fst
 >>
 >>are all typeable?
 >
 >Using ghci:
 >
 >Prelude> let y f = f.f
 >Prelude> :t y
 >y :: forall c. (c -> c) -> c -> c
 >
 >So it admits principal type (a->a) -> a->a. From this you can see that
 >(y head) and (y fst) cannot be typed, whereas (y id) can.

I think the OP's point is that all three of his examples make sense, and 
the resulting functions would have Haskell types, yet there doesn't seem 
to be a Haskell type which permits all three uses of y. I can come up 
with types which permit any one of the three:

   y :: forall a. (a -> a) -> a -> a
   y :: forall a f. (forall x. f x -> x) -> f (f a) -> a
   y :: forall a b c f. (forall x y. f x y -> x) -> f (f a b) c -> a

but I can't find a type which permits more than one. It can probably be 
done with type classes.

-- Ben



More information about the Haskell mailing list