- Parses a string representation of a grid into the program.
- Serializes a grid from the program into a string representation.
- Determines whether the digits in a grid are valid according to the constraints of the game.
- Fills every empty cells with their candidates.
- Solves a grid using a backtracking algorithm:
- Indicates the cells that can be solved:
- Indicates the candidates that can be eliminated:
- Chains and Loops
- Wings (XY-Wing, XYZ-Wing, WXYZ-Wing and W-Wing)
This program is used as a sandbox to try functional programming (FP) in TypeScript.
What is it?
FP is a programming paradigm in which the flow of the program is passed into pure functions instead of relying on objects like in object-oriented programming (OOP, which is a paradigm opposed to FP). The main motivation is to make the code easier to understand, more predictable, and well tested. In order to satisfy these goals, FP defines some concepts to eliminate any possible side effects.
How does it work?
FP relies on several concepts that aim to enforce building a software by describing what to do, using a structure and elements that expresses the logic of a computation, instead of how to do it with algorithms detailing explicitly every step. It is said to be declarative because it abstracts the flow control (how things are done) to focus on the data flow.
- The first and probably most important elements are the pure functions. A pure function returns always the same
result for the data that was pased to it as arguments, it doesn't rely on data outside of its scope and it doesn't
change the state of any variable or mutable references (objects and arrays). These properties make it really to use
unit testing with these functions, and ensure the caller that it will
always get the right result no matter what happend before and the current state of the program.// This is an impure function:;// This is the proper way to do it with a pure function:
- Speaking of state, it is important for the program to avoid changing
the value of its variables and for its data to be immutable (their
state cannot be modified after being created). To ensure that, every variable must be declared as constant and all
the mutable data (objects and arrays for instance) need to be readonly. Moreover, the state must stay in its local
context and never be shared to other parts of the program.// This variable is not constant and can change unexpectedly;// This is a constant so we know that it will keep the same state;// The data in this array and object can easily be modified when it is passed into a function;;// With TypeScript it is possible to ensure that their data never change;;
- Another difference of FP is the use of expressions
instead of statements. A statement is an element in
the program that is executed and that does not return a result (e.g. assigning a value to a variable, checking a
condition with an
switch, repeating an action inside a
whileloop); whereas an expression is an element that is evaluated to determine a value that it must return to the caller (using only constants, functions and operators). Therefore, in FP, we need to use specific functions to replace statements (e.g. we can loop through an array with
filterto reject some of the elements, apply
reduceto aggregate some results, etc.).// These are example of statemens:;for ; i < 10; i++// Instead we must use expressions:.keys.filteri % 2 === 0.mapi * 2;
- Function composition is a mechanism that
combines several simple general functions into a more specialized complicated one.// Composition of functions (evaluates functions from right to left in the argument list)// Describe simple general functions// Compose a specific function;isDivisionEven4; // Equivalent to isEven(divideBy2(4)) => divideBy2(4) = 2 => isEven(2) => true// => trueisDivisionEven10; // Equivalent to isEven(divideBy2(10)) => divideBy2(10) = 5 => isEven(5) => false// => false
- Other rules apply for FP, like currying or monads, but the one listed above are the most important to begin with.
In this project we ensure to comply with these rules as much as possible with the use of some external libraries:
TypeScriptis used to avoid making typing errors.
eslint-plugin-functionalis a set of rules that analyzes the code in order to detect violations of FP principles, these rules can be categorized like this: no mutation, no object-orientation, no statements, no exceptions and require currying.
ramdais a library that allows to evaluate data without the use of statements or mutations, in a pure functional approach. The
remedalibrary is quite similar but with a focus on performance through lazy evaluation (that is not supported by ramda yet).
Why bothering with this?
FP is difficult to learn for a beginner as the declarative approach is quite the opposite from what we learn with imperative programs (like in OOP). Moreover, FP does not make a program more performant, it is probably the opposite as it is better to use standard (imperative) mechanisms in order to optimise every step of the program. Also, the constraints of FP also makes it often harder to describe the logic using a chain of general expressions rather than simply detailing each step with straightforward statements.
So why using FP for this project?
FP is growing in popularity as we can see with the usage of the Redux library that allows to manage the state of web applications in a FP style (without doing mutations). Its goals are to behave consistently and to be easy to test. In fact, a lot of softwares are using some of the FP principles to avoid some flaws encountered with other approaches:
- Difficulty to spot an error when it is caused by an unpredictable side effect, that can sometime be hidden deeper in the control flow.
- Using data that is shared among several parts of the systems, all of which being able to modify it in parallel.
- The increasing use of mocks, stubs, spies, dummies and other isolation mechanisms in unit frameworks for systems that are too dependent on the state of other parts of the program.
This project is using FP in order to avoid these errors but most importantly it is a sandbox to evaluate the feasbility of building a software with complex pattern-recognition logics with all of these constraints, and to understand the advantages and limitations.