Wednesday, December 28, 2016

Category theory for programmers

Partial order

From wikipedia:

In mathematics, especially order theory, a partially ordered set (or poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the set, one of the elements precedes the other. Such a relation is called a partial order to reflect the fact that not every pair of elements need be related: for some pairs, it may be that neither element precedes the other in the poset. Thus, partial orders generalize the more familiar total orders, in which every pair is related.

Formal definition:

A partial order is a binary relation over a set which is reflexive, antisymmetric and transitive:

  • if and then
  • if , then

The binary relation over sets is a partial order. In the category of sets, we can have a commutative diagram as below:

Which can be translated into a Venn’s diagram:

Kleisli category

A small code example:

myNegate :: Bool -> (Bool, String)
myNegate x = (not x, "myNegate")

stringify :: Bool -> (String, String)
stringify bool = (show bool, "stringify")

compose :: (a -> (b, String)) -> (b -> (c, String)) -> a -> (c, String)
compose f g x =
  let (x1, string1) = f x
      (x2, string2) = g x1
    (x2, string1 ++ "\n" ++ string2)

main :: IO()
main = do
  print $ (compose myNegate stringify) True

A more general illustration of the above code:

Here m a corresponds to (a, String) in the code. For an category E, the corresponding Kleisli category K exists if

  • There is an arrow in K for
  • in K corresponds to in E
  • Composition id defined in C, i.e.
  • Similary, association law holds in E.

If the Kleisli category exists for such a category E, then m is called a monad.



class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}


data Const c a = Const c
instance Functor (Const c) where
  fmap f (Const c) = Const c

data Identity a = Identity a
instance Functor Identity where
  fmap f (Identity a) = Identity $ f a

The Const functor illustrated:

Function type as a functor

Given a function f :: a -> b, we can convert the infix op into prefix and get f :: fun a b, and fun a is a functor. (You don’t have to use a prefix op, but perhaps that’s easier to reason with. Suit yourself.)

In the illustration above, I use the f then g notation (more logical to me) instead of the usual .

Contravariant functor

Contravariant functor is similar to (covariant) functor, but with the directions of all arrows flipped. See the illustration below:

In the diagram above F r is the type constructor that receive a type a and returns a function type a -> r.


Bifunctor illustrated:

From haskell documentation:

Formally, the class Bifunctor represents a bifunctor from Hask ->

Intuitively it is a bifunctor where both the first and second
arguments are covariant.

You can define a Bifunctor by either defining bimap or by defining
both first and second.

If you supply bimap, you should ensure that:

bimap id id ≡ id

If you supply first and second, ensure:

first id ≡ id
second id ≡ id

If you supply both, you should also ensure:

bimap f g ≡ first f . second g

Examples of bifunctor:

    instance Bifunctor Either where
        bimap f _ (Left a) = Left (f a)
        bimap _ g (Right b) = Right (g b)

    instance Bifunctor Const where
        bimap f _ (Const a) = Const (f a)

    instance Bifunctor (,) where
        bimap f g ~(a, b) = (f a, g b)

The ~(a,b) part is lazy pattern matching, this means the pattern matching assumes succes until a or b is actually used later.

Disect Maybe as a Bifunctor

data Maybe1 a = Nothing1 | Just1 a
-- equivalent to: Either () (Identity a)
-- equivalent to: Either (Const () a) (Identity a)
-- We know that both Const and Idenity are functors
-- Maybe1 is therefore a bifunctor

All algebraic data types are functorial, and Functor instances can be automatically generated in Haskell:

