Awesome list in rescript

Prerequisite:

• Basic understanding of functional programming.
• Basic knowledge on rescript.

If you have already used or tried Rescript, then you should be already familiar with list{} in rescript. list{} is powerful but may cause performance issues if you don't understand how list{} works exactly. So lets try to understand it by creating our own list.

Lets first define the type.

type rec mylist<'a> = Nil | Cons('a, mylist<'a>)

mylist is a variant type with 2 type constructors, Nil and Cons. It also takes a generic type argument 'a, so that we can store any homogenous type (elements of same type) in our mylist.

Nil represents an empty mylist. Cons('a, mylist<'a>) takes two arguments 'a is the head, representing the current value and mylist<'a> is the tail, representing the following mylist. Now inserting multiple values into the list would look like below.

let data = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))

The above code creates mylist data with type 'a' as int and values 1, 2, 3, 4. As you can see the Nil type constructor denotes an empty list which inturn means that this is the end of the mylist.

One awesome, cool thing about our mylist is, we can create an infinite list very easily. Lets create one.

let rec cycle = Cons(1, cycle)

Look at the rec keyword after the let keyword. This rec says to the compiler that there is a recursive reference in the declaration. The above code compiles without any error. The tail of the above mylist is nothing but itself. So this actually refers to something like below.

Cons(1, Cons(1, Cons(1, Cons(1, Cons(1, Cons(1, Cons(1, .....)))))))

Since the tail is only a reference, there will not be an infinite loop or errors when you run the above code. So the tail always contains a mylist with head value as 1. You could ask, where could this be useful? This could be useful in cases where we want a set of values to be returned in a cyclic way.

let rec cycle = Cons(1, Cons(2, Cons(3, Cons(4, cycle))))

The above cycle will cycle through the values 1, 2, 3, 4, 1, 2, 3, ... each time you access the head upon its tail. Lets try to write the above cycle using the list{} in rescript.

let rec cycleList = list{1, 2, 3, 4, ...cycleList}

This is same as the above cycle. Here, it is easy to mistake the spread operator as something that is eagerly evaluated, but it is not. ...cycleList just places the same list at tail position. That is the reason why you cannot do things like below.

// CANNOT do this
let rec cycleList = list{...cycleList, 1, 2, 3, 4}

Here you are trying to place the list in the head position, while you can only place it in the tail position.

// CANNOT do this
let rec cycleList = list{...cycleList, ...cycleList}

Here you are trying to place the list in the head position as well as in the tail position, while you can only place it in the tail position.

list{} in rescript exactly works like the mylist that we created and are nothing but just a syntactic sugar. To access any i^th element in mylist we have to iterate from head until the i^th element. That is why the Rescript documentation says that list{} is fast at prepending items and getting the tail value but slow at everything else.

Hope you enjoyed! Happy Hacking!