Friday, August 25, 2017

String Calculator with Applicative Functors in Haskell

I like the simplicity of the String Calculator kata. It's a typical example of the map-reduce algorithm, where the string has to be split by a delimiter, mapped into a list of integers and then reduced to their sum. I have often used it as an example to quickly evaluate engineering candidates, try new languages and tools. This was the first challenge I tried to solve in Haskell about a year ago. I found the code the other day, I wanted to see how I could improve upon it with everything I've learned so far.

This is what I found from a year before:

import Test.Hspec
import Data.List.Split (splitOn)

calculator :: String -> Integer
calculator x = sum $ coerceString x ","

coerceString :: String -> String -> [Integer]
coerceString x c = map (coerce) (splitOn c x)
    where
        coerce "" = 0
        coerce a = read a :: Integer

main :: IO ()
main = hspec $ do
    describe "String Calculator" $ do
        it "returns 0 for empty string" $ do
            calculator "" `shouldBe` 0
        it "returns 1 for '1'" $ do
            calculator "1" `shouldBe` 1
        it "returns 3 for '1,2,3'" $ do
            calculator "1,2,3" `shouldBe` 6

This works for simple cases, but what should I do when there is a non-numeric string in the input arguments?

        it "returns 0 for '1,2,!'" $ do
            calculator "1,2,!" `shouldBe` 0

The algorithm crashes as I suspected:

String Calculator
  returns 0 for empty string
  returns 1 for '1'
  returns 3 for '1,2,3'
  returns 0 for '1,2,!' FAILED [1]

Failures:

  string_calculator_01.hs:22:
  1) String Calculator returns 0 for '1,2,!'
       uncaught exception: ErrorCall (Prelude.read: no parse)

Randomized with seed 1943023196

Finished in 0.0023 seconds
4 examples, 1 failure

I could easily wrap the entire logic and return zero when an exception occurs, however, Haskell can do better. Much better.

I can return a Maybe Int from the operation that parses the string to an integer: if the result is Nothing here, the overall result will be Nothing.
There is a string parser in the Text.Read module that does just that, it's called readMaybe.

Here is how it works:

 % ghci
GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /Users/adomokos/.ghci
λ> import Text.Read
λ> (readMaybe "12") :: Maybe Int
Just 12
λ> (readMaybe "!") :: Maybe Int
Nothing
λ>

I need to parse the list of strings, which is achieved by mapping over the values with readMaybe:

GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /Users/adomokos/.ghci
λ> import Text.Read (readMaybe)
λ> import Data.List.Split (splitOn)
λ> let xs = "1,2,3"
λ> splitOn (",") xs
["1","2","3"]
λ> map (\x -> readMaybe x :: Maybe Int) $ splitOn (",") xs
[Just 1,Just 2,Just 3]

I now have a list of Maybe Int values that can be reduced into a single Maybe Int value. Reducing an array of numbers would be super easy (foldl (+) 0 [1,2,3] or foldl1 (+) [1,2,3] or just simply sum [1,2,3]). It's obvious that I will need something similar.

Adding a number to a Maybe Int can be achieved with a Functor:

λ> fmap (+10) (Just 4)
Just 14
λ> (+10) `fmap` (Just 4)
Just 14
λ> (+10) <$> Just 4
Just 14

All three expressions mean the same thing. The first is using the fmap as a conventional function name and arguments style, the second one uses the infix version of fmap and the third one is using a symbol.

This works for adding a number to a Maybe Int, however, I need to use an Applicative Functor to calculate the sum of two Maybe Ints.

λ> (+) <$> Just 10 <*> Just 4
Just 14

Using Applicative Functors, folding the list of Maybe Ints happens like this:

λ> let xs = [Just 1, Just 2, Just 3]
λ> foldl (\acc x -> (+) <$> x <*> acc) (Just 0) xs
Just 6
λ> foldl1 (\acc x -> (+) <$> x <*> acc) xs
Just 6

The solution now works, although a bit hard to read:

import Test.Hspec
import Text.Read (readMaybe)
import Data.List.Split (splitOn)

