Double Dabble Ramda

Recently at work I’ve switched from using Lodash to Ramda for functional programming extensions to Javascript/Coffeescript and I’m happier than I’ve pretty much ever been. Ramda isn’t the Javascript Holy Grail – that honor, I’m guessing, goes to PureScript – very much next in line on the list of things to learn – but it does help me write tight, readable code in a record amount of time. I’ve spent the last day cleaning up our database interface, and will move on to refactoring the API next.

For fun, here’s a walkthrough of a RamdaJS rewrite of the doubledabble code I posted here a month ago.

Warning: by double-dabble I mean a method of converting between binary and decimal encoding for numbers. I realize that a lot of people use it to mean a (highly similar) method for switching between decimal and binary coded decimal instead.

OK, so from last time, here’s the code to convert a binary number into its decimal equivalent

double_dabble = (input) ->
  (parseInt(i) for i in input.split('')).reduce((a,i) -> a * 2 + i)

Run this on "11110011" and you get 243, as you should.

It’s split into two parts – a (Coffescript) list comprehension and a reduce. So, it’s a standard map-reduce model:

  1. First we get our data into a representation we can work with by maping some transformers over it
  2. Then we reduce it to the final answer

The map phase consists of splitting the input string into individual characters and then converting those characters to their integer equivalents – so that we’re left with [Int] representation of the binary number we started with.

The reduce phase runs a lambda function of two arguments (an accumulator and the current item in the list) over the list, accumulating the final result. For each digit, it doubles the accumulator (because each digit represents an additional column of binary number – and in the same way that each additional column of a decimal number means we’re in a series that’s ten times as big as it would’ve been if there were one fewer column, in a binary system each additional column means "twice as big") and then adds the current digit to it – which is always either 1 or 0.

I like this way of organizing the code because map-reduce is a common pattern that I recognize. To me, this is highly readable code.

But "readable" is a matter of taste, and to some people – people who do a lot of functional programming in particular – function composition is perhaps an even more familiar pattern. And, they would argue (and they would have a good point), that unlike the map-reduce version I just gave you, doing this with function composition would directly encode the order in which all these operations apply. My map-reduce version scrambles that a little bit, making it look almost like you parseInt before you split the input string!

RamdaJS makes it really easy to use that pattern.

To recap, there are three things we have to do:

  1. Split the input string into characters (all of which are 1 or 0)
  2. Convert those characters into ints
  3. Reduce the resulting list to the answer (by maping a lambda function over it)

OK.

The first is just R.split

R.split('')('11110011') # ['1','1','1','1','0','0','1','1']

Next, we convert all that to ints

R.map(parseInt)(['1','1','1','1','0','0','1','1']) # [ 1, 1, 1, 1, 0, 0, 1, 1 ]

Then, we reduce it using our lambda function

R.reduce(((a,i) -> a * 2 + i), 0, [ 1, 1, 1, 1, 0, 0, 1, 1 ]) # 243

As you can see, it’s a classic compose case: the result of each function becomes the argument for the next. RamdaJS gives us a convenient way to do this:

R.compose(
  R.reduce((a,i) -> a * 2 + i)(0)
  R.map(parseInt),
  R.split('')
)

Very clear to anyone who is familiar with function composition.

But there are still opportunities for improvement. These include:

  1. It would be nicer if the reduce section more clearly took just one argument. It does, and it’s the right one, but passing in the lambda expression and 0 is a little awkward. Especially passing in 0, since that’s such a common base when reducing a list of ints that we’d kind of like there to be a reduceZero function that takes a reducer and then the list.
  2. It’s not immediately obvious that the lambda expression is itself a function composition, but it is. We should maybe make that more obvious.
  3. Since this is still a map-reduce, however much function composition is hiding that fact, it’d be nice to split this into the map and reduce sections just as before. Concretely speaking, there should really be only two items in the compose list.

First things first – making the reduceZero function. We want this to be a function that always seeds the accumulator with 0 and then takes a reducer, and then takes a list to reduce.

Ramda really shines here:

reduceZero = R.reduce(R.__, 0, R.__)

Each of those underscores are argument placeholders. Like (almost) all RamdaJS functions, R.reduce is curried, so you can either call it with all arguments at once, or call it with one argument at a time. Putting the placeholders there just monkeys with the order – so this gives us an R.reduce that already knows it will be seeding the accumulator with 0. Now it’s waiting on two other arguments – a reducer and a list … in that order. So, we’re done!

The next point was to make clearer that our lambda reducer is itself a composed function. Let’s do it like this:

R.compose(R.add, R.multiply(2))

First, double the argument, then add it to … let’s come back to that. To stress the point, (almost) all RamdaJS functions come curried, so R.multiply(2) is just a convenient way of making a doubler. It’s still expecting another argument to multiply by 2.

Why not call that what it is?

double = R.multiply(2)
R.compose(R.add, double)

Unfortunately, this won’t work as written, because our lambda function from before really needs to take two arguments: an accumulator and a list item. But function composition really needs to work with functions of single arguments. If it doesn’t, it won’t necessarily know which argument to pass to double and which to pass to add. Put differently, add receives , as its first argument, the result of doubleing some number. It then needs to take a second argument. If you run this as is, you get a function back – still waiting on that argument:

input = '11110011'
reduceZero = R.reduce(R.__, 0, R.__)
double = R.multiply(2)
doublePlus = R.compose(R.add, double)
 R.compose(
  reduceZero(doublePlus)
  R.map(parseInt),
  R.split('')
)(input) # [Function: f1]

But again, here’s where RamdaJS really shines!

We know what the problem is: we made a function that takes one argument when we need one that takes only two (because that’s what reduce expects). We need to "uncurry" the result – and Ramda gives us a convenient way to do that! You have to tell it how many arguments you want the final function to have, which is a little awkward, but also pretty safe.

input = '11110011'
reduceZero = R.reduce(R.__, 0, R.__)
double = R.multiply(2)
doublePlus = R.uncurryN(2,R.compose(R.add, double))
 R.compose(
  reduceZero(doublePlus)
  R.map(parseInt),
  R.split('')
)(input) # 243

The final desideratum is dead simple – just compose again.

input = '11110011'
reduceZero = R.reduce(R.__, 0, R.__)
double = R.multiply(2)
doublePlus = R.uncurryN(2,R.compose(R.add, double))
splitToInt = R.compose(R.map(parseInt), R.split(''))
 R.compose(
  reduceZero(doublePlus),
  splitToInt
)(input) # 243

How "readable" this is a matter of taste. To my taste, it’s very much so. I see a compose that composes two functions which have pretty clear names. If I know that splitToInt takes a string representing a number and turns it into a list of positional ints, and I know that reduceZero is a common application of reduce that starts with 0 as its accumulator, I’m most of the way there. I can see instantly that we have a "data preparation" ("map") section that feeds into a "data processing" (reduce) section. The only thing that’s in any way mysterious about this is the doublePlus bit, but that’s the idiosyncratic part of this operation that I’d have to look up no matter what.

So, I like it. And I like RamdaJS for making it so easy.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>