I have no name, and I must recurse

Have you ever started on some creative work, and given yourself an arbitrary restriction within which to do it? Like making some pixel art, but you will only use black or white pixels. I think it's quite a fun way to drive the creative and problem solving juices, to test the limits of the restriction and learn new techniques.

In my case, I was solving some beginner programming puzzles, but the online judge system would only accept submissions in a handful of languages: C, C++, Java, Pascal, and Python. I didn't particularly like any of these, since I was mostly interested in playing around with functional concepts, but I concluded I could probably use Python's flexibility to make something similar.

So I started writing. The aim was to replace double-quote pairs ("") with matching pairs of TeX-style quotes (``, '') in a text. But then I stopped and looked at what I wrote and had a thought: would Python let me squish this into a single statement? I knew I could do funky things with list comprehensions, but I wasn't sure whether I could cram an entire program into a single line.

Turns out, after a bunch of research, that it's totally doable! It takes some thinking in terms of lists instead of loops, and some functools.reduce usage, but it works! This made me really excited; could I do this for every puzzle?

Next up: given a list of ranges, find the length of the longest collatz sequence starting from any number in each range. Sounds doable! So I went to work. Iterate on the lines of input, split on space, get a range from the lowest to highest (conditionals like this require a trick: {True: range(i, j), False: range(j, i)}[i < j]), and finally calculate the length of the collatz sequence.

The thing about the collatz sequence is it isn't a fixed length loop. In fact, like the prime numbers or the digits of pi, you can't tell where the sequence will go next. Whether it will always end is an open question to this day! So I couldn't just make a list comprehension out of it. I figured I could make a function that calculates it recursively, so I wrote a function, and found myself with a problem: I couldn't recursively call a function if I didn't have a name to call, and I couldn't give the function a name since my massive construction had to fit in a single statement.

I went looking around the internet, asked some friends, and after sifting through a bunch of "No you can't do this" answers I found a particularly funny looking expression that claimed to be the solution. It looks a bit like this: (lambda f, n: f(f, n))(lambda f, n: 1 if n == 1 else n * f(f, n-1), 5)

That is an anonymous recursive lambda which calculates 5 factorial. Or so I claim. What does it really do? I spent a few hours staring at the solution until it finally clicked, as it often does. Let me break it down.

We want a recursive factorial function. Easy enough:

def factorial(n):
  if n == 1:
    return 1
  else:
    return n * factorial(n-1)

Now we want it not to rely on its name. How? Maybe it's given itself as a parameter, like a callback:

def factorial(fact, n):
  if n == 1:
    return 1
  else:
    return n * fact(fact, n-1)

Fair enough, now we just need to call it with itself every time. We could make another function for this:

def setup(f, n):
  return f(f, n)

So now we can run setup(factorial, 5) to run our function. Packaging them all up in lambdas gets us

factorial = lambda f, n: 1 if n == 1 else n*f(f, n-1)
setup = lambda f, n: f(f, n)

And thus setup(factorial, 5) becomes (lambda f, n: f(f, n))(lambda f, n: 1 if n == 1 else n*f(f, n-1), 5) VoilĂ !

But what if I want to pass an anonymous recursive function to another function, without calling it immediately? Ah, there's a way for that too:

def setup(f):
  def engage(n):
    return f(f, n)
  return engage

Now setup only takes a function and returns another one, which only takes the parameter, which then kickstarts the recursion. Packing it up:

setup = lambda f: lambda n: f(f, n)

And we can now make a completely self-contained recursive factorial function!

factorial = (lambda f: lambda n: f(f, n))(lambda f, n: 1 if n == 1 else n*f(f, n-1))
factorial(5)

What about more parameters? No problem!

def setup(f, fixed, parameters):
  def engage(variable, ones):
    return f(f, fixed, parameters, variable, ones)
  return engage

I'll leave putting this together to you all.

So, I made such a function that calculated the length of the collatz sequence, given the starting number, and my single-statement program was complete! Sadly, it's extremely slow, so it wasn't very fit for the puzzle, but it was a great learning experience nonetheless.