calculator :: String -> Maybe Int
calculator input =
    foldr (\x acc -> (+) <$> x <*> acc) (Just 0) $
        map (\x -> readMaybe x) $ splitOn "," input

main :: IO ()
main = hspec $ do
    describe "String Calculator" $ do
        it "returns Nothing for empty string" $ do
            calculator "" `shouldBe` Nothing
        it "returns Just 1 for '1'" $ do
            calculator "1" `shouldBe` Just 1
        it "returns Just 3 for '1,2,3'" $ do
            calculator "1,2,3" `shouldBe` Just 6
        it "returns Nothing for '1,2,3,!'" $ do
            calculator "1,2,3,!" `shouldBe` Nothing

It's more meaningful after I've refactored it into chunks:

calculator :: String -> Maybe Int
calculator input =
    let foldingFn acc x =  (+) <$> acc <*> x
        parsedInts = map (\x -> readMaybe x) . splitOn (",")
    in foldr1 (foldingFn) (parsedInts input)

The parsedInts function can be further simplified:

calculator :: String -> Maybe Int
calculator input =
    let foldingFn acc x =  (+) <$> acc <*> x
        parsedInts = map (readMaybe) . splitOn (",")
    in foldr1 (foldingFn) (parsedInts input)

And finally, the sum of list of Maybe values can be calculated by using the sequence function like this:

calculator :: String -> Maybe Int
calculator input =
    let parsedInts = map (readMaybe) . splitOn (",")
    in fmap sum . sequence $ parsedInts input

I find this form to be the most readable, but I liked the journey of getting there through the Applicative Functors.

Wednesday, June 28, 2017

Scenario Outline in RSpec

Some business logic is best described in a table format. The rows and columns can better detail all the different permutations, than words and sentences. Gherkin handles this well with its scenario outlines, however, RSpec does not have such feature.

As I wanted to test all the different permutation of a business logic, I ended up with a ~200 lines spec file. It was hard to review what use cases were covered as I had to scroll up and down to review the file. Had RSpec have a table format, this logic could have been described in 40 lines, which can easily fit into a screen.

It was obvious a simple DSL was needed, but what would that look like? This is what I came up with first:

RSpec.describe 'eating apples' do
  def method_under_test(start, eat, left)
    start - eat == left
  end

  def example_runner(examples)
    lines = examples.split(/\n/)
    lines.delete_at(0) # Don't need the title
    lines.each do |line|
      example = line.split('|')
      start, eat, left = example.reject(&:blank?).map(&:to_i)
      expect(method_under_test(start, eat, left)).to eq(true)
    end
  end

  it 'can tell how many are remaining' do
    examples =
      <<~TABLE
        | start | eat | left |
        | 12    | 5   | 7    |
        | 20    | 5   | 15   |
      TABLE

    example_runner(examples)
  end
end

I am using the example_runner method to parse the examples table and run the specs one by one. The spec itself is clear, the examples TABLE is easy to visualize.

The spec documentation, however, does not reveal the used table. This is what it looks like:

eating apples
  can tell how many are remaining

Let’s say, one of the examples will trigger an error. When I change the second example’s “left” column’s 15 value to 16, this is what I see when I run the spec.

F

Failures:

  1) eating apples can tell how many are remaining
     Failure/Error: expect(method_under_test(start, eat, left)).to eq(true)

       expected: true
            got: false

       (compared using ==)

This is not very useful. I don’t know which example failed. Fortunately RSpec lets us provide more context for an expectation. When I change the line of the assertion with an added context like this,

expect(method_under_test(start, eat, left)).to eq(true), line

the example that failed is properly reported by RSpec:

F

Failures:

  1) eating apples can tell how many are remaining
     Failure/Error: expect(method_under_test(start, eat, left)).to eq(true), line
       | 20    | 5   | 16   |

This could be a decent solution, however, not printing the examples for the documentation output has major drawbacks. Every row in the table should be a separate example, it should be expressed as such. With some clever formatting and using include_example a similar table layout can be achieved. Consider this example:

