Tech Edit: Ch 8

[DrBoolean]

This is a very important chapter and as far as List operations go, I think it is a grand slam. I dug the filter double negatives :) I mix that up still! I also really like the visualizations and various "real world" uses of reduce to implement other familiar list methods. You even touch of an important advanced FP practice of not destroying information (discouraging every/some). I even go as far as to not use filter and have since employed partition in its place.

Found 1 quick typo (i know it's not my job, but I figured i'd say something if i see it)

• values together into on value -> values together into one value

There are some issues around Functors:

• Functor is not artificial invented terminology - it is an exact implementation from category theory (https://en.wikipedia.org/wiki/Functor) just as isomorphism or compose is.

• A functor is a value that has a utility for using an operator function on that value. - I'd add which preserves composition. That's very important because it means [x].map(f).map(g) === [x].map(x => g(f(x)) or in other words, means you can keep chaining maps or fusing them as we mention later in the chapter, without concern. Consider Promise.resolve('yo').then(x => x.toUpperCase()).then(x => x + '!') and Promise.resolve('yo').then(x => x.toUpperCase() + '!'). Were it not for this law, we wouldn't be able to trust then at all. (of course, we'd rename then to map to make it the proper interface)

• The string example is not a functor because it does not preserve composition:
  const x = stringMap(x => x.letter, stringMap(x => ({letter: x}), "bob")) // ''
const x = stringMap(x => ({letter: x}.letter), "bob") // 'bob'

Basically, the law suggests you must be able to change types within a map.

A few issues with BST

• A typical implementation of a binary tree found in an FP language would pass the value and not the whole node. This is because map should effortlessly preserve structure and obey the above laws.

Passing the whole node allows one to alter the structure of the tree while traversing it, which can lead to super confusing behavior like replacing subtrees you just mapped.

When we need a whole node, we use the comonad instance extend which does pass the whole node in, but only replaces the value of that one node with whatever's returned. So:

tree.map(v => v.toUpperCase()) // same tree with uppercases
tree.extend(node => node.value.toUpperCase()) // same tree with uppercases, but we get more context while altering the 1 value

The map provided then, disqualifies it from being a functor. Perhaps that should be mentioned or we shouldn't have previously discussed functors since, in my opinion, it's a little confusing to the reader. Otherwise if we pass value in, it is indeed a functor and we probably should mention that :)

• The same issue with value applies to reduce. Typically the way we'd want to get more context here is with different recursion schemes (and those have a direct relationship with comonads). Unlike map, I'd need to play around with altering the tree structure whilst reducing to understand why this matters or if it even matters.

For this one though, I realize how bending over backwards to be principled is in direct conflict with the intent of this book. If i had to pick a battle it'd be map since that does not hold the intuition and reduce is an entirely different animal.

• Finally the S in BST is not preserved by any of these operations. For it to remain a search tree, we must balance after each map/filter/reduce.

That means we cannot make a search tree a functor anyways because of the constraint that composition is limited to "comparable" return values. e.g. how does one balance tree.map(x => Promise.resolve(x)). I think maybe the best move here is to remove the search part so it keeps the discussion focused on the utility of these functions.

In any case, I think these issues can be easily ironed out with a few adjustments and the chapter can remain perfectly in tact since it flows beautifully and teaches some great content.

[getify]

@DrBoolean if you do a filter(..) operation on a tree, you necessarily have to alter the actual tree structure and not just deal with its values, right? Deleting a node from a binary tree means you have to propagate that deletion to down that subtree.

I originally was going to do these operations over only the values and not the nodes, but as soon as I got to filter(..), I realized I had to handle the tree structure. I don't see any other way to do filter(..) on a tree, am I missing something?

[DrBoolean]

In the time since I wrote this, I've been studying recursion-schemes much more deeply.

You are totally right that filter requires the whole node. In fact, that's why recursion schemes pass in the full object and end up amounting to GOF's visitor pattern (without that mutation)

I think the "right" thing to do is pass the full node to reduce, then implement map and filter in terms of reduce, but don't pass the full node in those functions.

Filter ends up being rather strange - you try to keep a bunch of nodes as you visit them, but as soon as it filters a node above them, they disappear. Huge branches of information lost because of one parent! I've seen various attempts to solve (facebook/react#2956) and the solution often ends up being toArray.

In fact, the Foldable interface amounts to toList in haskell.

I think most literature separates the subset of structure preserving maps (map) from the more general folds (filter), which can lose structural information, simply because one has so many more guarantees on how it works - a separation of bijective and injective functions.

[getify]

you try to keep a bunch of nodes as you visit them, but as soon as it filters a node above them, they disappear. Huge branches of information lost because of one parent!

Perhaps that's true of general trees, but for BSTs, I interpreted filter to only filter out a single node, not implying that it's children are lost. That's the whole reason for filter(..) implementing the "delete" algorithm of BSTs, so that all the children nodes below it shuffle upward and aren't lost.

[DrBoolean]

Ahh, right on. I don't claim to know much about BST's. That definitely sounds legit.