It’s time for my first code
kata,
and on Colin’s suggestion, I’m starting with a classic: prime
factorization.
The problem description is simple: write a function that takes an
integer n and returns a list of its prime factors in ascending order.
That leaves lots of room for creativity, and in my few months at 8th
Light, I’ve seen several interesting solutions, including Objective-C
and
Erlang.
I’ve been meaning to learn Clojure’s core.logic library for a while,
so I decided to come up with a logic programming solution.
If you haven’t yet checked out core.logic, there are a growing
number of resources on the web. To get up to speed, I worked through David Nolen’s logic tutorial, the Magical Island of Kanren, the
core.logic
Primer,
and a few chapters of The Reasoned
Schemer.
Hopefully, following along with my test cases will explain the subset
of logic functions in my solution.
On to the tests! The declarative aspect of logic programming feels
well-suited to a mathy problem like this. Instead of describing how to
factorize, I’ll write a few definitions and let the logic engine
handle the rest. The strategy I have in mind is the same simple one I learned in
8th grade algebra: start with a composite integer, and decompose it
into a factor tree whose leaves are prime factors.
To start, I’ll define “factor pairs”: a vector of two integers that
multiply to another. So, [2 3] is a factor pair of 6, [1 23] a
factor pair of 23. Here’s the most general test I came up with:
core_spec.clj
123456789
(ns prime-factors.core-spec(:require[speclj.core:refer:all][prime-factors.core:refer:all]))(defmacro they[&args]`(it~@args))(describe"Factor pairs of n"(they"contain two elements"(should='([_0_1])(factor-pairs81))))
There’s a lot of syntax right off the bat, but this test isn’t as
confusing as it might look. So far, I’ve found it easiest to understand logic programming as
describing a set of constraints on a solution. This test describes the
first constraint: factor pairs are vectors of two elements.
Here, _0 and _1 represent reified, unbound logic variables: symbolic
representations of logic variables that can take on any value. (The
numbers at the end indicate that they’re two different variables: _0
and _1 can take on different values). So this
test simply describes the most general constraint: the factor-pairs
function should take something as an argument and return a list of
vectors of two things–any two things!.
The run* function is the, uh, core of core.logic, used to set up
problems for the logic engine to solve. It returns a list of all the
solutions that match the constraints defined inside. The fresh form
inside of run* is
analogous to let: a way to declare local logic variables. The first
two lines say “Find all
the solutions where pair, factor1, and factor2 meet these
constraints,” and the third describes the only constraint: “A pair is a
vector of two elements, factor1 and factor2”.
Note that I’m ignoring the number argument! At this point
(factor-pairs 81), (factor-pairs 72), and (factor-pairs 23) all
return the same result. For now, calling this function factor-pairs
is a little misleading, since it returns the equivalent of all
possible pairs of two things. But now that the tests pass, we can add
another constraint:
core_spec.clj
1234567891011121314151617181920
(ns prime-factors.core-spec(:require[speclj.core:refer:all][prime-factors.core:refer:all]))(defmacro they[&args]`(it~@args))(defn should-all[predicatecollection](should(every? predicatecollection)))(defn in-interval?[lowhigh](fn [pair](every? #(and (>= %low)(<= %high))pair)))(defn two-elements?[pair](= 2(count pair)))(describe"Factor pairs of n"(they"contain two elements"(should-alltwo-elements?(factor-pairs81)))(they"are defined between 2 and n"(should-all(in-interval?281)(factor-pairs81))))
Here, I’ll describe the next constraint: factor pairs should only be
defined between 2 and n. (Yes, a pair like [1 23] is technically a
pair of factors, but it’s not very useful for my prime factorization purposes).
I may be open to a little TDD legal trouble
with this test update, but I’ve added a couple helper functions to
keep the tests as declarative as possible. Should-all asserts that a
predicate matches for every element in a collection. In-interval?
tests whether a pair is in the range low to high, inclusive.
Hopefully, Two-elements? explains itself. Since factor-pairs will
now return a list with many elements, I’ve generalized the original test.
It only takes one line to add the extra constraint:
The new line declares that factor1 and factor2 must both be in the
finite interval 2-number. Factor-pairs is still something of a
misnomer: it now returns the Cartesian product of all numbers
2-number. But it’s a step closer. I’ll add one more constraint:
core_spec.clj
12345678910111213141516171819202122232425
(ns prime-factors.core-spec(:require[speclj.core:refer:all][prime-factors.core:refer:all]))(defmacro they[&args]`(it~@args))(defn should-all[predicatecollection](should(every? predicatecollection)))(defn in-interval?[lowhigh](fn [pair](every? #(and (>= %low)(<= %high))pair)))(defn two-elements?[pair](= 2(count pair)))(defn multiply-to?[n](fn [[factor1factor2]](= n(* factor1factor2))))(describe"Factor pairs of n"(they"contain two elements"(should-alltwo-elements?(factor-pairs81)))(they"are defined between 2 and n"(should-all(in-interval?281)(factor-pairs81)))(they"equal n when multiplied"(should-all(multiply-to?81)(factor-pairs81))))
Factor pairs contain two elements between 2 and n that equal n when
multiplied. That’s a complete definition of a factor pair, and adding
the third constraint completes the function:
Here, eq converts an arithmetic expression into a constraint, as
long as the logic variables are defined over a finite domain. So the
final constraint simply says number must equal factor1 times
factor2. If you’re not convinced by the tests, try it in a REPL:
There are some properties here that I’ll use to my advantage. First,
by default, factor pairs are ordered by the first factor, ascending.
Second, I’ve already created an implicit definition of primes: numbers
that return an empty list of factor pairs. I’ll add it as a test for
clarity:
core_spec.clj
1234567891011121314151617181920212223242526272829
(ns prime-factors.core-spec(:require[speclj.core:refer:all][prime-factors.core:refer:all]))(defmacro they[&args]`(it~@args))(defn should-all[predicatecollection](should(every? predicatecollection)))(defn in-interval?[lowhigh](fn [pair](every? #(and (>= %low)(<= %high))pair)))(defn two-elements?[pair](= 2(count pair)))(defn multiply-to?[n](fn [[factor1factor2]](= n(* factor1factor2))))(describe"Factor pairs of n"(they"contain two elements"(should-alltwo-elements?(factor-pairs81)))(they"are defined between 2 and n"(should-all(in-interval?281)(factor-pairs81)))(they"equal n when multiplied"(should-all(multiply-to?81)(factor-pairs81))))(describe"Prime numbers"(they"have no factor pairs"(should='()(factor-pairs23))))
Now I’ll move on to decomposition. If you’ve watched a prime factors
kata before, you’ve probably seen a few standard tests: start by
testing 1, then 2, then 3, and then composites. Here’s where something
similar comes in:
(ns prime-factors.core-spec(:require[speclj.core:refer:all][prime-factors.core:refer:all]))(defmacro they[&args]`(it~@args))(defn should-all[predicatecollection](should(every? predicatecollection)))(defn in-interval?[lowhigh](fn [pair](every? #(and (>= %low)(<= %high))pair)))(defn two-elements?[pair](= 2(count pair)))(defn multiply-to?[n](fn [[factor1factor2]](= n(* factor1factor2))))(describe"Factor pairs of n"(they"contain two elements"(should-alltwo-elements?(factor-pairs81)))(they"are defined between 2 and n"(should-all(in-interval?281)(factor-pairs81)))(they"equal n when multiplied"(should-all(multiply-to?81)(factor-pairs81))))(describe"Prime numbers"(they"have no factor pairs"(should='()(factor-pairs23))))(describe"Decomposition"(it"decomposes 1 into itself"(should='(1)(decompose1))))
(ns prime-factors.core-spec(:require[speclj.core:refer:all][prime-factors.core:refer:all]))(defmacro they[&args]`(it~@args))(defn should-all[predicatecollection](should(every? predicatecollection)))(defn in-interval?[lowhigh](fn [pair](every? #(and (>= %low)(<= %high))pair)))(defn two-elements?[pair](= 2(count pair)))(defn multiply-to?[n](fn [[factor1factor2]](= n(* factor1factor2))))(describe"Factor pairs of n"(they"contain two elements"(should-alltwo-elements?(factor-pairs81)))(they"are defined between 2 and n"(should-all(in-interval?281)(factor-pairs81)))(they"equal n when multiplied"(should-all(multiply-to?81)(factor-pairs81))))(describe"Prime numbers"(they"have no factor pairs"(should='()(factor-pairs23))))(describe"Decomposition"(it"decomposes 1 into itself"(should='(1)(decompose1)))(it"decomposes primes into themselves"(should='(2)(decompose2))(should='(3)(decompose3))(should='(17)(decompose17))(should='(23)(decompose23)))
I’ll get back to passing with a small tweak. Instead of returning
'(1), decompose should check if a number has any
factor pairs. If not, return the number.
(ns prime-factors.core-spec(:require[speclj.core:refer:all][prime-factors.core:refer:all]))(defmacro they[&args]`(it~@args))(defn should-all[predicatecollection](should(every? predicatecollection)))(defn in-interval?[lowhigh](fn [pair](every? #(and (>= %low)(<= %high))pair)))(defn two-elements?[pair](= 2(count pair)))(defn multiply-to?[n](fn [[factor1factor2]](= n(* factor1factor2))))(describe"Factor pairs of n"(they"contain two elements"(should-alltwo-elements?(factor-pairs81)))(they"are defined between 2 and n"(should-all(in-interval?281)(factor-pairs81)))(they"equal n when multiplied"(should-all(multiply-to?81)(factor-pairs81))))(describe"Prime numbers"(they"have no factor pairs"(should='()(factor-pairs23))))(describe"Decomposition"(it"decomposes 1 into itself"(should='(1)(decompose1)))(it"decomposes primes into themselves"(should='(2)(decompose2))(should='(3)(decompose3))(should='(17)(decompose17))(should='(23)(decompose23)))(it"decomposes 2 * a prime into 2 and itself"(should='(22)(decompose4))))
Decompose already includes the base case at the bottom of of the
prime factor tree. If I feed it a number that’s not prime, it should
decompose its factors until it runs into a prime. Concatenating the
results should return a nice list of prime factors:
(ns prime-factors.core-spec(:require[speclj.core:refer:all][prime-factors.core:refer:all]))(defmacro they[&args]`(it~@args))(defn should-all[predicatecollection](should(every? predicatecollection)))(defn in-interval?[lowhigh](fn [pair](every? #(and (>= %low)(<= %high))pair)))(defn two-elements?[pair](= 2(count pair)))(defn multiply-to?[n](fn [[factor1factor2]](= n(* factor1factor2))))(describe"Factor pairs of n"(they"contain two elements"(should-alltwo-elements?(factor-pairs81)))(they"are defined between 2 and n"(should-all(in-interval?281)(factor-pairs81)))(they"equal n when multiplied"(should-all(multiply-to?81)(factor-pairs81))))(describe"Prime numbers"(they"have no factor pairs"(should='()(factor-pairs23))))(describe"Decomposition"(it"decomposes 1 into itself"(should='(1)(decompose1)))(it"decomposes primes into themselves"(should='(2)(decompose2))(should='(3)(decompose3))(should='(17)(decompose17))(should='(23)(decompose23)))(it"decomposes 2 * a prime into 2 and itself"(should='(22)(decompose4)))(it"decomposes a composite into its prime factorization"(should='(222)(decompose8))(should='(235)(decompose30))(should='(21111)(decompose242))(should='(251123)(decompose(* 235211)))))
This isn’t the fastest way to find prime factors, but it’s no worse
than the typical trial division solution to the prime factors kata.
Using core.logic to declare definitions and constraints on the
solution feels uniquely concise, expressive, and clear, and the
exercise helped me get a more concrete handle on logic programming.
You can find the code from this post (and a few earlier iterations) as
a Gist here.