A Pythonic FP adventure
Designing a horrible implementation for LCM

Let's write a naive function to find the largest common multiple of two integers in Python. As usual in Python, there is only one obvious solution.

We will test it with the following check:

return lcm(5, 12) == 60

Here's the naive function:

def lcm(a: int, b: int) -> int:
    m = 1
    n = 1
    while abs(m*a) != abs(n*b):
        if abs(m*a) < abs(n*b):
            m += 1
        else:
            n += 1
    return m*a
return lcm(5, 12) == 60

True

Now we should either try to make the function more readable to increase maintainability, or if it is causing performance issues, optimize it.

Allegedly Python supports the functional programming paradigm. Functional programs are readable and maintainable so let's try that out.

First we want to turn the loop into a recursive call. Because we do not want to change the type of the function, we need to introduce an inner function.

def lcm(a: int, b: int) -> int:
    def inner(m, n):
        if abs(m*a) < abs(n*b):
            return inner(m + 1, n)
        elif abs(n*b) < abs(m*a):
            return inner(m, n + 1)
        else:
            return m*a
    return inner(1, 1)
return lcm(5, 12) == 60

True

Now our function technically adheres to the functional paradigm. But we can do better! The return statements seem quite redundant, right?

def lcm(a: int, b: int) -> int:
    def inner(m, n):
        return (inner(m + 1, n) if abs(m*a) < abs(n*b) else
                inner(m, n + 1) if abs(n*b) < abs(m*a) else
                m*a)
    return inner(1, 1)
return lcm(5, 12) == 60

True

I can only guess why if-expressions in Python look like something out of Perl.

Let's change the inner function to a lambda term as that removes one return statement.

def lcm(a: int, b: int) -> int:
    inner = lambda m: lambda n: (
        inner(m + 1)(n) if abs(m*a) < abs(n*b) else
        inner(m)(n + 1) if abs(n*b) < abs(m*a) else
        m*a
    )
    return inner(1)(1)
return lcm(5, 12) == 60

True

In the process I also curried the inner function to make it closer to a true lambda term. Though it is not yet a true lambda term as its definition is self-referential.

Fixing this allows us also to remove the last return statement by turning the whole function into a lambda expression.

The fix seems easy at first – just use fixed point recursion. The problem is that Haskell Curry's classic Y-combinator, when implemented directly in Python, gives rise to a stack overflow once any function is passed to it. Python gets stuck evaluating the Y-combinator as the argument is evaluated eagerly:

All argument expressions are evaluated before the call is attempted. – https://docs.python.org/3/reference/expressions.html#calls

Here's an example for the factorial function producing stack overflow even before the number to calculate the factorial for is specified:

Y = (lambda f: (lambda x: f(x(x)))
               (lambda x: f(x(x))))
Y(lambda factorial:
  lambda n: 1 if n == 1 else n*factorial(n - 1))

Luckily Python can be tricked into not evaluating the argument as eagerly with a different version of the Y-combinator. The main difference seems to be that inside the combinator, f is not passed the arguments directly but rather as a lambda form, which allows for more lazy evaluation. Let's call this new combinator fix. Here's the definition I found on several internet forums:

fix = lambda f: (
    (lambda x: f(lambda v: x(x)(v)))
    (lambda x: f(lambda v: x(x)(v)))
)

I couldn't find motivation for the given combinator, so here's proof it works as expected:

fix(g)

= (lambda f: (
    (lambda x: f(lambda v: x(x)(v))) # By rewriting
    (lambda x: f(lambda v: x(x)(v))) # definition above
))(g)

= (lambda x: g(lambda v: x(x)(v)))   # By invoking the function
  (lambda x: g(lambda v: x(x)(v)))   # application (lambda f: ...)(g)

= g(lambda v:
    (lambda x: g(lambda v: x(x)(v))) # By rewriting x in 'x(x)' with
    (lambda x: g(lambda v: x(x)(v))) # the argument 'lambda x: ...'.
    (v))                             # This is a function application.

= g((lambda v: fix(g))(v))           # By rewriting the equality
                                     # fix(g) = (lambda x: ...)(lambda x: ...)
                                     # proven in the first two steps

= g(fix(g))                          # By function application
                                     # (lambda v: ...)(v)

fix(g) = g(fix(g)) means that the return value of fix(g) is such a value that calling g repeatedly on it doesn't change the result, ie. it is a fixed point of g.

Let's try it out with the factorial function we saw failing earlier.

fix = lambda f: (
    (lambda x: f(lambda v: x(x)(v)))
    (lambda x: f(lambda v: x(x)(v)))
)

return fix(lambda factorial:
           lambda n: 1 if n == 1 else n*factorial(n - 1))(5)

It works fine. Now we can just use the fixed point operator to define the recursive inner function.

fix = lambda f: (
    (lambda x: f(lambda v: x(x)(v)))
    (lambda x: f(lambda v: x(x)(v)))
)

lcm = lambda a, b: (
    fix(lambda inner:
        lambda m: lambda n: (
            inner(m + 1)(n) if m*a < n*b else
            inner(m)(n + 1) if n*b < m*a else
            m*a
        )
    )(1)(1)
)

return lcm(5, 12) == 60

True

Expanding fix to make lcm a pure lambda term gives

lcm = lambda a, b: (
    (lambda f: (
        (lambda x: f(lambda v: x(x)(v)))
        (lambda x: f(lambda v: x(x)(v)))
    ))
    (lambda inner:
        lambda m: lambda n: (
            inner(m + 1)(n) if m*a < n*b else
            inner(m)(n + 1) if n*b < m*a else
            m*a
        )
    )(1)(1)
)

return lcm(5, 12) == 60

True

A Pythonic FP adventure Designing a horrible implementation for LCM

A Pythonic FP adventure
Designing a horrible implementation for LCM