RSpec.describe 'eating apples' do
  def method_under_test(start, eat, left)
    start - eat == left
  end

  RSpec.shared_examples 'eating_apples' do |example|
    it "calculates the remaining apple for - #{example}" do
      parsed_example = example.split('|')
      start, eat, left = parsed_example.reject(&:blank?).map(&:to_i)

      result = method_under_test(start, eat, left)
      expect(result).to eq(true)
    end
  end

                                     # start | eat | left
                                     # ______|_____|_____
  include_examples 'eating_apples', '  12    | 5   | 7'
  include_examples 'eating_apples', '  20    | 5   | 15'
end

The table is shifted to the right, but it’s clearly visible, and the commented out header provides a different color in my IDE that separates it from the data.

include_examples

The shared_example is also a lot simpler, I don’t need to deal with the header information, as it’s not passed to it, examples are being ran line by line.

By making the test description dynamic, the reporter prints out the tested values:

eating apples
  calculates the remaining apple for -   12    | 5   | 7
  calculates the remaining apple for -   20    | 5   | 15

The triggered error is properly reported by both the line number and the example used for that particular use case.

.F

Failures:

  1) eating apples calculates the remaining apple for -   20    | 5   | 16
     Failure/Error: expect(result).to eq(true)

       expected: true
            got: false

       (compared using ==)

I am not a big fan of adjusted white space for positioning equal signs under one another, but am happy to use white space to format test code to better describe the logic it validates.

RSpec does not have scenario outlines, but hopefully, with a shared_example and a bit of clever formatting the same can be accomplished.

Wednesday, May 31, 2017

Bit Shifting for a Shard ID in Ruby

As our database grew, we had to take a serious look at how can we could split it up by our clients, as most of them wanted to have their own data separate from the others anyway. A few months ago I found a great article from Pinterest, that describes how they sharded their MySQL database.

A sharded entity needs a UUID to uniquely identify the record across all shards. Most of the programming languages can generate a UUID easily, however, what was amazing to me, was that Pinterest generated its own unique ids by encapsulating three distinct numbers in one. Wait, what??! Read that article, it’s definitely worth your time.

While Pinterest encapsulated three numbers into one, we only needed two, a client_id and an entity_id. Our client_id would be a much smaller number than our entity_id, we wanted to reserve more bits for the latter.

It turns out, Ruby has many friendlier tools to deal with binary operations. Let's look at them!

What is the binary representation of the integer number 123?

123-in-binary

Out of the 7 bits, you'll see that the 3rd one is turned off, all the others are turned on, giving us 64 + 32 + 16 + 8 + 2 +1 = 123. How can we get this binary representation in Ruby? It's super easy, just use the to_s(2) method to do it.

pry(main)> 123.to_s(2)
=>"1111011"

This is the exact same string representation as the one in the image above, where the third bit is turned off and represented with a zero.

I'd like to keep the client_id on the left side, but I'd like to reserve bits on the right side. For the sake of simplicity, I will keep this as a small number. Let's add 5 bits to the right-hand side of these bits by using the bitwise left shift operator.

pry(main)> (123 << 5).to_s(2)
=> "111101100000"

The original number, 123, is still represented on the left side, but 5 "0"s were added to the right-hand side. You get the numeric representation of this by leaving out the to_s(2) call at the end:

pry(main)> 123 << 5
=> 3936

This number can be converted back to binary:

pry(main)> 3936.to_s(2)
=> "111101100000"

On the left side I have the binary representation of 123, but how about those bits on the right side? What are those representing? Right now, those bits are all turned off, they will give you 0 ("00000".to_i(2) => 0). How can I store the number 3 on the right side? The bits should look like this:

3-on-right-side

The binary "|" will turn the two rightmost bits on:

pry(main)> (123 MM 5 | 3).to_s(2)
=> "111101100011"

Again, leaving out the to_s(2) will provide the number representation:

pry(main)> (123 << 5 | 3)
=> 3939

The storing part will work, but how can we get our two numbers back from this one combined number? Well, we have to split the bits and convert the binary representation to an integer.

Five bits were used on the right side to store our second number. We need to chop those off to get the number stored on the left side. The bitwise right shift (>>) will do just that:

pry(main)> (3939 >> 5).to_s(2)
=> "1111011"

