How to write recursive lambdas in Python

python_recursive_lambdas.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python distinguishes between to kinds of functions: procedures which have their roots from the procedural programming paradigm and lambdas, derived from the lambda calculus and based on the functional programming paradigm.\n",
    "\n",
    "A procedure is declared with the `def` keyword, followed by its name. Assigning a name to procedures is necessary. There is no way to define anonymous procedures like in some other programming languages, e.g. JavaScript.\n",
    "\n",
    "Compared with that a lambda does not have to have a name. It can be either defined at the position of a parameter for a function call or it can be called directly after its definition by wrapping a lambda into an closure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "(lambda x : print(x))(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let't take a look at a simple example for a recursive function: A recursive counter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "def counter(start : int, stop : int):\n",
    "    if start <= stop:\n",
    "        print(start)\n",
    "        counter(start + 1, stop)\n",
    "\n",
    "counter(1, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can we turn this function into a function which does not know its own Name? This should be possible:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "def nameless_counter(function : callable, start : int, stop : int):\n",
    "    if start <= stop:\n",
    "        print(start)\n",
    "        function(function, start + 1, stop)\n",
    "\n",
    "nameless_counter(nameless_counter, 1, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This doesn't look beautiful but it has one advantage: Within the definition of the `nameless_counter` the counter does not have to know its own name but can still call itself recursively. Therefore the counter can be transformed into a lambda:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(None,\n",
       " (None, (None, (None, (None, (None, (None, (None, (None, (None, 0))))))))))"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nameless_counter = lambda function, start, stop : (print(start), function(function, start + 1, stop)) if start <= stop else (0)\n",
    "\n",
    "nameless_counter(nameless_counter, 1, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The additional output is a side effect that we are going to ignore here because we want to use the `print()` function to prove the lambda and afterwards make a recursive call. Regular lambdas are not made to do more than a single task. The tuple definition allows to do both but the output looks ugly.\n",
    "\n",
    "Calling the `nameless_counter` still has some disadvantages: We need to type the name twice. Let's turn this into a function call so the name needs to be typed only once:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "nameless_counter = lambda function, start, stop : (print(start), function(function, start + 1, stop)) if start <= stop else (0)\n",
    "\n",
    "def init(function : callable, start : int, stop : int):\n",
    "    function(function, start, stop)\n",
    "\n",
    "init(nameless_counter, 1, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Perfect, now the name of the `nameless_counter` is not necessary anymore because the lambda definition can be fed directly into the `init` function call as a parameter:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "def init(function : callable, start : int, stop : int):\n",
    "    function(function, start, stop)\n",
    "\n",
    "init(lambda function, start, stop : (print(start), function(function, start + 1, stop)) if start <= stop else (0), 1, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's turn the init function into a lambda:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(None,\n",
       " (None, (None, (None, (None, (None, (None, (None, (None, (None, 0))))))))))"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "init = lambda function, start, stop: function(function, start, stop)\n",
    "\n",
    "init(lambda function, start, stop : (print(start), function(function, start + 1, stop)) if start <= stop else (0), 1, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And combine them by wrapping the `init` lambda into a closure and call it directly without having to specify a name:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(None,\n",
       " (None, (None, (None, (None, (None, (None, (None, (None, (None, 0))))))))))"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(lambda function, start, stop: function(function, start, stop))(lambda function, start, stop : (print(start), function(function, start + 1, stop)) if start <= stop else (0), 1, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're done! It's a lambda which performs a recursive call to itself without having a name for any of these lambdas. It even handles the return value without a problem."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}