# 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);
```

# 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));

}
```

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));
});

}
```

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.
• 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!

# Functions are Objects in Scala

Scala is a multi-paradigm language which supports both object-oriented programming and functional programming. So Scala has both functions and objects. But in the implementation level, function values are treated as objects. The function type A => B is just an abbreviation for the class scala.Function1[A, B],

```package scala
trait Function1[A, B] {
def apply(x: A): B
}
```

There are traits Function2, …, Function22 for functions which take more arguments.

An anonymous function such as (x: Int) => x * x is expanded to

```new Function1[Int, Int] {
def apply(x: Int) = x * x
}
```

A function call such as f(a, b) is expanded to f.apply(a, b).

So the translation of

```val f = (x: Int) => x * x
f(7)
```

would be

```val f = new Function1[Int, Int] {
def apply(x: Int) = x * x
}
f.apply(7)
```

This trick is necessary because JVM does not allow passing or returning functions as values. So to overcome the limitation of JVM (lack of higher order functions), Scala compiler wraps function values in objects.

The following method f is not itself a function value.

```def f(x: Int): Boolean = ...
```

But when f is used in a place where a Function type is expected, it is converted automatically to the function value

```(x: Int) => f(x)
```

This is an example of eta expansion.

The code examples in this article are taken from Martin Odersky’s Functional Programming Principles in Scala lecture.

# Classes and Substitutions in Scala

In functional programming, it is conventional to define the meaning of a function application using a computation model based on substitution. In Scala, the meaning of classes and objects are also defined using substitution model. Let’s assume that we have a class definition,

class C(x1; …; xm){ … def f(y1; …; yn) = b … }

• The formal parameters of the class are x1; …; xm.
• The class deﬁnes a method f with formal parameters y1; …; yn.

Then, the expression new C(v1; …; vm).f(w1; …; wn) is rewritten to

[w1/y1; …; wn/yn][v1/x1; …; vm/xm][new C(v1; …; vm)/this]b

• the substitution of the formal parameters y1; …; yn of the function f by the arguments w1; …; wn,
• the substitution of the formal parameters x1; …; xm of the class C by the class arguments v1; …; vm,
• the substitution of the self reference this by the value of the object new C(v1; …; vn)

Martin Odersky explained the evaluation of Scala classes and objects using this model in his lecture, Functional Programming Principles in Scala.