The string "1111011" is our original 123 in a binary string format. We can convert that to an integer by using the to_i(2) String method:

pry(main)> (3939 >> 5).to_s(2).to_i(2)
=> 123

I right shifted the original number, 3939, converted it to a binary string and converted that to an Integer.

There are more efficient ways to do this by using a binary "&" (3939 >> 5) & 0b1111111 => 123 with the max value the bits can represent. That's what the Pinterest article had, but I found using the Ruby conversion methods a bit more friendly to those of us who are not dealing with binary data on a daily basis.

We have the number on the left side, but what about the number on the right side? When we convert the number representation (3939) to a binary string, we know that the five characters on the right side will represent the bits of our other number. Ruby String’s last(x) will do just that:

pry(main)> (3939 >> 0).to_s(2).last(5)
=> "00011"

Converting this binary String to Integer should be similar to what we've done before:

pry(main)> (3939 >> 0).to_s(2).last(5).to_i(2)
=> 3

Using the binary "&" with the max number the bits can store will do this conversion in one step: (3939 >> 0) & 0b11111 => 3. As a side note, the binary number can be represented as a hexadecimal value: (3939 >> 0) & 0x1F => 3. This is a lot shorter than a series of ones and zeros.

There is a limit of how large the numbers can be as you have a limit of bits to store those. The max number can be determined by flipping the available bits on. For an 7 bit number it's 64 + 32 + 16 + 8 + 4 + 2 + 1 = 127 or 2**x-1, where x is the number of bits. In our case it is 2**7-1 = 127.

We ended up using a 64-bit Integer for our shard_id, which is a BIGINT in MySQL. We store client_id in 22 bits giving us the maximum of 2**22-1 = 4_194_304 and 40 bits for the entity_id with 2**40-1 = 1_099_511_627_775 max value. The remaining two bits are "worth in gold, we can expand the number or store a third (albeit small) number in it.

Tuesday, April 25, 2017

Fireside Chat

When I saw a retweet from Jason Fried about available tickets to a fireside chat with him at Basecamp, I jumped on it. I figured if I can kill two birds with one stone, - meeting him in person and seeing their offices - it's a no-brainer. Company Culture was the topic of the conversation led by Aimee Groth, who visited Chicago to publicize her new book, Kingdom of Happiness about Zappos' culture.

Basecamp HQ

Basecamp HQ is as cool as you think it is. Very few desks, a couple of meeting rooms. It reminded me more of a train terminal with its large windows and limited furnishing than a real office. The office is centered around an auditorium, which is an effective PR and educational platform for the company.

I enjoyed looking at the walls covered with postcards from employees all over the world, but I especially liked David's H-1B approval notice from the USCIS from 2005. I laughed out loud when I noticed it, as I had to go through similar hassle myself, but mine is safely guarded with my documents at home.

Basecamp works in six weeks work schedule. Whatever the team can get down in six weeks, they will deliver it. The scope can change, but the six weeks schedule is hard set. This timeframe helps them delivering functionality, and since the company is working remotely, it worked out well for them.

They don't have managers who only manage people or projects, the teams are led by team leads. These team leads are developers as well, shipping code on a daily basis. Jason and his team realized that managers who do not code, grow away from the work. According to him, "professional (full time) managers forget to do the work".
At one point they've tried rotating team leads, but that did not work out, as the continuity was lost. I could see that: "I see this problem, but I won't deal with it, I'll leave it for the next person, who will take over." Basecamp is looking for people who are self-managed, however, Jason emphasized multiple times: "people like to be led". It's important to "rally the folks by clear goals and purpose".

Jason also talked about the Jeff Bezos investment in the company, which meant a small ownership stake in Basecamp. They did not need the money to survive, David and Jason felt having a person like Mr. Bezos is mutually beneficial to both parties. "Who would not like to have Jeff Bezos as an advisor in his or her company?!" They have not talked to Jeff Bezos for a while, but if they wanted to, they could just reach out to his secretary, set up a meeting, and Jeff would fly to Chicago for a meeting or dinner with them.

