When playing with a new bit of language, it can be helpful to restrict the problem space to an old, well understood algorithm. For me at least, learning one thing at a time is easier! For this post, Itâ€™ll be prime sieves, and Iâ€™ll be exploring clojure reducers.
A quick recap, the sieve of eratosthenes is a not-maximally-non-optimal way of finding primes. Itâ€™s usually expressed as follows:
In clojure, something like:
Which is fine, but Iâ€™d like it lazy so I only pay for what I use, and I can use as much as Iâ€™m willing to pay for. Letâ€™s look at lazy sequences. Luckily for us, there is an example of exactly this on the lazy-seq documentation, which we slightly modify like so:
So now we have a nice generic source of primes that grows only as we take more. But is there another way?
A few months ago Rich Hickey introduced reducers. By turning the concept of ‘reducing’ inside out the new framework allows a parallel reduce (fold) in some circumstances. Which doesn’t apply here. But let’s see if we can build a different form of sieve using the new framework. First a quick overview (cribbing from the original blog post):
Collections are now ‘reducible’, in that they implement a reduce protocol. Filter, map, etc are implemented as functions that can be applied by a reducible to itself to return another reducible, but lazily, and possibly in parallel. So in the example below we have a reducible (a vector), that maps inc to itself to return a reducible that is then wrapped with a filter on even? which returns a further reducible, that reduce then collects with +.
We’ll be referring to r here and there – just remember it’s the clojure.core.reducers namespace
These are composable, so we can build ‘recipes’.
into uses reduce internally, so we can use it to build collections instead of reducing:
So here’s the core of ‘reducer’, which “Given a reducible collection, and a transformation function xf, returns a reducible collection, where any supplied reducing fn will be transformed by xf. xf is a function of reducing fn to reducing fn.”
And we can then use that to implement mapping as so:
Fine. So what about sieves? One thought is we could build up a list of composed filters, built as new primes are found (see the lazy-seq example above). But there’s no obvious place to do the building, as applying the reducing functions is left to the reducible implementation. Another possibility is to introduce a new type of reducing function, the ‘progressive-filter’, which keeps track of past finds and can filter against them.
And we then reduce with a filtering function that is a function of the current candidate and one of the list of found primes (see the #(f input %) bit above)
It’s nicely lazy, so we can use iterate to generate integers, and take only a few (r/take, as it’s operating on a reducer):
You get the idea.
I’ve often found myself at a loss for blog post topics, so rather than write one myself I decided to let a computer do the heavy lifting!
Markov chains offer a neat trick for generating surrealist blog oeuvres. They work by figuring out the probability of one word appearing after another, given a suitable corpus of input material.
DSL based templating sucks! This looks a very short beep-like sound card. Let paragraphs rely on a sense of data. Roy recently released my mind: In practice of course, it grew features.
Our first local policy at LShift although weâ€™ve had a Meteor is necessary to distinguish this point though, we want to and hence wonâ€™t discuss. Empty is the dark ages trying to wind position when your job to generate input data API calls to understand this blog post. Hello, add our socket buffer, etc.
Iâ€™m glad I have addressed your submitter claims to work out what if we just the two commits! You especially love peer review. Perhaps itâ€™s about the motherboard. Success!
A couple years ago we presented a couple design sketches for a code coverage tool for clojure. More recently we spent some time researching whether existing code coverage tools would suffice for our requirements, and after finding out that java based code coverage tools either don’t work at all, or produce unhelpful output, we decided to finally write cloverage. You can find it on github: https://github.com/lshift/cloverage.
To try it out, add the lein-cloverage plugin to your user profile in ~/.lein/profiles.clj:
Then run `lein cloverage` in your project root.
It’s based on a prototype one of ourÂ commenters mentioned on Tim’s post. Thanks Mike!
I’ve been learning Clojure recently, and I’d been looking around for a good initial project to test my new knowledge. I’ve always wanted to write a Befunge interpreter, and so decided that sounded like a fun project. Little did I know the maze of twisty little passages I was letting myself in for, but I’ve learnt a lot of interesting things along the way, and there’s a few things worth sharing.
Clojure has an interesting implementation of a Huet-style zipper. I started translating it to Smalltalk, and in the process discovered a number of things not really related to zippers. Given that the end result ends up looking very similar to something we’ve already seen , let’s talk more about the translation process itself.
You are currently browsing the archives for the Clojure category.