Monoids

monoids.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Monoids\n",
    "\n",
    "Monoids are algebraic structures that have an identity element and an associative binary operation. So what is a monoid? It's a ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait \u001b[36mMonoid\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "trait Monoid[A] {\n",
    "  def mempty: A\n",
    "  def mappend(a0: A, a1: A): A\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... and the associativity and identity rules which cannot be enforced by Scala 😞\n",
    "\n",
    "Okay, but what can we do with it? Well the simplest thing to do is if we have a collection (monad) of monoids, we can apply the monoid's binary operation recursively over the elements of the collection. That means we can fold over the elements, starting from the monoid's identity and applying the binary operation recursively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mimport \u001b[36mPredef.{implicitly => as}\u001b[0m\n",
       "defined \u001b[32mfunction \u001b[36mmconcat\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import Predef.{implicitly => as} // `implicitly` is just too long :)\n",
    "// Haskell calls it mconcat, but it's also known as reduce\n",
    "def mconcat[A: Monoid](xs: A*): A = xs.fold(as[Monoid[A]].mempty)(as[Monoid[A]].mappend)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, create some instances, so we can try it out!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36madd\u001b[0m\n",
       "defined \u001b[32mfunction \u001b[36mmultiply\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "// Addition on numbers is a monoid\n",
    "def add[A: Numeric] = new Monoid[A] {\n",
    "  def mempty = as[Numeric[A]].zero\n",
    "  def mappend(a0: A, a1: A) = as[Numeric[A]].plus(a0, a1)\n",
    "}\n",
    "\n",
    "// as well as multiplication\n",
    "def multiply[A: Numeric] = new Monoid[A] {\n",
    "  def mempty = as[Numeric[A]].one\n",
    "  def mappend(a0: A, a1: A) = as[Numeric[A]].times(a0, a1)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note on syntax: our context bound acts the same way as it were an implicit evidence. So\n",
    "```\n",
    "  def mconcat[A: Monoid](xs: A*): A\n",
    "```\n",
    "and\n",
    "```\n",
    "  def mconcat[A](xs: A*)(implicit ev: Monoid[A]): A\n",
    "```\n",
    "are the same, the former being syntactic sugar. Which means..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36msumResult\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m7\u001b[0m\n",
       "defined \u001b[32mfunction \u001b[36msum\u001b[0m\n",
       "defined \u001b[32mfunction \u001b[36mproduct\u001b[0m\n",
       "defined \u001b[32mfunction \u001b[36mmconcatRight\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "// ... you specify your instance this way.\n",
    "val sumResult = mconcat(1,2,4)(add)\n",
    "\n",
    "assert(mconcat(1,2,4)(add) == 7)\n",
    "\n",
    "// okay but call this thing sum:\n",
    "def sum[A: Numeric](xs: A*) = mconcat[A](xs:_*)(add)\n",
    "\n",
    "assert(sum(1,2,4) == 7)\n",
    "\n",
    "assert(mconcat(1,2,4)(multiply) == 8)\n",
    "\n",
    "//name the product fold as well\n",
    "def product[A: Numeric](xs: A*) = mconcat[A](xs:_*)(multiply)\n",
    "\n",
    "assert(product(1,2,4) == 8)\n",
    "\n",
    "// Gr8! Let's try out if the associativity rule really holds for a\n",
    "// specific case\n",
    "def mconcatRight[A: Monoid](xs: A*): A =\n",
    "  xs.foldRight(as[Monoid[A]].mempty)(as[Monoid[A]].mappend)\n",
    "\n",
    "// ((1 + 2) + 4) = (1 + (2 + 4))\n",
    "assert(mconcat(1,2,4)(add) == mconcatRight(1,2,4)(add))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's concatenate lists! More generally, let's do it for all things that are iterable!\n",
    "\n",
    "Sure, simple as a cake!\n",
    "\n",
    "```\n",
    "  def multiply[A: Iterable] = new Monoid[A] {\n",
    "    def mempty = as[Iterable[A]].empty\n",
    "    def mappend(a0: A, a1: A) = as[Iterable[A]].concat(a0, a1)\n",
    "  }\n",
    "```\n",
    "\n",
    "Well, well, not so fast. There isn't a typeclass for standard Scala collection iterables. Instead we must use\n",
    "`CanBuildFrom` for these functionalities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mimport \u001b[36mscala.language.higherKinds\u001b[0m\n",
       "\u001b[32mimport \u001b[36mscala.collection.Iterable, scala.collection.generic.CanBuildFrom\u001b[0m\n",
       "defined \u001b[32mfunction \u001b[36mconcat\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import scala.language.higherKinds\n",
    "\n",
    "// this is a bit nasty. we don't have a typeclass for iterable structures in scala, we have to use\n",
    "// CanBuildFrom instead\n",
    "import scala.collection.Iterable, scala.collection.generic.CanBuildFrom\n",
    "def concat[A, I <% Iterable[A]](implicit bf: CanBuildFrom[I, A, I]) = new Monoid[I] {\n",
    "  def mempty = bf().result()\n",
    "  def mappend(a0: I, a1: I) = bf.apply().++=(a0).++=(a1).result()\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Basically, we restrict our monoid to be a implicitly convertible to an `Iterable`. Then we use an implicit builder for this collection. Another method would be to use a lower type bound instead of a lower view bound like this:\n",
    "\n",
    "```\n",
    "def concat[A, I <: Iterable[A]](implicit bf: CanBuildFrom[I, A, I]): Monoid[i]\n",
    "```\n",
    "\n",
    "The view bound has the advantage over a type bound to be able to work with `String`, which doesn't subclass nor `Iterable`, nor anything like it (it's just the plain `java.lang.String`), but Scala has an implicit conversion from it to `Seq`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mresultSeq\u001b[0m: \u001b[32mSeq\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m, \u001b[32m4\u001b[0m, \u001b[32m5\u001b[0m, \u001b[32m6\u001b[0m)\n",
       "\u001b[36mresultList\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m, \u001b[32m4\u001b[0m, \u001b[32m5\u001b[0m, \u001b[32m6\u001b[0m)\n",
       "\u001b[32mimport \u001b[36mscala.collection._\u001b[0m\n",
       "\u001b[36mmutableSeq\u001b[0m: \u001b[32mcollection\u001b[0m.\u001b[32mmutable\u001b[0m.\u001b[32mSeq\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mArrayBuffer\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m, \u001b[32m4\u001b[0m, \u001b[32m5\u001b[0m, \u001b[32m6\u001b[0m)\n",
       "\u001b[36mresultSet\u001b[0m: \u001b[32mcollection\u001b[0m.\u001b[32mSet\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mSet\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m3\u001b[0m, \u001b[32m4\u001b[0m, \u001b[32m6\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "// works for all sequences as long both all arguments are exactly T[U]\n",
    "val resultSeq = mconcat(Seq(1,2,3), Seq(4,5,6))(concat)\n",
    "val resultList = mconcat(List(1,2,3), List(4,5,6))(concat)\n",
    "\n",
    "import scala.collection._\n",
    "val mutableSeq = mconcat(mutable.Seq(1,2,3), mutable.Seq(4,5,6))(concat)\n",
    "\n",
    "// even sets!\n",
    "val resultSet = mconcat(Set(1,1,3), Set(4,4,6))(concat)\n",
    "assert(mconcat(Set(1,1,3), Set(4,4,6))(concat) == mconcatRight(Set(1,1,3), Set(4,4,6))(concat))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's great! Does it work for strings? With view bounds? Yes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mjoin\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "assert(mconcat(\"abc\", \"def\")(concat) == \"abcdef\")\n",
    "\n",
    "def join(xs: String*) = mconcat(xs:_*)(concat)\n",
    "\n",
    "assert(join(\"abc\", \"def\") == \"abcdef\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And that's all I wanted to say. Next it'll be something on applicative functors I guess.\n",
    "```\n",
    "(++) <$> [\"Boom\", \"Bang\"] <*> [\"?\", \"!\"]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bye!\n"
     ]
    },
    {
     "data": {
      "text/plain": []
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "println(\"Bye!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala 2.11",
   "language": "scala211",
   "name": "scala211"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala211",
   "pygments_lexer": "scala",
   "version": "2.11.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}