Functional Recursion with ADTs

First to Key! First to the EGG!

Sometimes, I feel like functional thinking is a lot like the gunthers in Ready Player One! Every day you find a new clue about how to do something clean and pure.

I ran into a bug today in hyper’s cache service, one of our clients reported the bug, the listDocs the feature was not returning all of the matched documents using the Redis adapter, based on the matching pattern.

The Redis scan command was being used to apply a MATCH pattern to the key set to return all the keys that matched that pattern. In order to prevent blocking the API only returns a count of 20 and a cursor to retrieve more if you would like. The cursor is a non-zero value and to get the next set you provide the cursor and continue to iterate until the cursor becomes 0 this lets you know the list is complete.

The first solution was an imperative while loops, which are scary, to say the least, I tend to avoid while loops, but I need a fix and this was the first solution I could clearly think through.

let list = []
    
    async function asyncScan(cursor) {
      return new Promise((resolve, reject) => {
        client.scan(cursor, "MATCH", store + '_' + pattern, (e, r) => {
          if (e) { return reject(e) }
          resolve(r)
        })
      })
    }

    // get initial list  
    let [cursor, keys] = await asyncScan(0)
    list = list.concat(keys)

    let done = false

    while (!done) {
      // if cursor === 0 exit
      if (cursor === '0') {
        done = true
        break;
      }
      // else get more keys
      [cursor, keys] = await asyncScan(cursor)
      // add the keys then check
      list = list.concat(keys)
    }

Not the greatest solution but it did the trick! Yay!

Can we do this in a functional way?

With recursion, we can iterate through a list by having the function call itself if it needs more, then when it is at the end return the result which will return through rest of the list. But how can this work in a lazy way?

Recursion is a powerful concept, and let’s take advantage of the chain feature of the async ADT

const matcher = `${store}_${pattern}`
return scan(0, "MATCH", matcher)
  .chain(getKeys(scan, matcher))

...

function getKeys(scan, matcher) {
  return function repeat([cursor, keys]) {
    return cursor === '0'
      ? Async.Resolved(keys)
      : scan(cursor, "MATCH", matcher)
          .chain(repeat)
	      .map(v => keys.concat(v))
  }
}

Much better!

Using a closure we can access the matcher, then create a repeat function to create a lazy recursion with Async.chain. Async.chain is a function that passes the current value of the ADT to function expecting an Async as its returning result. Then the ADT replaces the current ADT with the returned ADT from the chain function. By wrapping this ADT in a recursive function, we can continue to call itself until all of the keys are found. Then we append the keys together by using the map function and contacting the keys with the returning value, the end result is a full list of keys.

What do you think?

Summary

Using ADTs we can not only save lines of code, but make our code easier to read and easier to extend and easier to manage over time. Using ADTs are a bit of a learning curve, but once you start to understand map, chain, and concat so many tasks become declarative and efficient. Don't know where to start? Try https://github.com/MostlyAdequate/mostly-adequate-guide