{-# LANGUAGE DeriveFunctor #-}
data Maybe2 a = Nothing2 | Just2 a deriving Functor


A profunctor is similar to a bifunctor, but with one of the arrows flipped. For example, the function type (->) a b or a -> b is a profunctor:

In the diagram above, if f were pointing down, then the functor won’t work correctly, so -> is not a bifunctor.


A function with two parameters (z, a) and returns a b can be seen as a mapping from a Cartesian product to , as illustrated below:

The following diagram show how currying works from the category theory point of view:

Functional objects

A functional object represents all possible functions . Intuitively, the size of a functional object .

Type algebra

Let’s translate some haskell function syntax into functional object notation.

f :: Either a b -> c

-- currying
f :: c -> (b -> a) -- is equivalent to 
f :: c -> b -> a

f :: c -> (a, b) -- is somewhat equivalent to 
f :: (c -> a, c -> b)

Curry-Howard-Lambek isomorphism

Logic Types Category theory
True () Terminal object
False Void Initial object
(a, b)
Either a b
f :: a -> b

Natural transformation

The square on the right side is called the naturality square, in which . Here is a natural transformation.

Let’s zoom into the naturality square:

When , and are fixed, will be automatically determined.

Transformation from a high resolution functor F to a low resolution functor G:

Transformation from a high resolution functor F to a high resolution functor G:

Transformation from a low resolution functor F to a low resolution functor G:

Given a natural transformation as below:

alpha :: forall a. F a -> G a 

We get the following theorem for free (derived from the square of naturality):

alpha . fmap f = fmap f . alpha
-- type annotation,
-- on the left side
alpha :: F a -> G a
fmap :: (a -> b) -> G a -> G b
f :: a -> b 
-- on the right side
fmap :: (a -> b) -> F a -> F b
f :: a -> b
alpha :: F b -> G b

Here is an example of natural transformation:

safeHead :: [a] -> Maybe a 
safeHead [] = Nothing 
safeHead (x:_) = x

To show that the theorem holds:

f :: Int -> Int
f x = x + 1

(safeHead . fmap f) [] 
= safeHead []
= Nothing
(safeHead . fmap f) [1, 2]
= safeHead [2, 3]
= Just 2

(fmap f . safeHead) []
= fmap f Nothing
= Nothing
(fmap f . safeHead) [1, 2]
= fmap f (Just 1)
= Just 2

Composibility of natural transformations:

Identity of natural transformations:


In the diagram above, are categories, are functors, are natural transformations. The whole structure is called a 2-category because it’s a category of categories.

In a 2-category, an object is also called a 0-morphism, a functor is a 1-morphism, a natural transformation is a 2-morphism (morphism between morphisms), and so on.

Naturality and composability in a 2-category

Naturality and composability in a 2-category is more complicated than a 1-category because of higher-order morphisms:

In the diagram above, we have

If we trace a single object from category , we get the following diagram:

Notice the last layer forms a naturality square:

There, are functors and , is a natural transformation.

If we are to define the fmap function for , it would be something like:

fmap :: (F a -> F' a) -> G F a -> G F' a
fmap alpha GFa = 
    let G x = GFa
        G alpha x 


Bicategory is different from category in the sense that the identity and associativity laws hold up to isomorphism (hence less strict).


Let’s start with Kleisli arrows that was introduced before. In haskell the signature of a Kleisli arrow (fish operator, composition of two embellished arrows) is:

(>=>) :: (a -> m b) -> (b -> m c) -> mc

Trying to implement it:

(>=>) :: (a -> m b) -> (b -> m c) -> mc
f >=> g = \a -> 
    let xmb = f a
        xmb ...

We got a xmb :: m b and a g :: b -> m c, there is a type mismatch. This must be dealt with. We introduce a new operator, >>= (called bind):

-- will be implemented later
(>>=) :: m b -> (b -> mc) -> mc

(>=>) :: (a -> m b) -> (b -> m c) -> mc
f >=> g = \a -> 
    let xmb = f a
        xmb >>= g

Next try to implement bind, assuming m is already a functor:

(>>=) :: m b -> (b -> m c) -> mc
x >>= g = 
    let x1 = fmap g x

(>=>) :: (a -> m b) -> (b -> m c) -> mc
f >=> g = \a -> 
    let xmb = f a
        xmb >>= g

Now we have a x1: m m c, but we need a m c, this is begging for a new function m m c -> m c. In haskell it’s called join.

join :: m m a -> m a

(>>=) :: m b -> (b -> m c) -> mc
x >>= g = 
    let x1 = fmap g x
        join x1

(>=>) :: (a -> m b) -> (b -> m c) -> mc
f >=> g = \a -> 
    let xmb = f a
        xmb >>= g

So everything hangs on join. Time for a formal definition of monad:

class Functor m => Monad m where 
    join :: m (m a) => m a 
    return :: a -> ma

Once you fufilled your duty of defining join and return, >>= and >=> will be automatically defined for you.

In reality, haskell uses a different definition:

class Monad m where 
    (>>=) :: m a -> (a -> m b) -> m b 
    return :: a -> m a

And join is defined in terms of >>=.

The Maybe monad

join :: Maybe (Maybe a) -> May a
join Just (Just a) = Just a
join _ = Nothing

return :: a -> Maybe a
return a = Just a 

If we choose to define >>= instead (which might better explain the brilliance of Maybe):

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b 
Nothing >>= f = Nothing 
Just a >>= f = f a

Thursday, December 22, 2016

Small experiment with dependent types in Swift 3

//: Playground - noun: a place where people can play

import Cocoa

// warmup exercise
// get the types of variables using swift reflection
let x = Mirror(reflecting: (1, 2, "e"))
let y = Mirror(reflecting: (3, 4, "hello"))
// compare types
print(x.subjectType == y.subjectType)

class TypeT<T> { }
// return value is a Mirror (Swift jargon for reflection of types)
// this value depends on the value of the first param
func value<T>(_ val: Int, blank: T) -> Mirror {
    if(val == 0) {
        // if val is zero, then return the type of blank
        return Mirror(reflecting: blank)
    // otherwise, wrap the type of blank inside a TypeT and recurse.
    return value(val - 1, blank: TypeT<T>())

let x1 = value(3, blank: 0) // Mirror for TypeT<TypeT<TypeT<Int>>>

Thursday, February 11, 2016

Scala Enumerations

object EnumerationTypes extends App {

  object WeekDay extends Enumeration {
    type WeekDay = Value
    val Mon = Value("Mon")
    val Tue = Value("Tue")
    val Wed = Value("Wed")
    val Thu = Value("Thu")
    val Fri = Value("Fri")
    val Sat = Value("Sat")
    val Sun = Value("Sun")
    // Returns the value by name, if the name does not exist in the Enumeration, then return None
    def valueOf(name: String) = WeekDay.values.find(_.toString == name)
  import WeekDay._

  def isWorkingDay(d: WeekDay) = ! (d == Sat || d == Sun)
  val x = WeekDay.valueOf("Tue")

  WeekDay.values filter isWorkingDay foreach println

Friday, January 22, 2016

Let it be

From Beatles:

LET IT BE                       (Beatles)

                       G              D                 Em          Cmaj7    C6
                When I find myself in times of trouble, Mother Mary comes to me
                G                 D              C  G/B Am G
                Speaking words of wisdom, let it be

                And in my hour of darkness, She is standing right in front of me

                Speaking words of wisdom, Let it be

                        Em        G/D          C          G
                Let it be, let it be,  let it be, let it be
                G                D              C  G/B Am G
                Whisper words of wisdom, let it be

                And when the broken hearted people, Living in the world agree

                There will be an answer, let it be

                But though they may be parted, There is still a chance that they may see

                There will be an answer, let it be

        CHORUS: Let it be, let it be, let it be, let it be
           |    There will be an answer, let it be
           |    Let it be, let it be, let it be, let it be
           |    Whisper words of wisdom, let it be

                Let it be, let it be, let it be, let it be

                Whisper words of wisdom, let it be

                And when the night is cloudy, 
                There is still a light that shines on me

                Shine on till tomorrow, let it be

                I wake up to the sound of music, Mother Mary comes to me

                Speaking words of wisdom, let it be


               chords in instrumental section and ending:

               C  G/B   Am   G   F  C/E  D   C   G

Wednesday, January 13, 2016

Firebase comment app in javascript

var firebaseData = new Firebase('');
var commentsDB = firebaseData.child("comments");
//commentsDB.transaction(function(currentval) {
//  return (currentval || 0) + 1;

var getEpoch  = function() {
  return (new Date()).getTime();

var epochToDate = function(epoch) {
  var d = new Date(0);
  return d;

var handleCommentKeypress = function (e) {
  if (e.keyCode == 13) {
    var author = $("#author-field").val();
    var comment = $("#comment-field").val();
    if (author && comment) {
      var date = new Date();
      date = date.toString();
        {author: author, comment: comment, date: getEpoch()}
    } else {
      alert("Author and Comment are required fields!");

commentsDB.on("child_added", function (snap) {
  var entry = snap.val();
  var entryLI = $("<li></li>").text( + ": " + entry.comment + " [ " + epochToDate( + " ] "


var ref = new Firebase("");
ref.orderByChild("height").on("child_added", function (snapshot) {
  console.log(snapshot.key() + " was " + snapshot.val().height + " meters tall");

Tuesday, January 12, 2016

Javascript variable hoisting

var type = 'Ring Tailed Lemur';
function Lemur() {
 var type = 'Ruffed Lemur';

is translated into

var type = 'Ring Tailed Lemur';
function Lemur() {
 var type;
 var type = 'Ruffed Lemur';

undefined is logged in this case.

Manipulate clipboard in Javascript

window.addEventListener('copy', function (ev) {
    console.log('copy event');
    // you can set clipboard data here, e.g.
    ev.clipboardData.setData('text/plain', 'some text pushed to clipboard');
    // you need to prevent default behaviour here, otherwise browser will overwrite your content with currently selected 

Monday, January 11, 2016

Scala extractors

  * Created by kaiyin on 1/10/16.
object TestUnapply {
  case class Division(val number: Int) {
    def unapply(divider: Int): Option[(Int, Int)] = if (number % divider == 0) Some(number/divider, 0) else None
    def unapply(divider: Double): Boolean = number % divider.toInt == 0

  val divisionOf15 = Division(15)
  val y = 5 match {
    case divisionOf15(z, w) => s"$z, $w"
    case _ => s"Not divisible"

  val z = 5.0 match {
    case divisionOf15() => "Divisible"
    case _ => "Not divisible"

Friday, January 8, 2016

Relation between join, fmap and bind

Recognizing the equivalence:

join (fmap f ma) = ma >>= f


  join (fmap f ma)
  fmap f ma >>= id         -- join x = x >>= id                 (definition)
  (ma >>= return . f) >>= id
                           -- fmap f xs = xs >>= return . f              (1)
  ma >>= (\x -> (return . f) x >>= id)
                           -- m >>= (\x -> k x >>= h) = (m >>= k) >>= h  (2)
  ma >>= (\x -> return (f x) >>= id)
                           -- (f . g) x = f (g x)               (definition)
  ma >>= (\x -> id (f x))  -- return a >>= k = k a                       (3)
  ma >>= (\x -> f x)       -- id x = x                          (definition)
  ma >>= f                 --                                (eta reduction)

  (1) implied by monad laws
  (2) associativity monad law
  (3) left identity monad law

Credit to verement.

Monoid in scala

The monoid typeclass:

  * Created by kaiyin on 1/8/16.

object M {

  trait Monoid[A] {
    def append(a1: A, a2: A): A

    def empty: A

  object Monoid {
    implicit def ListMonoid[A]: Monoid[List[A]] = new Monoid[List[A]] {
      def append(a1: List[A], a2: List[A]) = a1 ::: a2

      def empty = Nil

    implicit def PairMonoid[A, B](implicit a: Monoid[A], b: Monoid[B]): Monoid[(A, B)] = new Monoid[(A, B)] {
      def append(ab1: (A, B), ab2: (A, B)) = (a.append(ab1._1, ab2._1), b.append(ab1._2, ab2._2))
      def empty = (a.empty, b.empty)

    def append[A](a1: A, a2: A)(implicit m: Monoid[A]): A = m.append(a1, a2)
    def empty[A](implicit m: Monoid[A]) = m.empty

import M.Monoid._
import M.Monoid

implicitly[Monoid[List[Int]]].append(List(1, 2), List(3, 4))

append(List(1, 2), List(3, 4))
append(List(List(1), List(2)), List(List(3), List(4)))
append((List(1, 2), List(5, 6)), (List(3, 4), List(7, 8)))

Monday, January 4, 2016

Riding the knight in haskell

Caluclate possible moves of a knight on a chess board:

import Control.Monad as M

type KnightPos = (Int, Int)

moveKnight :: KnightPos -> [KnightPos]
moveKnight (c, r) = do
  (c', r') <- possibleMoves
  M.guard (c' `elem` [1..8] && r' `elem` [1..8])
  return (c', r')
      possibleMoves = [
        \(a, b) (c, d) -> (c + a, d + b),
        \(a, b) (c, d) -> (c + a, d - b),
        \(a, b) (c, d) -> (c - a, d + b),
        \(a, b) (c, d) -> (c - a, d - b)
        ] <*> [(1, 2), (2, 1)] <*> [(c, r)]