The best advice from Bezos - and according to Jason, this was worth the entire dividend they have paid for his investment - was: "invest in the things in your business, that won't change". Don't chase the shiny new things, stick to what will not change. For them, it's Basecamp. The company had 4-5 products that they sold a couple of years ago to focus on their main product, which is Basecamp.

Jason went into details why other products were divested (like HighRise, Backpack, Campfire). Maintaining the web, Android and iOS versions of their products resulted in 15 different projects. That led to insufficient focus for each platform for each product with the employees they had at the time. They could - of course - have hired other developers, but they intentionally wanted to stay small. They did not want to get richer, be the next billionaire, they were just as happy with what they had. This sounds strange, almost naive in the era of bloated startups that are bleeding money chasing to be the next Facebook.

I enjoyed the Q&A at the very end. Some interesting questions came up about the startup community in Chicago, about VCs in general. Jason kindly offered to stay as long as everybody's questions were answered. Really a courteous offer, considering it was after 8 pm on a Friday night.

Oh, yes, and one more thing: Basecamp has 130,000 paying customers. It's a remarkable achievement by a company that has never taken VC money, was profitable from the get-go, and created an exciting app in the "not-so-exciting" domain of project management.

Tuesday, March 28, 2017

Containers

As I was exploring how to make Golang even faster on AWS Lambda, I found a project that promised sub-millisecond execution time compared to my (already pretty good) ~60 millisecond. It used Python execution that ran the Go code in-process in contrast to my attempt, where I had to spawn a new process and execute the lambda code there. Very clever, no wonder that solution did not have the 60-millisecond penalty for running that code. However, in order to build the sample code for this AWS Lambda I had to use Docker.

I've heard about Docker years ago, understood what it's used for at a very high level, however, I have never really given it a serious try. I figured it was time. Boy, I was in for some pleasant surprise!

The project AWS Lambda Go from Eawsy used Docker to containerize their build environment on my laptop. What does that mean? Imagine having a build server running on your computer in seconds, where the version of the Go compiler, the Python environment is set by the author of the Dockerfile. I'd use a little build engine that takes in my code, runs its magic and a zip file comes out that I can run on Lambda. What?!

I wrote all these different tutorials about running MRI Ruby on AWS Lambda or interacting with a Postgres DB with Clojure and I had to set up all the prereqs in plain text: "you have to have Postgres running, and Clojure, and MRI Ruby". I provided all the different Makefile scripts to follow the examples. However, with Docker, I'd just provide a Dockerfile that sets up the environment in the future.

I believe containers are big and will be even bigger very soon.

I see more and more applications where the code describes the behavior and the container descriptor describes the environment.


They live side by side, clearly stating what virtual components the software needs to execute. Engineers can run the software with those containers locally, and the software can be deployed to the cloud with those images pre-built, with tight control over its execution context.

There are many resources to learn Docker. I started with reading the Docker in Action book and went further by reading the Docker in Practice book.

I created a Docker templates repository, where I collected ideas for different recipes. Do I need a Ruby worker with Redis and Postgres backend? I'll just run docker compose up with this docker_compose.yml file and I have an environment, where everything from the OS to the version of Redis and Postgres is predefined. If it works on my machine, it will work on yours, too.

There are many things I like about Docker as compared to Vagrant or other virtual machine solutions. The biggest thing for me is the low power Docker containers would need. Vagrant images would reserve 2 of your 4 cores and 8GB memory when Docker will only take from the host as much as it needs. If it's 32MB, that's it, if it's 1GB, it will take that much.

Docker is the future, and you will see more and more code repos with a Dockerfile in it.

Wednesday, February 8, 2017

Golang

The first time I heard about Golang was a few years back, when the great guys at Brad's Deals, our next door office neighbor organized and hosted the local Go meetup there. Then IO.js and Node.js war broke out and TJ Holowaychuck shifted from Node.js to Golang announcing the move in an open letter to the community.
I did not think much of the language, as its reputation was far from the beauty of a real functional language.

Fast forward a couple of years and I am giving Ruby a serious try on AWS Lambda. Ruby works there, however, it needs enough memory and 3000 ms (3 seconds) to do anything. We have to invoke some of them millions of times in a month and when we calculated the cost for it, the bill gets fairly large quickly.

