logoalt Hacker News

momentoftoptoday at 5:39 PM0 repliesview on HN

Most of them have simple types and are easy to define in ML or Haskell.

   I : a -> a
   I x = x

   K : a -> b -> a
   K x y = x

   W : (a -> a -> b) -> a -> b
   W f x = f x x

   C : (a -> b -> c) -> b -> a -> c
   C f x y = f y x

   B : (a -> b) -> (c -> a) -> c -> b
   B f g x = f (g x)

   Q : (a -> b) -> (b -> c) -> a -> c
   Q f g x = g (f x)
There are, however, combinators that do self-application (crucially used in the definition of the Y combinator) and these do not have simple types.