WTF Is a Y Combinator? (And Why Should You Care About Combinators)

1
# This is a combinator - it takes functions and returns a new function
2
def compose(f, g):
3
    return lambda x: f(g(x))
4
 
5
# So is this
6
def twice(f):
7
    return lambda x: f(f(x))
8
 
9
# And this
10
def flip(f):
11
    return lambda a, b: f(b, a)

1
# This won't work - the function has no name to call
2
factorial = lambda n: 1 if n <= 1 else n * factorial(n - 1)
3
# Error: factorial is not defined inside the lambda

1
# This version has issues with Python's eager evaluation
2
Y = lambda f: lambda x: f(Y(f))(x)

1
factorial_maker = lambda fact: lambda n: 1 if n <= 1 else n * fact(n - 1)
2
 
3
factorial = Y(factorial_maker)

1
# Z combinator - works in Python's eager evaluation
2
Y = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))

1
# Traditional memoization with mutable state
2
def memoize(f):
3
    cache = {}  # Mutable state!
4
    def wrapper(*args):
5
        if args not in cache:
6
            cache[args] = f(*args)
7
        return cache[args]
8
    return wrapper
9
 
10
# Y combinator approach - pure functional memoization
11
memo_Y = lambda f: (
12
    lambda x: f(lambda v: x(x)(v))
13
)(
14
    lambda x: f(lambda v: x(x)(v))
15
)
16
 
17
# Memoized fibonacci using Y combinator
18
fib_memo_maker = lambda memo_fib: lambda cache_func: lambda n: (
19
    cache_func(n, lambda: (
20
        n if n <= 1 else 
21
        memo_fib(cache_func)(n-1) + memo_fib(cache_func)(n-2)
22
    ))
23
)
24
 
25
# Pure functional cache implementation
26
make_cache = lambda: lambda n, compute: (
27
    compute()  # In practice, you'd use immutable data structures
28
)
29
 
30
memoized_fib = memo_Y(fib_memo_maker)(make_cache())

1
# Parser type: string -> (result, remaining_string) | None
2
Y = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))
3
 
4
# Basic parser combinators
5
def char(c):
6
    return lambda s: (c, s[1:]) if s and s[0] == c else None
7
 
8
def choice(*parsers):
9
    def parser(s):
10
        for p in parsers:
11
            result = p(s)
12
            if result: return result
13
        return None
14
    return parser
15
 
16
def sequence(*parsers):
17
    def parser(s):
18
        results, remaining = [], s
19
        for p in parsers:
20
            result = p(remaining)
21
            if not result: return None
22
            value, remaining = result
23
            results.append(value)
24
        return (results, remaining)
25
    return parser
26
 
27
def many(parser):
28
    # Here's where Y combinator shines - recursive parser without names!
29
    many_maker = lambda rec: lambda s: (
30
        lambda result: (
31
            ([result[0]] + rec(result[1])[0], rec(result[1])[1]) 
32
            if result else ([], s)
33
        )
34
    )(parser(s))
35
    
36
    return Y(many_maker)
37
 
38
# Example: Parse nested parentheses
39
paren_parser_maker = lambda paren: choice(
40
    sequence(char('('), lambda s: paren(s), char(')')),
41
    lambda s: ('', s)  # Empty match
42
)
43
 
44
parse_parens = Y(paren_parser_maker)
45
 
46
# Test it
47
print(parse_parens("((()))"))  # (['(', ['(', ['(', '', ')'], ')'], ')'], '')
48
print(parse_parens("(()"))     # (['(', ['(', '', ')'], ')'], ')')

1
Y = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))
2
 
3
# Depth-first search using Y combinator
4
dfs_maker = lambda dfs: lambda graph, start, visited=None: (
5
    visited or {start} if visited is None else visited
6
) if start in (visited or {start}) else (
7
    lambda new_visited: {start} | new_visited
8
)(
9
    set().union(*[
10
        dfs(graph, neighbor, (visited or set()) | {start})
11
        for neighbor in graph.get(start, [])
12
    ])
13
)
14
 
