2

A long time ago, in a galaxy far far away, during a Scheme course, we were given this example of lambda games:

(define (foo x)
  (lambda (y) (x (x (x y)))))

Now, obviously ((foo 1+) 0) will print 3. (1+ is the standard Scheme increment operator) But the fun is that you can apply foo over itself, and then you can do fun stuff like:

    (((foo foo) 1+) 0)

which of course prints 27. And then there is the really funny:

(define a (foo foo))
(((a foo) 1+) 0)

I did this trick in CommonLisp, Clojure, Ruby, Python, Haskell, Erlang and Julia...

So the question arises, can you do it in Swift? I know you can do higher order functions, but can you create such functions which will be as 'reflexive' as in pure functional languages?

Tx!

Ambicatus
  • 23
  • 2
  • 1
    Swift has higher order functions, but I think the type system will be in the way of `foo(foo)(1+)(0)` working. – Sylwester Nov 25 '18 at 21:38
  • “`1+` is the standard Scheme increment operator.” There is no `1+` function defined in any Scheme standard I know of. – Alexis King Nov 25 '18 at 22:49
  • You are correct. Since both Guile and Elk have `1+` defined in them, I assumed it is standard function... – Ambicatus Nov 26 '18 at 06:12

1 Answers1

2

You can do this if you make foo generic:

func foo<T>(_ x: @escaping (T) -> T) -> (T) -> T {
    return { y in x(x(x(y))) }
}

func inc(x: Int) -> Int {
    return x + 1
}

foo(inc)(0)  // 3
foo(foo)(inc)(0)  // 27

Because foo is generic, this falls down when you try to define a.

This:

let a = foo(foo)

doesn't compile.

a itself needs to be generic and as @MartinR noted in the comments, in Swift only functions can be generic. So a will have to be defined as a function.

Here is my attempt:

func a<T>(_ x: @escaping (T) -> T) -> (T) -> T {
    return foo(foo)(x)
}

a(foo)(inc)(0)  // this runs for quite a long time ...
vacawama
  • 150,663
  • 30
  • 266
  • 294
  • What about the equivalent of `(define a (foo foo))` in Swift? `let a = foo(foo)` does not compile. – Martin R Nov 25 '18 at 21:51
  • Might be impossible since only functions can be generic, not closures or other expressions: https://stackoverflow.com/q/25545220/1187415, https://stackoverflow.com/q/25401584/1187415. – Martin R Nov 25 '18 at 21:58
  • Thanks a lot, @vacawama and others for the clear explanation! Notice first that if you do `foo(a)(inc)(0)` it runs for a _much_ shorter time for obvious reasons :) Also notice that if you compile this with an optimizer (`swiftc -O ...`) it will compute the value in compile time instead of runtime, and the resulting assembly will just icontains the actual result. It's quite illuminating to see run time vs compile time difference here Thanks again for all who answered! – Ambicatus Nov 26 '18 at 06:17