I created a simple AWS Lambda with Ruby just to print the words "Hello, World!" with 128 MB memory. It took 5339 ms to execute it.

Ruby Hello World on AWS Lambda

Then one night I wrote a tiny Go program:

package main

import "fmt"

func main() {
  fmt.Println("Hello, World!")
}

I cross compiled (since I am working on OSX) with the command GOOS=linux GOARCH=amd64 go build github.com/adomokos/hello to Linux, packaged it up with a Node.JS executor and ran it. I couldn't believe my eyes, it took only 68 ms to get the string "Hello, World!" back. 68 ms! And it was on a 128 MB memory instance. It was beautiful!

Go Hello World on AWS Lambda

Ruby would need four times the memory and it would still execute ~10 times slower than Go. That was the moment when I got hooked.

Go is a simple language. I am not saying it's easy to learn, it's subjective: it depends on your background, your experience. But it's far from the beauty of Haskell or Clojure. However, the team I am working with would have no trouble switching between Go and Ruby multiple times a day.

What kind of a language today does not have map or reduce functions?! Especially when functions are first-class citizens in the language. It turns out, I can write my own map function if I need to:

package collections

import (
  "github.com/stretchr/testify/assert"
  "strconv"
  "testing"
)

func fmap(f func(int) string, numbers []int) []string {
  items := make([]string, len(numbers))

  for i, item := range numbers {
    items[i] = f(item)
  }

  return items
}

func TestFMap(t *testing.T) {
  numbers := []int{1, 2, 3}
  result := fmap(func(item int) string { return strconv.Itoa(item) }, numbers)
  assert.Equal(t, []string{"1", "2", "3"}, result)
}

Writing map with recursion would be more elegant, but it's not as performant as using a slice with defined length that does not have to grow during the operation.

History

Go was created by some very smart people at Google, I wanted to understand their decision to keep a language this pure.
Google has a large amount of code in C and C++, however, those languages are far from modern concepts, like parallel execution and web programming to name a few. Those languages were created in the 60s and 80s, well before the era of multi-core processors and the Internet. Compiling a massive codebase in C++ can easily take hour(s), and while they were waiting for compilation, the idea of a fast compiling, simple, modern language idea was born. Go does not aim to be shiny and nice, no, its designers kept it:

  • to be simple and easy to learn
  • to compile fast
  • to run fast
  • to make parallel processing easy

Google hires massive number of fresh CS graduates each year with some C++ and Java programming experience, these engineers can feel right at home with Go, where the syntax and concept is similar to those languages.

Tooling

Go comes with many built-in tools, like code formatting and benchmarking to name the few. In fact I set up Vim Go that leverages many of those tools for me. I can run, test code with only a couple of keystrokes.

Let's see how performant the procedure I wrote above is. But before I do that I'll introduce another function where the slice's length is not pre-determined at the beginning of the operation, this way it has to auto-scale internally.

func fmapAutoScale(f func(int) string, numbers []int) []string {
  // Initialize a slice with default length, it will auto-scale
  var items []string

  for _, item := range numbers {
    items = append(items, f(item))
  }

  return items
}

The function is doing the same as fmap, similar test should verify the logic.

I added two benchmark tests to cover these functions:

// Run benchmark with this command
// go test -v fmap_test.go -run="none" -benchtime="3s" -bench="BenchmarkFmap"
// -benchmem
func BenchmarkFmap(b *testing.B) {
  b.ResetTimer()

  numbers := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
  for i := 0; i < b.N; i++ {
    fmap(func(item int) string { return strconv.Itoa(item)  }, numbers)
  }
}

func BenchmarkFmapAutoScale(b *testing.B) {
  b.ResetTimer()

  numbers := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
  for i := 0; i < b.N; i++ {
    fmapAutoScale(func(item int) string { return strconv.Itoa(item)  },
    numbers)
  }
}

