Monoids in PHP

Sometimes the only way to grok a functional programming concept is reimplementing it. Monoids are a mathematical and functional structure that it's difficult to find appealing at a first glance, but that shines when employed in some real problem. I've taken the lesson from Dave Fayram and implemented the same approach in PHP. PHP is not a functional language, lacking lazy evaluation and immutability for example; however, it's flexible enough to let me implement monoids for a limited set of classes.

Definition

A monoid - in its mathematical definition - is a set closed against an operation with a null* element. The classic example is the set of integer beings closed against addition, with 0 as the null element.

There are many more hidden monoids even in imperative languages such as PHP. Strings with respect to concatenation, and numerical arrays with respect to merging are monoids. Their null elements are respectively the emtpy string and the empty array().

The problem

The original problem to show the use of monoids is FizzBuzz. I like this problem as it is simple enough to be implement in less than a Pomodoro by a programmer,leaving time for experimentation.

FizzBuzz maps an integer to a phrase composed by some keywords - for example, 15 maps to FizzBuzz while 3 maps to Fizz. Many numbers are mapped to themselves - 4 is mapped to 4.

Imperative implementation

Here is an OO implementation, widely overengineered to encapsulate the composing logic into a Result object, which also lets us specify the default value as the number itself.

class FizzBuzz
{
  private $words;

  public function __construct()
  {
      $this->words = array(
      3 => 'fizz',
      5 => 'buzz',
      );
  }

  public function say($number)
  {
      $result = new Result($number);
      foreach ($this->words as $divisor => $word) {
          if ($this->divisible($number, $divisor)) {
              $result->addWord($word);
          }
      }
      return $result;
  }

  private function divisible($number, $divisor)
  {
      return $number % $divisor == 0;
  }
}

class Result
{
  private $result;
  private $words = array();

  public function __construct($number)
  {
    $this->number = $number;
  }

  public function addWord($word)
  {
    $this->words[] = $word;
  }

  public function __toString()
  {
    if ($this->words) {
      return implode('', $this->words);
    }
    return (string) $this->number;
  }
}

I should have probably named the parameter of Result::__construct() $default.

Functional solution

Here's my porting of the functional solution from the original link to PHP:

<?php
class FizzBuzz
{
  private $words;

  public function __construct()
  {
    $this->words = array(
      3 => Words::single('fizz'),
      5 => Words::single('buzz'),
      7 => Words::single('bang'),
    );
    $this->divisors = array_keys($this->words);
  }

  public function say($number)
  {
    $words = array_map(function($divisor) use ($number) {
      return $this->wordFor($number, $divisor);
    }, $this->divisors);
    return reduce_objects($words, 'append')->getOr($number);
  }

  private function wordFor($number, $divisor)
  {
    if ($number % $divisor == 0) {
      return Maybe::just($this->words[$divisor]);
    }
    return Maybe::nothing();
  }
}


interface Monoid
{
  /**
  * @return Monoid
  */
  public function append($another);
}

function reduce_objects($array, $methodName)
{
  return array_reduce($array, function($one, $two) use ($methodName) {
    return $one->$methodName($two);
  }, Maybe::nothing());
}

class Maybe implements Monoid
{
  public static function just($value)
  {
    return new self($value);
  }

  public static function nothing()
  {
    return new self(null);
  }

  public function getOr($default)
  {
    if ($this->value !== null) {
      return $this->value;
    }
    return $default;
  }

  private $value;

  private function __construct($value)
  {
    $this->value = $value;
  }

  public function __toString()
  {
    return (string) $this->value;
  }

  public function append(/*Maybe*/ $another)
  {
    if ($this->value === null) {
      return $another;
    }
    if ($another->value === null) {
      return $this;
    }
    return Maybe::just($this->value->append($another->value));
  }
}

/**
 * A Monoid over ('', .)
 */
class Words implements Monoid
{
  private $words = array();

  public static function identity()
  {
    return new self(array());
  }

  public function single($word)
  {
    return new self(array($word));
  }

  private function __construct($singleWord)
  {
    $this->words = $singleWord;
  }

  public function append(/*Words*/ $words)
  {
    return new self(array_merge($this->words, $words->words));
  }

  public function __toString()
  {
    return implode('', $this->words);
  }
}

class FizzBuzzTest extends PHPUnit_Framework_TestCase
{
  public static function numberToResult()
  {
    return array(
      array(1, '1'),
      array(3, 'fizz'),
      array(5, 'buzz'),
      array(6, 'fizz'),
      array(10, 'buzz'),
      array(15, 'fizzbuzz'),
      array(3*5*7, 'fizzbuzzbang'),
    );
  }

  /**
  * @dataProvider numberToResult
  */
  public function testNumberIsMappedToResult($number, $result)
  {
    $fizzBuzz = new FizzBuzz();
    $this->assertEquals($result, $fizzBuzz->say($number));
  }
}

I am using a Maybe object too to deal with the default value, and I recognize the combination of Maybe and monoids is very flexible. Comparing it to PHP, it's like being able to write:

42 * null
array('value') + null

instead of

42 * 1
array('value') + array()

with a missing value (null) being recognized as the null element of the operation. Unfortunately, this isn't supported at the language level, so this logic had to be implemented in the Maybe class, which was tricky to write but did not take much time. Functional concepts have brought me a different OO design, since I don't think I would have thought of reducing objects.

Conclusions

You know when they say learning a functional language makes you a better programmer even in your current OO, imperative language? It's mostly true, but keep in mind that most of the tricks cannot be ported back at a reasonable cost due to the lack of support at the language level. For example, a Maybe class is on the border line as something you should rely on at the language level, since it's boring and error-prone to write it or import it again in every code base. The same goes for monoids and primitives: PHP's array_map is not as low-profile as Clojure's map as it will fight the style of the rest of the project and of other programmers.

That said, I'm the first to recognize that the functional approach to the Game of Life shortens the implementation time to 25', even in an imperative language like PHP.