15
# Example graph
16
graph = {
17
    'A': ['B', 'C'],
18
    'B': ['D', 'E'],
19
    'C': ['F'],
20
    'D': [],
21
    'E': ['F'],
22
    'F': []
23
}
24
 
25
dfs = Y(dfs_maker)
26
print(dfs(graph, 'A'))  # {'A', 'B', 'C', 'D', 'E', 'F'}
27
 
28
# Topological sort using Y combinator
29
topo_sort_maker = lambda topo: lambda graph, visited, stack: (
30
    lambda node: (
31
        (visited, stack) if node in visited else
32
        lambda new_visited, new_stack: (
33
            new_visited, [node] + new_stack
34
        )(*reduce(
35
            lambda acc, neighbor: topo(graph, *acc),
36
            graph.get(node, []),
37
            (visited | {node}, stack)
38
        ))
39
    )
40
)
41
 
42
# Helper to run topological sort on all nodes
43
run_topo_sort = lambda graph: (
44
    lambda topo: reduce(
45
        lambda acc, node: topo(graph, *acc)(node),
46
        graph.keys(),
47
        (set(), [])
48
    )[1]
49
)(Y(topo_sort_maker))

1
# Infinite list of natural numbers using Y combinator
2
naturals_maker = lambda nats: lambda start: (
3
    start, lambda: nats(start + 1)
4
)
5
 
6
# Helper to take n items from infinite list
7
take = lambda n: lambda inf_list: (
8
    [] if n <= 0 else
9
    [inf_list[0]] + take(n-1)(inf_list[1]())
10
)
11
 
12
naturals = Y(naturals_maker)(0)
13
print(take(10)(naturals))  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

1
# Function decorators are combinators
2
def memoize(f):
3
    cache = {}
4
    def wrapper(*args):
5
        if args not in cache:
6
            cache[args] = f(*args)
7
        return cache[args]
8
    return wrapper
9
 
10
# functools provides combinators
11
from functools import reduce, partial
12
 
13
# Pipeline pattern using reduce
14
def pipeline(*functions):
15
    return reduce(lambda f, g: lambda x: g(f(x)), functions, lambda x: x)
16
 
17
# Partial application
18
add = lambda x, y: x + y
19
add_five = partial(add, 5)

1
# Reducer combinator pattern
2
def combine_reducers(**reducers):
3
    def combined(state, action):
4
        return {
5
            key: reducer(state.get(key), action)
6
            for key, reducer in reducers.items()
7
        }
8
    return combined
9
 
10
# Middleware composition
11
def compose_middleware(*middlewares):
12
    def composed(next_handler):
13
        for middleware in reversed(middlewares):
14
            next_handler = middleware(next_handler)
15
        return next_handler
16
    return composed

1
# This won't work in Python due to eager evaluation
2
Y_pure = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))

1
Z = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))

1
# Theta combinator
2
Θ = lambda f: (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y)))

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

1
# Identity: returns its argument unchanged
2
I = lambda x: x
3
 
4
# Constant: returns a function that always returns the first argument
5
K = lambda x: lambda y: x
6
 
7
# Compose: function composition
8
B = lambda f: lambda g: lambda x: f(g(x))
9
 
10
# Flip: reverses argument order
11
C = lambda f: lambda x: lambda y: f(y)(x)
12
 
13
# Substitution combinator
14
S = lambda f: lambda g: lambda x: f(x)(g(x))

1
Y = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))
2
 
3
# Sum of list
4
sum_maker = lambda sum_func: lambda lst: 0 if not lst else lst[0] + sum_func(lst[1:])
5
sum_list = Y(sum_maker)
6
 
7
# Flatten nested lists
8
flatten_maker = lambda flatten: lambda lst: sum(
9
    (flatten(item) if isinstance(item, list) else [item] for item in lst), []
10
)
11
flatten = Y(flatten_maker)
12
 
13
# Map function
14
map_maker = lambda map_func: lambda f, lst: [] if not lst else [f(lst[0])] + map_func(f, lst[1:])
15
recursive_map = Y(map_maker)