When I ran the benchmark tests, this is the result I received:

 % go test -v fmap_test.go -run="none" -benchtime="3s" -bench="BenchmarkFmap"
    -benchmem
 BenchmarkFmap-4   ‡ 10000000 | 485 ns/op | 172 B/op | 11 allocs/op
 BenchmarkFmapAS-4 ‡ 5000000  | 851 ns/op | 508 B/op | 15 allocs/op
 PASS
 ok   command-line-arguments  10.476s

The first function, where I set the slice size to the exact size is more performant than the second one, where I just initialize the slice and let it autoscale. The ns/op displays the execution length per operation in nanoseconds. The B/op output describes the bytes it uses per operation. The last column describes how many memory allocations it uses per operation. The difference is insignificant, but you can see how this can become very useful as you try writing performant code.

Popularity

Go is getting popular. In fact, very popular. It was TIOBE's "Language of the Year" gaining 2.16% in one year. I am sure you'll be seeing articles about Go more and more. Check it out if you haven't done it yet, as the chance of finding a project or job that uses Go is increasing every day.

Sunday, November 13, 2016

Recursion Done Right - Haskell Influenced Recursion in Ruby

Learning Haskell has influenced the way I think about code. I wrote about currying before in various languages, but Haskell taught me a bit about how to do recursion properly.

Although fast paced, I really like the examples in the book Learn you a Little Haskell for Great Good. As one chapter talks about recursion and higher order functions, I was amazed by the simplicity of the code that lets you do basic list operations.

Here is how one could find the maximum of a list:

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of an empty list"
maximum' (x:xs) = max x (maximum' xs)

There is already a maximum function in Haskell's core library, this example just shows you what you need to do to implement it yourself.

I am not going into details about the type declaration, but there are a couple of points I'd like to talk about. The pattern matching in the second line checks for the case, where the collection is an empty array. When that happens, an exception is thrown. The last line does pattern matching as well, it grabs the head and the tail of the list and saves it into the x and xs variables. Then it uses the max functions to figure out which number is greater: x or the recurred result of maximum' with the tail of the list. This is a prime example of declarative code, its simplicity is striking and the fact that I don’t have to know how max works with the recursion makes it a joy to read.

Let’s look at another example. Here is how you could implement map in Haskell yourself:

map' :: (a -> b) -> [a] -> [b]
map' f [] = []
map' f (x:xs) = f x : map' f xs

Similarly, the edge-case is handled first. The last line has the logic, function f is applied to the head of the list, the result is concatenated with the recurred result of map' of f function and the tail of the list.

All right, let’s see how we could express this logic in Ruby.

Here is my first attempt:

module Collections
  def self.maximum(collection)
    head = collection.first
    tail = collection[1..-1]

    return 0 unless tail
    max head, (maximum tail)
  end

  def self.max(a, b)
    a > b ? a : b
  end
  private_class_method :max
end

RSpec.describe 'Recursion done right' do
   context 'maximum' do
     it 'returns an empty array as max of empty list' do
       expect(Collections.maximum([])).to eq(0)
     end

    it 'returns the maximum of a list' do
      expect(Collections.maximum([1,3,2])).to eq(3)
    end
  end
end

I did not find a max method in Ruby, I added that as a private class method. This is still pretty easy to read, but a bit more verbose than what I'd like it to be. I wanted to find the (x:xs) head-tail (car-cdr for you LiSP folks) equivalent in Ruby, I knew that will be key to make it a more succinct solution. This is it: (head, *tail) = collection. I also had to change the guard to quit from the recursion to look for an empty array, as the splat operator will provide that.

Here is my revised solution:

module Collections
  def self.maximum(collection)
    (head, *tail) = collection

    return 0 if tail.empty?
    max head, (maximum tail)
  end
  ...
end

This is better, but the destructuring can take place in the argument:

module Collections
  def self.maximum((head, *tail))
    return 0 if tail.empty?
    max head, (maximum tail)
  end
  ...
end

This is pretty darn close to the solution in Haskell.
Now let’s look at the map function.

These specs describe the behavior:

context 'map' do
  it 'mapping [] with (*3) gives []' do
    expect(Collections.map(->(x){ x*3 }, [])).to be_empty
  end
  it 'mapping [1,2,3] with (*3) gives [1,6,9]' do
    expect(Collections.map(->(x){ x*3 }, [1,2,3])).to eq([3,6,9])
  end
