Investigate the possibility to further generalize folds
- Dominant language
- TypeScript
- Stars
- 8
- Forks
- 4
- PR merge metrics
- No merged PRs in 30d
Description
### Explanation
As can be seen in #1, the current design only considers a subset of folding functions, since it was built (with partial folds in mind) upon a specific use case (see https://gist.github.com/spion/4b31ec396c4cbfebede55558f6238891).
This can be a bit limiting in some cases, and it'd be interesting to generalize this library further to accept something more than just Monoids.
### Why?
Because it's fun, and maybe the use cases will appear afterwards :)
### Reproduction steps
```typescript
const HundredMinus: MonoidObj = Object.freeze({
operation: (res, acc) => res - acc,
identity: 100,
getCacheValue: (leaf) => leaf.data
});
const data = [1, 3, 5];
const tree = fromArray(data);
console.log(tree.getField(HundredMinus)); // prints 91, OK
insert(tree, 3, [7]);
printtree(tree);
/* prints:
R___
/ \
a b
/ \ / \
1 3 5 7
*/
console.log(tree.getField(HundredMinus)); // prints -84 instead of 84
```
### Further explanation
I would expect the code above to work similarly as if I were folding a list. An example:
```
> (foldl (lambda (el res) (- res el)) 100 '(1 3 5))
91
> (foldl (lambda (el res) (- res el)) 100 '(1 3 5 7))
84
```
### Potential solution
Let's re-consider the case from #1:
```
R___
/ \
a b
/ \ / \
e1 e2 e3 e4
```
For the operation `-` we have that `pf(a) = e1 - e2` and `pf(b) = e3 - e4`, but `pf(a) - pf(b) = e1 - e2 - e3 + e4`, which is different from `pf(R) = e1 - e2 - e3 - e4`.
If, however, we had a way to (optionally) specify an order relation for the elements, we could fix this issue. In the example above, if we consider the orders `e4 > e3 > e2 > e1`, then we will have:
1. `pf(a) = e2 - e1`
2. `pf(b) = e4 - e3`
3. `pf(R) = e4 - e3 - e2 - e1`
There seems to be some related discussion [here](http://lambda-the-ultimate.org/node/1882).
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.