lc core functions
npm install lesscode-fpGoing back in time, when Alan Turing built
the Turing machine to perform computation, Alanzo Chruch designed
Lambda Calculus to mathematically compute anything by composing lambda functions (world's smallest programming language).
The soon world flooded with programming languages in both paradigms and many languages start borrowing each other's concepts (sounds familiar?) only to become bloated and unmanageable.
Fast forward, 1977, John Bakus's paper, "Can programming be liberated from Von Neumann style?" put it very rightly.
The above article influenced me to dive deep into programming paradigm concepts, mostly functional programming, and understand it from the work of those two greats.
So begin the journey of Functional Thinking, with few straightforward goals in mind :
- Seek a deep understanding of the functional programming's motivation and concepts, without being caught in the programming languages nuances/jargon, syntax, or even nomenclature.
- Come up with a language-agnostic list of real-world functions (library), and implement it in a multi-paradigm language that supports functional programming.
This repo is about my learning of functional programming and coming up with a language-agnostic library of functions, which
can be applied to solve many real-world problems. I will also compare it to object-oriented (imperative) programming, where the difference is significant.
In functional programming :
- Data is immutable. You compute a new value using pure/impure functions.
- Functions are pure (no side-effects)) but you are allowed to write impure functions.
- Solutions are composed using functions.
----
lesscode-fp, is a language agnostic javascript functional library, which define and implement functions to compose both pure and impure functions along with the functions to manipulate & transform String, List & Map / Object categories.
You can implement these functions in any multi-paradigm language that supports functional programming.
``
// to install and play with javascript library
yarn add lesscode-fp
//or
npm install lesscode-fp
`
It is still an experimental library, so use at your discretion.
---
Object-oriented programming thrives in broader categorization of complexities (using multiple classes), functional programming thrives in generalization of complexities into few categories.
---
Pure functions have no side-effects, are time-independent & maintain referential transparency, which means, for a given input, you can replace the function with its output, anytime.
Think of them as a mathematical function, which will always return the same output for a given input.
It also means a pure function can easily cache (memoize) the value it returns after the execution.
Lesscode library functions are pure unless they are not. Pure functions are named starting with lowercase; uppercase for impure.
`
// appends String to another String and returns a new String
const sappend = str1 => str2 => str1 + str2
// checks if a value is null or not?
const eqNull = val => (val == null || undefined) ? true : false
// Find the max of 2 munmers
const max = a => b => Math.max(a,b)
`
In functional programming, you do not mutate data; instead, you compute a new.
Now that memory/storage is cheap, this is one of the major advantages of functional programming.
Lesscode adheres to the principle unless it's a Monad (see below)
`
// appends String to another String and returns a new String
const sappend = str1 => str2 => str1 + str2
The origin of functional programming, lambda calculus, only allowed single input/ output. While it may not seem practical, currying (see below) allows you to do so. Functional programming treats functions as a 1st class citizen, so you can pass and return a function to/from another function.
Also, single input/output makes function composition (see below) trivial.
Lesscode functions accept a single parameter (whereever possible); multi-parameter functions are curried.
`
// reverses a List, point-free (see Data-Last).
// same as : lreverse => lst => lfold(([])(lappend)(lst)
const lreverse => lfold(([])(lappend)
// sappend takes a String as 1st parameter and using currying ,
// returns a function that takes another String as a parameter
// sappend = str1 => ( (str2) => str1 + str2 )
const sappend = str1 => str2 => str1 + str2
`
Currying (f(a, b) => f(a)(b)), allows function with multiple parameters to be written as sequence of functions that each take a single parameter.
Currying allows you to partially apply other options (initialization) and dependencies (injection) on multi-parameter functions.
Currying also allows you to create domain-specific language (DSL) by partially applying many generic functions.
So, if you are writing a multi-parameter function, please curry it.
Every function in lesscode library is curried and point-free (where possible).
`
// it splits a String into List based on pattern matching.
// s2List is a curried function.
const s2List = ptrn => str => str.split(ptrn)
// suppose your domain breaks Sting into List based on space.
// partially apply s2List, with space, and create a new function.
const space2List = s2List(space)
// will break String into List on every whitespace.
space2List('This is cool') // ['This','is','cool']
`
In FP, data and functions are separate; hence you build a library of functions to work with your data.
Data last principle makes function composition, easier (builder pattern). Also, it allows for a point-free style of writing functions.
All the functions in lesscode library accept data as the last parameter.
`
// takes List as the last parameter
const l2String = sep => lst => lst.join(sep)
// coverts List of Strings to uppercase; point free
twoUpper = lmap(suppercase)
`
In functional programming there is no assignment, you just compose functions to produce more specific functions/ solutions.
Functional programming language like Haskell has infix composition operator like '.' (for pure function) and '>>= / >>' (for monadic composition). Other multi-paradigm languages like javascript, java, etc do not have any such operators nor they support infix styling.
Lesscode library provides :
- $(...) for pure function composition.
- $M(...) for monadic composition.
- $E(...) for applicative composition.
- $3(...) for stream composition.
`
/**
Coconut machine will take List of coconuts, then slice the top & put a straw.
coconutMachine = DropStraw . SliceFromTop
**/
const coconutMachine = $(DropStraw ,SliceFromTop)
// to copy the content of one file to another (point-free)
const FileCopy = to => $M(FileWrite(utf8)(to), FileRead(utf8))
`
'$' has a tiny footprint and can be easily spotted to show the composition.
While primitive data-types like numbers, characters, bytes are great for mathematical functions, real-world functions require complex
data-types like strings / lists / maps of something.
Lesscode library provides functions to manipulate/transform the following categories: String, List, Map / Object (non-mutable).
These categories are quite popular in many programming languages.
List allows easier work distribution; Map / Object allows faster retrieval; String is a preferred way of storing data.
Lesscode library prefixes the 1st letter of the category (s, l, m) for all the category-specific functions.
This design is by choice. It allows you to spot which category a function belongs easily.
`
// slices String at the specified position
const sslice = start => end => str => str.slice(start,end)
// converts String to List, by breaking it with supplied pattern
const s2List = ptrn => str => str.split(ptrn)
`Morphism
In category theory, the Functor is a structure-preserving transformation from one category to another. Since Functor always produces another functor, the composition is trivial.
E.g., transforming List of lowercase text to List of uppercase, transforming List of Strings to List of Hash of Strings.
Lesscode library implements 'lmap' for List functor.
Using lmap, you can transform one List into another. lmap essentially lifts each item from the List, apply the function, then puts back the result into the new List.
`
// Map over List to tranform into another List,
// while preserving the structure (Functor - borrowed from category theory).
const lmap = func => lst => lst.map(func)
// convert the List of Strings to uppercase
const str = ['neelesh' , 'vaikhary']
const strUpper = lmap(supper)(str)
print(strUpper) // ['NEELESH' , 'VAIKHARY']
// Applying the cocununt machine logic to slice & straw, list of coconuts
const readyCoconut = lmap($(DropStraw ,SliceFromTop))
// ['strawed sliced coconut', 'strawed sliced coconut']
print(readyCoconut['full coconut', 'full coconut'])
`
Lesscode library provides lfold for List catamorphism.
- lfold - folds left to right
- lfoldr - folds right to left
`
// ['1','2','3','4'] => 1234
list2String = lfold([])(sum)
Lesscode provides many built-in catamorphisms :
`
- s2String // '12' => [1,2]
- l2String, // [1,2,3] => '12'
- l2countMap (histogram), // [1,1,3] => { '1' : , '3' : 0}
- l2indexMap, // [1,1,3] => { '1' : [0,1]. '3' : 2}
- m2List // { '1' : [0,1]. '3' : 2} => [[0,1][1,1][2,3]]
- m2valList, // { '1' : [0,1]. '3' : 2} => [[0,1],[2]]
- m2keyList // { '1' : [0,1]. '3' : 2} => [1,3]Side-effects
Monads, let you do all that. Monads let you write functions that can separate concerns (decorator pattern), allow side effects (IO), introduce sequence, hide complexity.
Think of Monad as a function that wraps all the side effects and makes it a pure and allow composition by passing the value from one to another. In category
theory jargon, Monads are just a Monoid) (Category with a single element that can join).
Monad is just a monoid in the category of endofunctors - Saunders Mac Lane
Lesscode provides some built-in Monads using javascript async (promise).
$M(...) supports monadic composition (instead of a >==> operator or kliesli arrow , as it's called in category theory).
$ indicates composition, M denotes Monad, or sequence.
`
// Read the content of a file.
const FileRead = option => name => fs.promises.readFile(name, option);
// mondaic composition : copy the content of one file to another (point-free)
const FileCopy = to => $M(FileWrite(utf8)(to), FileRead(utf8))
`
Lesscode implements applicative composition using $E(...) and accept Primitive / Object / List as a parameter.
If the parameter is a List, all the functions are concurrently applied to all the items to produce another List.
$ indicates composition, and E denotes concurrency.
`
// apply max, min concurrently to the list of two numbers
$E(sum(3), sum(2))([1,2,4]).then(Print) // [ 3, 4, 6, 4, 5, 7 ]
// make 2 Http call concurrently and return the result as a List
$E(HttpGET())(['https://www.google.com','https://www.yahoo.com']).then(Print)
`
Lesscode implements stream as $3. $ means it's still a composition, but 3 denotes that its arity is 3, i.e., it accepts 3 parameters (out-stream, function, instream)
Algorithms span many domains, and hence it becomes tricky to provide a single generic library.
Lesscode library provides generic functions to solve many such coding problems.
Given an array of integers nums and an integer target, return indices of the two numbers add up to the target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
examples
`
nums = [2,7,11,15], target = 9 => [0,1]
nums = [3,3], target = 6 => [0,1]
Solution
`
/**
* Logic is very self-explanatory :
* 1. Transform List to another List by subracting it from the target : lmap(sub)
* 2. Join the 2 List to obtain matching indices : ljoinIndex
* 3. Remove dupes - [[1,2], [2,1]] => [[1,2]] : lcollapse
* 4. Discard self - [[0,0]] => []
**/
const {
$M,
sub,
eqNot,
comma, s2List,
lcollapse, llift2, lmap, lflat, lfilter, ljoinIndex,
Print,
} = require('lesscode-fp')
const target = process.argv[3]
const nums = s2List(comma)(process.argv[2].slice(1,-1))
// [3,3] / 6 => [[1,1]]
const twoSum = nums => target => {
// Remove self : [ [ 0, 0 ], [ 1, 2 ], [ 2, 1 ] ] => [ [ 1, 2 ], [ 2, 1 ] ]
const ldropSelf = lfilter(llift2(eqNot))
// Transform List to sublist with subtraction
const subList = lmap(sub(target))(nums)
return $(ldropSelf, lcollapse, ljoinIndex(subList))(nums)
}
`
The above solution will work for more than one too.
This is the beauty of functional programming. Once you build a domain-specific library, it is all about simple composing.
Instead of 2 numbers, if we ask for the sum of 3 numbers to be equal to the target, the above code can be easily extended to find the 3sum.
`
/**
* Logic is very self-explanatory:
* 1. Making every item in the List as target find 2sum that satisfy the criteria for 3sum
**/
const threeSum = nums => target =>{
// [[ 3, 3, 5 ]] => []
const ldropSelf = lfilter(llift3( a => b => c => a != b && a != c && b != c))
const all2Sum = lfoldA()(cat => index => val => $(lappend(cat),lmap(lappend([index])),twoSum(nums))(val))
return $(Print, ldropSelf, lcollapse, all2Sum,lmap(sub(target)))(nums)
}
`
Many of the real-world problems involve :
- processing data sequentially / concurrently.
- processing synchronously / asynchronously.
- processing bulk / continuous stream of data.
input.txt
`
writing less-code is cool...
output.txt
`
writing less-code is cool...
`
const {
suppercase,
$M, // Composition
FileRead, FileWrite, // IO Monad
} = require('lesscode-fp')
const In = process.argv[2]
const Out = process.argv[3]
$M(FileWrite(utf8)(Out), suppercase, FileRead(utf8))(In)
`
Doing things concurrently, also tolerating failures instead of aborting on error (if a file download fails, it is ok, write the error).
Download the List of images specified in a file and write metadata(URL, size, hash) to the specified output file.
input.txt
`
http://i.imgur.com/c2z0yhtx.jpg
http://i.imgur.com/KxyEGOn.jpg
http://i.imgur.com/vPae8qL.jpg
http://i.imgur.com/cz0yhtx.jpg
output.txt
`
http://i.imgur.com/c2z0yhtx.jpg 0 Error%3A%20Request%20failed%20with%20status%20code%20404
http://i.imgur.com/KxyEGOn.jpg 470489 cc042826ed386d4247aca63cb7aff54b37acb1f89ce8f4549ac96a9e8683360c
http://i.imgur.com/vPae8qL.jpg 69085 bde0a62bb35dffe66cebf6cfd9ca3841ca1419fb323281bd67c86145f2173207
http://i.imgur.com/cz0yhtx.jpg 2464218 ed9f8c1e95d58e02fcf576f64ec064a64bc628852bc3b298cda15f3e47dfe251
`
// Lesscode-fp
const {
linebreak, utf8, newline, // Strings
hash, // math
l2String, s2List, // List
mget, mgettwo, // Map
$M, $E, // Composition
Print, // Monad
FileRead, FileWrite, // IO Monad
HttpGET // IO Monad
} = require('lesscode-fp')
const LogData = name => async data => ${name} ${mgettwo('headers')('content-length')} ${hash('sha256')(mget('data'))}
const LogErorr = name => async err =>
// processURL :: String -> String
const ProcessURL = name => $M(LogData(name), HttpGET())(name).catch(LogErorr(name))
const In = process.argv[2]
const Out = process.argv[3]
// Main pipeline. Classic mix of sequence ($M - monad) & concurrency ( $E - applicative)
$M(FileWrite(utf8)(Out),l2String(newline), $E(ProcessURL), s2List(linebreak), FileRead(utf8))(In).catch(Print)
`$3
Sometimes, the input is a continuous stream of data, which needs to be processed forever.
Stream content of a text file, convert to uppercase, then write back to another stream (output file).
input.txt (the real file may be enormous)
`
this text is all lowercase. please turn it into to uppercase.
output.txt
`
THIS TEXT IS ALL LOWERCASE. PLEASE TURN IT INTO TO UPPERCASE.
`
const {
utf8,
suppercase,
$3,
FileStreamIn, FileStreamOut
} = require('lesscode-fp')
const is = FileStreamIn(utf8)(process.argv[2])
const os = FileStreamOut(utf8)(process.argv[3])
/**
Streaming pipeline.
A classic example of doing pure function composition inside two im-pure (Monads),
which also happens to be the stream.
Stream also allows monadic composition, since it converts pure to moand, internally.
**/
$3(os)(suppercase)(is)
``