Write the function `selfApp` in book *Types and Programming Languages* in scala

Question

Is it possible to write this function is Scala? Or any other language?

Answer 1

I don't think it's possible in Scala without wrapping the function in an extra object. One way to do so would be:

type XtoX = {def apply[X](x: X): X }
def selfApp(f: XtoX): XtoX = f(f)

Now you can define an object with an apply method of the appropriate type like this:

object ID { def apply[X](x: X): X = x }

And call selfApp as selfApp(ID), which will simply return the object it's given. However this will not work:

def id[X](x: X): X = x

selfApp(id)

Nor can you use an anonymous function x => x. This is because when passing methods or anonymous functions around, there's represented as FunctionN object and the FunctionN traits have monomorphic (i.e. non-generic) apply functions. So you need to explicitly create an object with a generic apply method yourself.

---

In Haskell you can do it without any wrapping by using the RankNTypes extension like this:

{-# LANGUAGE RankNTypes #-}
selfApp :: (forall x. x -> x) -> (forall x. x -> x)
selfApp f = f f

---

And of course in dynamically typed languages you can just write the function without worrying about types at all. For example in Python:

def id(x): return x
def selfApp(f): return f(f)
print( selfApp(id)(42) ) # Just works - no extensions, no wrapping, no nothing