Abstract

We restate three well-known machine-learning methods — decision trees, k-means clustering, and gradient boosting — as pipelines of higher-order functions, decomposing each into atomic steps and mapping those steps onto the standard functional combinators map, reduce, and filter. These combinators are the ordinary vocabulary of functional programming [1, 2, 3], and expressing an algorithm in terms of them makes its structure and reusable parts explicit without changing what it computes. The payoff is compositional clarity: classical methods are more interpretable and less compute-hungry than large neural models [4, 5], and a clean compositional description of them makes their reusable parts recombinable.

1. Introduction

Large transformer models [4, 5] dominate current practice, but classical machine-learning methods remain valued for interpretability and modest compute requirements. Describing such methods in a uniform compositional vocabulary makes their reusable parts explicit and recombinable. This article does exactly that for three methods, using higher-order functions as the common vocabulary. Rewriting a decision tree's split step as a map does not change what the tree computes — it makes its structure explicit, which is the contribution: a re-description that surfaces the composable shape of each algorithm.

2. Related Work

Functional combinators. map, reduce/fold, and filter are the canonical higher-order functions of functional programming; the case that expressing computation through them aids modularity and reasoning is classical [1, 2], as are the underlying language concepts [3]. The transformations below reuse these combinators rather than inventing new ones.

The methods themselves. Decision trees, k-means, and gradient boosting are textbook algorithms predating this work by decades; this article changes nothing about what they compute. The positioning — that lighter, more interpretable methods complement heavy neural models [4, 5] — is the motivation for describing them compositionally.

3. Three Re-descriptions

Each method is decomposed into atomic steps, then those steps are named in higher-order-function terms. The accompanying code is schematic — it communicates the decomposition.

3.1 Decision tree

[ILLUSTRATIVE] schematic:

# Schematic — communicates the decomposition.
def split_scores(data, criterion): # map: score each candidate split
 return map(criterion, candidate_splits(data))

def build(data, depth=0):
 if stop(data, depth):
 return leaf(data)
 best = max(split_scores(data, criterion)) # reduce: pick best split
 left = filter(lambda x: x < best.threshold, data) # filter: partition
 right = filter(lambda x: x >= best.threshold, data)
 return node(best, build(left, depth+1), build(right, depth+1))

3.2 k-means clustering

[ILLUSTRATIVE] schematic:

# Schematic.
def assign(points, centroids): # map: nearest centroid per point
 return map(lambda p: argmin_dist(p, centroids), points)

def update(points, labels, k): # reduce: mean of each cluster
 return [mean(points_where(points, labels, i)) for i in range(k)]

3.3 Gradient boosting

[ILLUSTRATIVE] schematic:

# Schematic.
def fit(X, y, n):
 residual, learners = y, []
 for _ in range(n):
 h = fit_weak_learner(X, residual) # one boosting step
 learners.append(h)
 residual = residual - h(X) # update residuals
 return learners

def predict(X, learners): # reduce: sum learner outputs
 return sum(h(X) for h in learners)

These sketches show the shape of each algorithm in HOF terms. They omit framework-specific detail by design: the composition is the subject, and the same map/reduce/filter structure holds across whatever framework realizes it.

Evidence & Scope

This is a re-description in a uniform vocabulary. Expressing decision trees, k-means, and gradient boosting through map/reduce/filter clarifies their structure and reuse while leaving what they compute unchanged — accuracy, complexity, and scalability are properties of the underlying algorithms [1, 2, 3]. The code blocks are [ILLUSTRATIVE] schematics that communicate each decomposition. The benefits argued here — interpretability and modest compute cost relative to large transformer models [4, 5] — belong to the classical methods, and the compositional description makes them legible.

References

  1. John Backus (1978). Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. Communications of the ACM. [1977 ACM Turing Award Lecture]
  2. John Hughes (1989). Why Functional Programming Matters. The Computer Journal.
  3. Christopher Strachey (2000). Fundamental Concepts in Programming Languages. Higher-Order and Symbolic Computation. [Reprint of 1967 lecture notes]
  4. Ashish Vaswani et al. (2017). Attention Is All You Need. Advances in Neural Information Processing Systems (NeurIPS). arXiv:1706.03762.
  5. Tom B. Brown et al. (2020). Language Models are Few-Shot Learners. Advances in Neural Information Processing Systems (NeurIPS). arXiv:2005.14165. [GPT-3]