Encoding algebraic data type in JavaScript

JavaScript lacks algebraic data type, but we can emulate it because JavaScript has first-class functions.

Here’s a simple Haskell program declaring Tree data type with Bud, Leaf and Tree data constructors. treeSum calculates the sum of leaf nodes by iterating all nodes in the given tree.

data Tree = Bud | Leaf Int | Tree Tree Tree deriving Show

treeSum :: Tree -> Int
treeSum Bud = 0
treeSum (Leaf n) = n
treeSum (Tree t1 t2) = treeSum t1 + treeSum t2

main = do
	let t0 = treeSum Bud
	putStrLn $ show t0
	let t1 = treeSum (Leaf 2)
	putStrLn $ show t1
	let t2 = treeSum (Tree (Leaf 3) (Tree (Leaf 5) Bud))
	putStrLn $ show t2

In JavaScript, we can emulate the data constructors of Tree with higher order functions. The trick used here is to pass b, l and p as arguments to data constructors. Only one of these 3 arguments is used by each data constructor:

  • b is a value for Bud.
  • l is a function taking an integer n as an argument and returns a value for Leaf.
  • p is a function taking left and right trees as arguments and returns a value for Tree.

(ES6 let and arrow are used for conciseness.)

let Bud = b => l => p => b;
let Leaf = n => b => l => p => l(n);
let Tree = t1 => t2 => b => l => p =>
           p(t1(b)(l)(p))(t2(b)(l)(p))

You can think of Bud as a value by itself. For Leaf and Tree, you can create each node by partially applying arguments.

var t0 = Bud;
var t1 = Leaf(2);
var t2 = Tree(Leaf(2), Bud);

With this encoding scheme, defining treeSum is trivial. You just need to pass 3 functions to handle Bud, Leaf and Tree respectively. If w is Bud, it returns 0. If w is a Leaf node, it returns n. If w is a Tree node, it returns the sum of left and right trees.

let treeSum = w => w(0)(n => n)(x => y => x + y);

The client code looks almost the same to Haskell.

var v0 = treeSum(Bud);
console.log(v0);

var v1 = treeSum(Leaf(2));
console.log(v1);

var v2 = treeSum(Tree(Leaf(3))(Tree(Leaf(5))(Bud)));
console.log(v2);
Advertisements

Creating a ServerSentEventServer with ReactiveWebServer

Recently, I am working on a toy project named ReactiveWebServer. It is an event-driven web server built with Rx.

Here’s a simple web server returning “Hello World”.

using (var ws = new WebServer("http://*:8080/"))
{
    const string responseBody = "Hello World";

    ws.GET("/")
        .Subscribe(ctx => ctx.Respond(responseBody));

    Console.ReadLine();
}

The code is simple, but there is nothing new compared to other web servers such as NancyFx.

The real power of ReactiveWebServer comes from its ability to handle streaming data. For example, here’s a ServerSentEvent server implementation streaming integers every second.

using (var ws = new WebServer("http://*:8000/"))
{
    ws.GET("/events").Subscribe(ctx =>
    {
        var obs = Observable.Interval(TimeSpan.FromSeconds(1))
            .Select(t => new ServerSentEvent(t.ToString()));

        ctx.Respond(new ServerSentEventsResponse(obs));
    });

    Console.ReadLine();
}

Data streaming is made simple and easy. You just need to create an instance of IObservable<ServerSentEvents>, wrap it with ServerSentEventsResponse, and pass the result to ctx.Respond method.

Rx Study Materials

I recently taught myself Rx and found the following materials are helpful in understanding the concepts and the APIs of Rx.

  • The introduction to Reactive Programming you’ve been missing
    This article explains how to think in reactive. It explains the core concepts of reactive programming with many examples. This is not-specific to Rx, but most helpful in understanding what reactive programming is.

  • Introduction to Rx
    This is a book on Rx freely available. Part 3 is most helpful as it shows how to use each operator of Rx.

  • ReactiveX
    The best way to understand a Rx operator is to draw a marble diagram. ReactiveX explains each operator with marble diagram. For example, take a look at Repeat.

  • 101 Rx Samples
    This site hosts a number of Rx operator examples.

  • Rx Workshop
    Video tutorials on Rx provided by Microsoft Channel9.

Rx RetryWithDelay extension method

Rx provides Observable.Retry which repeats the source observable sequence until it successfully terminates.

Observable.Retry is a useful combinator, but it is a bit limited when retrying an I/O request. For example, when retrying a network request, we should wait a few seconds before sending a new request.

Here is an implementation of Observable.RetryWithDelay which repeats the source observable with delay.

    public static class ObservableExtensions
    {
        public static IObservable<T> RetryWithDelay<T>(this IObservable<T> source, TimeSpan timeSpan)
        {
            if (source == null)
                throw new ArgumentNullException("source");
            if (timeSpan < TimeSpan.Zero)
                throw new ArgumentOutOfRangeException("timeSpan");
            if (timeSpan == TimeSpan.Zero)
                return source.Retry();

            return source.Catch(Observable.Timer(timeSpan).SelectMany(_ => source).Retry());
        }
    }

After validating arguments, Observable.RetryWithDelay create a new observable sequence by concatenating the following two observables:

  • Observable.Timer(timeSpan)
  • source

SelectMany is used to concatenate these two observable sequences. Observable.Timer(timeSpan) has a single value that fires after timeSpan. SelectMany ignores this value and returns source. Then it repeats the result sequence with Retry.

  • Observable.Timer(timeSpan).SelectMany(_ => source).Retry()

This is the next observable sequence we want to continue when source is terminated by an exception. Catch swallows the exception thrown by source and continues with the next observable.

  • source.Catch(Observable.Timer(timeSpan).SelectMany(_ => source).Retry())

