Higher order function on a tree¶
Yeah, tree is constructed in such a way, but how do you perform an operation on it?
I set three operations which will help you customize a tree in a simple manner.
They automatically traverse the tree on which it inhabits.
It means they will be implemented in a way that reach all of nodes checking each reference between nodes out.
1. fmap , fmapL ¶
fmap is a bit generalized map operation which can often be called functor.
Type of functor is
fmap :: Functor f => (a -> b) -> f a -> f b
where first argument is a function which gets a and returns b & second is a set of data type which contains data a with functor instance.
Since I set fmap as a member argument of base node, f a is a set of nodes which can be shown as an object before .fmap.
Note that original functor are performed on an immutable data which mean type a & b are non-relavant. But, this case, since fmap is a member function, type is
fmap :: Functor f => (a -> a') -> f a -> f a'
where a' can be partially modified object.
This allowance of mutableness helps performance faster, but makes side-effects and codes ugly.
On the other hand, fmapL does not have any side effects as it returns lists after a given function is applied.
Its type are
fmapL :: Functor f => (a -> [b]) -> f a -> [b]
2. filter , filterL ¶
filter is a function which accepts a function which will return boolean value.
original type is defined only for list.
filter :: (a -> Bool) -> [a] -> [a]
here type of extended filter was
filter :: (a -> Bool) -> f a -> f a
where f is a set of object.
Keep in mind tree have to be reconstructed after filtering nodes.
For instance, to put it falankly, if a parent node has two child, and it is removed the left two orphans makes quarrel which one should come to a grand parent.
You can filter a parent whose child is just 1, but you cannot filter singleton or a parent more than two children out.
3. foldl foldr ¶
fold is a generalization of above two higher order functions.
But, it shuld be used for the cases where only states are needed and updated during a traverse.
Its type are
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
where b is a state
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
where b is a state
Its differece is whether state comes first or second of a given function. Note it does not change how they are traversed on a tree, but each individual application is just slightly different.