end

My implementation of map takes a lambda with one argument, which multiplies that one argument by three, and the second argument is the collection of items the map function will operate on.

This is my implementation for it:

module Collections
  def self.map(f, (head, *tail))
    return [] unless head

    [f.(head)] + map(f, tail)
  end
  ...
end

The key to make it concise is the destructuring the collection argument into head and tail. The guard statement makes sure the recursion will quit once there is no item in the head. The bulk of the logic is the last line of the method: the lambda is applied to the head, it's converted into an array and that value is concatenated with the result of the recurred result of the lambda and the rest of the collection.

In our case, the following calculation takes place:

map (*3) [1,2,3]
[(3*1)] + map (*3) [2,3]
[(3*1)] + [(3*2)] + map (*3) [3]
[(3*1)] + [(3*2)] + [(3*3)]
[3] + [6] + [9]
[3,6,9]

Haskell takes pride in how easily it implements the quicksort algorithm. Let’s see how it’s done there:

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerSorted = quicksort [a | a <- xs, a <= x]
        biggerSorted = quicksort [a | a <- xs, a > x]
    in  smallerSorted ++ [x] ++ biggerSorted

I don’t blame you if this seems to be a bit more cryptic than you wanted to be. It takes a little practice to read what is really going on here. I'll explain it, as it will help our own Ruby implementation. The first line is the type declaration, ignore that for now. The second line is the guard, sorting an empty array will give you back an empty array. The meat of the logic begins on the third line. The collection argument is destructured into head and tail, just like I've been doing in the examples above. Based on the head value, we are filtering the elements into smaller-equal, and bigger parts. We do all this recursively until the list is exhausted. Right before the result is returned, the three items, the smaller sorted, the head value and the bigger sorted elements are combined into one collection.

Let’s see how this is done in Ruby. Here are the specs I prepared to prove the logic:

context 'quicksort' do
  it 'returns an empty list for empty list' do
    expect(Collections.quicksort([])).to eq([])
  end
  it 'sorts a list of items' do
    expect(Collections.quicksort([2,5,3])).to eq([2,3,5])
  end
end

Here is how I'd like the code to be:

def self.quicksort((head, *tail))
  return [] unless head

  smaller_sorted = quicksort(Collections.filter(->(x) { x <= head }, tail))
  bigger_sorted = quicksort(Collections.filter(->(x) { x > head }, tail))
  smaller_sorted + [head] + bigger_sorted
end

This logic is very close to the Haskell example, but unfortunately, I don't have the filter function just yet. (Ruby standard library offers the select method on enumerables, but let's keep these examples free from all that.) filter takes a lambda as its predicate function, and a collection it needs to operate on. This spec proves out our logic:

context 'filter' do
  specify 'filter (>2) [] returns an empty list' do
    expect(Collections.filter(->(x){ x > 2 }, [])).to be_empty
  end
  specify 'filter (>2) [1,3,5] returns [3,5]' do
    expect(Collections.filter(->(x){ x > 2 }, [1,3,5])).to eq([3,5])
  end
end

And the implementation is similar what you've seen before:

def self.filter(f, (head, *tail))
  return [] unless head

  if f.(head)
    [head] + filter(f, tail)
  else
    filter(f, tail)
  end
end

And now, when you run the entire spec, the quicksort implementation just magically works.

specs executed

Studying Haskell taught me a few things about recursion. The head and tail concept is essential to make the code simple and neat. Without that it would have been a lot more noisier. Whenever I used recursion before, I always felt I needed an accumulator. I wanted something I could jump to and investigate when something went wrong. I would have written the filter function like this before:

def self.filter(f, (head, *tail), accumulator=[])
  return accumulator unless head

  accumulator << head if f.(head)

  filter(f, tail, accumulator)
end

Although this works, adding the accumulator with a default argument to the list just makes this code a lot noisier, but I do like not having conditional branches in it, it's just easier to reason about this code.

You can review the examples in this gist.

Based on what you read here, try implementing replicate, take, reverse, repeat and zip functions yourself. In case you need directions, check out this gist to see how I did it.