You say the Y combinator, as presented, could be done in Haskell, but it's got an infinite type, so it's a bit trickier to get working.