The title seems a little weird, looks like a typo, but there is a pun intended in here. The “Trie” in “Trieng“ stands for the Trie data-structure and in this blog post we’ll explore the world of ReasonML by taking an example of a Trie and implement a React app in ReasonReact.
I wrote this post to serve as a good introduction to ReasonML and the Trie data structure that I have been playing around with the last couple of months.
What is ReasonML?
Reason or ReasonML is not a new language; it is a new syntax which is powered by OCaml (a battle-tested functional programming language from 1996) ecosystem. The ReasonML code that we write can be compiled to JavaScript which can be run in the Browser and Node.js using BuckleScript compiler. BuckleScript is used to compile ReasonML/OCaml code to JavaScript.
Reason’s creator also created ReactJS, whose first prototypes were written in SML, a distant cousin of OCaml.
What does this have to do with Functional Programming?
Functional Programming is paradigm in programming in which the focus is on transforming data by applying functions. Functions can be thought of as computation that maps input of a particular type/structure to output of a different type/structure.
Functional programming works on principles like Immutability, Scopes & Closures, Recursion, programming without side-effects. Side-Effect means when a function changes a value other than its input parameter. Example of side-effect is mutating the state of global variables from a function. Mutating data is a taboo in functional programming.
Functional Programming Languages can be loosely classified into 2 family of languages
- LISP family
- ML family
LISP family languages:
LISP family languages are dynamically typed, the syntax of these languages contain a lot of parenthesis.
The popular LISP dialects in use these days are Clojure, Common Lisp and Scheme. LISP uses a special kind of syntax called S-expressions and prefix notations. One of the good books to learn about LISP is the SICP (Structure and Interpretation of Computer Programs).
ML family languages:
ML family of languages are statically strongly/gradually typed, they make of Hindley-Milner type system. The H-M type system allows the compiler to make type inferences when types are not explicitly provided in the code. The ML family languages have some great features like pattern-matching, currying. Popular languages from the ML family are Haskell, OCaml, SML(Standard ML), F#. ReasonML belongs to the ML family of languages and also provides us a syntax to do imperative programming when we can’t think of a functional implementation (Yes, ReasonML allows mutations, for and while loops).
What is a Data Structure ?
A data structure can be thought of as an API which allows certain operations and guarantees some time and space complexity for these operations.For example a Set data structure can be implemented using a HashTable or a HashMap as long as we are able to guarantee uniqueness of values and find values in O(1) we are good to go.
Trie is also called a prefix tree because we store prefixes in a tree like structure. Trie is a multi-way tree data-structure i.e. one node can have multiple children.
Lets take an example of searching through a list of words/sentences (strings). This can be implemented naively using an array or a list, But for fast prefix lookup we can use Trie.
| NAIVE IMPLEMENTATION | TIME COMPLEXITY | SPACE COMPLEXITY |
|---|---|---|
| Insert | O(1) | O(n*m) n-number of strings m-length of string |
| Delete | O(n*m) + O(n) NA find + delete from list | NA |
| Find | O(n*m) | NA |
| Find All Prefix | O(n*m) n – number of strings m – length of prefix | NA |
| TRIE IMPLEMENTATION | TIME COMPLEXITY | SPACE COMPLEXITY |
|---|---|---|
| Insert | O(n) | O(n*m) n-number of strings m-length of string |
| Delete | O(m) | NA |
| Find | O(m) | NA |
| Find All Prefix | O(n) + O(m) n – number of strings m – length of prefix | NA |
So, Trie is faster than a list implementation for this problem. Only downside is: Trie takes more space in memory as it stores data in the form of nodes, node takes up more memory than a character. Also strings are stored as a sequence of characters in adjacent memory locations, so they can take advantage of hardware cache while lookups for memory locations (In case of a Trie there is a high chance of cache miss while memory location lookups).
Enough with the theory let’s get started with some code.
I have implemented the Trie data-structure in ReasonML and used this data-structure to build a demo of filtering through a list of strings in ReasonReact (React library implemented in ReasonML).
You can checkout the code here: https://github.com/melwyn95/Trie-ReasonML/blob/master/src/Trie.re
You can play around with the demo here: https://melwyn95.github.io/Trie-ReasonML/
The Trie node and operations have the following signatures:
Type Signatures for Trie Node and operations
ReasonML language features
- ReasonML’s type system and compiler:
ReasonML’s type system is complete and “sound”. The type coverage is always 100% Types can be inferred by the compiler. The type system deduces the types for you even if you don’t manually write them down.
- Record types:
You can define your own types in ReasonML like this
type person = {
age: int,
name: string,
};
Records in ReasonML are like JavaScript objects but are
- Lighter
- Immutable by default
- Fixed in field names and types
- Very fast
- A bit more rigidly typed
- Variant types:
Variant Type
In functional programming there is a concept of polymorphic types which are known by many names like enums, sum types, algebraic data-types.
This type allows us to define multiple specific constructors of a type, in the above example the type action has 3 constructors – these are used to define operations taking place on the front-end. When the page is initialised we dispatch an action of type Init. when we search something in the list the action type Search is dispatched. When we want to add something to the trie we dispatch Add.
For more about variant types refer: https://reasonml.github.io/docs/en/variant
- Destructuring and Pattern Matching:
Destructuring is a syntax through which we can extract fields from a data-structure without using the dot operator. It is a visually concise way of extracting fields.
Example:
type person = { name: string, age: int };
let somePerson = { name: 'Guy', age: 30 };
let { name, age } = somePerson;
Pattern Matching
Pattern Matching is like destructuring but it works with variant types. It is used with the switch expression, It forces you to handle all the cases for a variant type. In the example above the findPrefixRoot function returns a option type of node, if the prefix is found in the trie it return Some(node) else it return None
Option type is special variant type provided in the ReasonML standard library it has type definition
type option(‘a) = Some(‘a) | None;
Here ‘a is like a generic, it is replaced by the type we specify.
So, In the example above we have to handle both the cases for the option type returned by the findPrefixRoot function. If None is returned means there is no node in the Trie that matches the specified prefix, so we return an empty list ([]). If Some(prefixRoot) is returned we need to find all the words starting from the prefix root.
- Currying and Partial Applications of functions:
Currying is nice feature that functional languages provide, in simple words currying is, unless a function is provided with all the arguments needed by the function, the function is not executed, but it returns intermediate functions to which we can pass additional parameters/argument.
All the functions in ReasonML are auto curried.
And the process of creating intermediate functions from a curried function is called partial application.
Example:
let add = (x, y) => x + y; let addFive = add(5); let eleven = addFive(6); let twelve = addFive(7);
Here add is a function which is auto curried, and we create a new function called addFive by partially applying 5 as a parameter to add. Then when we call addFive with parameters 6 & 7 we get 11 & 12 respectively.
Internally add is represented as:
let add = x => y => x + y;
- Mutation in ReasonML:
Mutation is generally discouraged in functional programming but sometimes it is helpful to optimize the performance.
ReasonML provides us mutative programming capabilities through ref()
Mutation using ref()
let bindings are immutable, but you can wrap it with a ref, which is like a box whose content can change.
In the above example I have wrapped list in a ref, to mutate the value of list we have to use := operator, and to access the value inside the ref, we use ^ operator.
The listAllWords function could have been written in a functional way, but I wrote it using mutation just to explore the concept.
Bonus: Making API call in Reason-React
API call using Fetch
For working with API calls and JSON we need to use BuckleScript libraries like bs-fetch and bs-json.
I used references from stack overflow and ReasonML forums to make the above code work, and I don’t completely understand how the above code works, but it works.
It also reminds me that I’m not done learning ReasonML, there is lots of stuff that is to be learnt and understood.
I hope this blog-post inspires you to learn ReasonML and ReasonReact.
If you have made it this far, thanks for reading and !!!Happy Hacking!!!
References / Resources:
- You can start by watching this video – it is 5 ½ hours long, but it will cover all the basic stuff in order to get started with ReasonML
- The Official Documentation of ReasonML is really helpful when dealing with modules, Functors and Promises.
- For ReasonReact refer the official site. It has the commands in order to get started with a demo project, the demo project has nice examples to get started.
- Finally, one last resource Online Book on ReasonML by Dr. Axel Rauschmayer, It covers all the basic concepts and touches upon some advanced concepts.
