hfour / hfour/yads

Investigate the possibility to further generalize folds

Open
#2 2 comments 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.