Functional Programming Notes

ProfessorFrisbyIntroducesComposableFunctionalJavaScript.md

A box (or discriminated union) is just a context in which to apply functions.

.map(f) is really not about traversal, but rather applying a function or transformation within a context (of a box).

.fold(f, ...) is similar to map, except the return value is unboxed.

• Formally, folding is the application of a combining function to reduce a structure or collection to a single value.
• For boxes like Either, fold usually takes multiple functions, one to apply to each type of the union.

.chain(f) is similar to .map(f), but it should be used when f returns a box instead of a raw value. That way, the result of the function will be a box(a) instead of a box(box(a)).

A semigroup is a box that has a .concat() method so that its enclosed value may be concated.

• The laws of associativity apply: a.concat(b).concat(c) === a.concat(b.concat(c)).
• The actual implementation of concat may vary. + and && are two examples.
• If a structure's members are all semigroups, then the structure is also a semigroup.
• The concat method need not apply to all types in the union. For example, folktale's Validation.Failure concats but Validation.Success is the identity.
• See http://mathworld.wolfram.com/Semigroup.html.

A monoid is a semigroup with an identity element, often named empty. See http://mathworld.wolfram.com/Monoid.html.

• The identity element ensures failsafe concatenation: ''.concat('something').

.foldMap() is a shortcut for a map and then a fold with an initial value:

List.of(1,2,3)
.map(Sum)  // where Sum is a semigroup
.fold(Sum.empty())
// => Sum(6)

// becomes

List.of(1,2,3)
.foldMap(Sum, Sum.empty())
// => Sum(6)

A functor is a box with .map() that obeys these laws:

• Preserves function composition: box.map(f).map(g) === box.map(f(g(x)).
• Identity box.map(id) === id(box).

A monad is a box with .of() and .chain() (which is also known as .flatMap(), .bind(), and >>=.

An applicative functor uses the .ap() function to apply a function in one box to the contents of another box:

const add = x => y => x + y
Box(add)
  .ap(Box(2) // Box(y => 2 + y)
  .ap(Box(3) // Box(5)

Lifting and .liftA2() help clean up the above need to apply a simple function to two (thus the A2) boxes. We lift the values out of the boxes and apply the function:

liftA2(add, Box(2), Box(3))
// => Box(5)

This is made possible by the law Box(x).map(f) === Box(f).ap(Box(x)):

const liftA2 = (f, boxx, boxy) =>
  boxx.map(f).ap(boxy)

Applicative functors are great for nested looping. For example,

// No mapping or for loops
const merchandise = () =>
  List.of(x => y => z => `product:${x} size:${y} color:${z}`)
  .ap(List(['t-shirt', 'sweater'])
  .ap(List(['small', 'medium', 'large'])
  .ap(List(['black', 'white'])

Applicative functors are also great for concurrent actions. For example,

const Db = ({
  find: id =>
    new Task((rej, res) =>
      setTimeout(() => res({id: id, title: `Project ${id}`}), 100)) // fake delay
})

const reportHeader = (p1, p2) =>
  `Report: ${p1.title} compared to ${p2.title}`

Task.of(p1 => p2 => reportHeader(p1, p2))
.ap(Db.find(20))
.ap(Db.find(8)) // does not wait for previous Db.find to complete
.fork(console.error, console.log)
// => Report: Project 20 compared to Project 8

TODO: If I remove the fork call above, will any of it run?

.traverse() is used to "leap frog" or "commute" from an array of Tasks...

const readFile = futurize(fs.readFile)

const files = ['foo.json', 'bar.json']
const res = files.map(filename => readFile(filename, 'utf-8'))
// => [Task, Task]

...to a Task with an array of results:

const files = List(['foo.json', 'bar.json'])
files.traverse(Task.of, filename => readFile(filename, 'utf-8'))
.fork(console.error, console.log)
// => Task([result, result])

Note that traverse can also turn Map({key: Task}) => Task(Map({key: result}))

Map({home: '/', about: '/about'})
.traverse(Task.of, route => httpGet(route))  // httpGet returns a Task
.fork(console.error, console.log)
// => Task({home: results, about: results})

Traverse only applies to applicative functors.

A natural transformation is, naively, a function that converts one box to another, i.e. Either(x) => Task(x).

• Formally, a natural transformation (nt) must obey nt(x).map(f) === nt(x.map(f)).

• The two sides of this law describe the two paths (top-right vs left-bottom) that may be used to get from F(a) --> G(b):

  F(a) -- map(f) --> F(b) | | | nt | nt | | G(a) -- map(f) --> G(b)

An isomorphism can convert one type to another and back again.

from(to(x)) === to(from(x))

For example,

// String ~ [Char]
const Iso = (to, from) => ({ to, from })
const stringToCharIso = Iso(s => s.split(''), c => c.join(''))

This allows us to convert types into another type that is more conducive to what we want to do:

const truncate = str =>
  stringToCharIso.from(stringToCharIso.to(s).slice(0, 3)).concat('...')
  
truncate('hello world')
// => 'hel...'