Closed DrBoolean closed 7 years ago
@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?
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 (https://github.com/facebook/react/issues/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.
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.
Ahh, right on. I don't claim to know much about BST's. That definitely sounds legit.
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 employedpartition
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 addwhich 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. ConsiderPromise.resolve('yo').then(x => x.toUpperCase()).then(x => x + '!')
andPromise.resolve('yo').then(x => x.toUpperCase() + '!')
. Were it not for this law, we wouldn't be able to trustthen
at all. (of course, we'd renamethen
tomap
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
value
and not the wholenode
. This is becausemap
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 instanceextend
which does pass the wholenode
in, but only replaces thevalue
of that onenode
with whatever's returned. So: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 passvalue
in, it is indeed a functor and we probably should mention that :)value
applies toreduce
. 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 andreduce
is an entirely different animal.S
inBST
is not preserved by any of these operations. For it to remain a search tree, we must balance after eachmap/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.