Value restriction of F#

In F#, we can declare a polymorphic value

> let a = [];; 

val a : 'a list

However, if we make it mutable, fsharpi complains with value restriction error

> let mutable a = [];;

  let mutable a = [];;
  ------------^

/Users/kseo/stdin(1,13): error FS0030: Value restriction. The value 'a' has been inferred to have generic type
    val mutable a : '_a list    
Either define 'a' as a simple data term, make it a function with explicit arguments or, if you do not intend for it to be generic, add a type annotation.
> let a = [];; 

val a : 'a list

This looks unreasonable at first! But let’s see what happens if we get rid of this restriction.

let mutable a = []
let f x = a <- (x :: a)

f(1);;
f(true);;
f(“Hello World”);;

The type of function f is ‘a -> unit. Hence f(1), f(true) and f(“Hello World”) type check. However, a ends up having three different types [“Hello World”; true; 1]. Oops! So, the type system of F# has a rule called value restriction to prevent this kind of bad behaviour.

In fact, all ML family languages have value restriction. See Notes on SML97’s Value Restriction for further information.

Emulating Haskell type classes in F#

One language feature I like most in Haskell is type class. It was originally conceived as a way of implementing overloaded arithmetic and equality operators. It is a clever trick to support ad-hoc polymorphism, which does not require extensive modifications of the compiler or the type system.

F# does not provide type class, but we can emulate it with other F# language features such as operator overloading and inline function. Type Classes for F# shows this trick. Here’s the Functor example taken from the blog:

type Fmap = Fmap with
    static member ($) (Fmap, x:option<_>) = fun f -> Option.map f x
    static member ($) (Fmap, x:list<_>  ) = fun f -> List.map   f x
let inline fmap f x = Fmap $ x <| f

Here, fmap function must be inline because inline functions can have statically resolved type parameters. Without the inline modifier, type inference forces the function to take a specific type. In this case, the compiler can’t decide between option and list and emits an error.

You can use it as in the following:

> fmap ((+) 2) [1;2;3] ;;
val it : int list = [3; 4; 5]
> fmap ((+) 2) (Some 3) ;;
val it : int option = Some 5

I transliterated the TreeRec example of Simon Thompson’s paper, Higher-order + Polymorphic = Reusable into F# by emulating type class in this way.

type Tree<'a> =
    | Leaf
    | Node of 'a * Tree<'a> * Tree<'a>

type LeafClass = LeafClass with
    static member ($) (LeafClass, t:'a list)  = []
    static member ($) (LeafClass, t:Tree<'a>) = Leaf
let inline leaf () : ^R = (LeafClass $ Unchecked.defaultof< ^R> )

type NodeClass = NodeClass with
    static member ($) (NodeClass, l1:'a list)  = fun a l2 -> List.concat [l1; [a]; l2]
    static member ($) (NodeClass, t1:Tree<'a>) = fun a t2 -> Node(a, t1, t2)
let inline node a x1 x2 = (NodeClass $ x1) a x2

type TreeRecClass = TreeRecClass with
    static member ($) (TreeRecClass, l:'a list) = fun f st ->
        let listToTree = function
            | [] -> failwith "listToTree"
            | a::x ->
                let n = List.length x / 2
                let l1 = Seq.take n x |> Seq.toList
                let l2 = Seq.skip n x |> Seq.toList
                (a, l1, l2)
        let rec treeRec' = function
            | [] -> st
            | l ->
                let a, t1, t2 = listToTree l
                let v1 = treeRec' t1
                let v2 = treeRec' t2
                f v1 v2 a t1 t2
        treeRec' l
    static member ($) (TreeRecClass, t:Tree<'a>) = fun f st ->
        let rec treeRec' f st = function
            | Leaf -> st
            | Node(a, t1, t2) -> f (treeRec' f st t1) (treeRec' f st t2) a t1 t2
        treeRec' f st t
let inline treeRec f st x = (TreeRecClass $ x) f st

let inline tSort x =
     // FIXME: Implement sorting!
    let mVal sort1 sort2 v = List.concat [sort1; sort2; [v]]
    let mergeVal sort1 sort2 v t1 t2 = mVal sort1 sort2 v
    treeRec mergeVal [] x

One problem with this approach is that we no longer can group related operations together into a single class. It can’t express that Tree-like type t* has three operations: leaf, node and treeRec. We end up having three distinct types LeafClass, NodeClass and TreeRecClass.

Scala Option.fold vs Option.map/getOrElse

Scala Option offers two different ways to handle an Option value.

Option.map/getOrElse

val name: Option[String] = request getParameter "name"
name map { _.toUpperCase } getOrElse ""

Option.fold

val name: Option[String] = request getParameter "name"
name.fold("") { _.toUpperCase }

On the spark-dev mailing list, there was a discussion on using Option.fold instead of Option.map/getOrElse combination.

Two idioms look almost the same, but people seem to prefer one over the other for readability reasons. Here is the summary of the discussion:

  • Option.getOrElse/map is a more idiomatic Scala code because Option.fold was only introduced in Scala 2.10.
  • Fold on Option is not obvious to most developers.
  • Option.fold is not readable.
    • Reverses the order of Some vs None.
    • Putting the default condition first there makes it not as intuitive.
    • When code gets long, the lack of an obvious boundary with two closures is confusing. (“} {” compared to getOrElse)
  • Fold is a more functional idiom in general.

It seems people are getting used to functional idioms such as map and filter, but still are reluctant to accept more functional idioms such as Option.fold.

I prefer Option.getOrElse/map because I think putting the default value first is not intuitive and much of Scala code is already written with Option.getOrElse/map. However, both options are fine as long as only one style is used through the project. Consistency is more important than taste!