potassco / potassco/constraint-handler
Fold implementation as intended?
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 3
- Forks
- 0
- Avg merge
- 1d 19h
- Merged PRs (30d)
- 20
Description
Hey, so I've implemented some basic examples of how to use set_fold and multimap_fold using the function for add.
This all went fine and the output was as expected. However, while creating the page for functions (that will also include lambdas) I wanted to give another example.
While doing this, I realized that the fold mechanism seems to be a "reversed right fold", is that intended?
More specifically, based on what I know about folds, left and right folds only specify how the operations are parenthesized.
Given a list [1,2,3,4], the sum of all of them would look like 1+2+3+4 = 10. When doing this using a fold and assuming that a "reversed" fold is simply a normal fold with elements in reversed order, we get the following:
| Variant | Expression | Result |
|---|---|---|
| left fold | (((1+2) + 3 ) + 4) |
10 |
| right fold | (1 + (2 + (3 + 4))) |
10 |
| reversed left fold | (((4+3) + 2 ) + 1) |
10 |
| reversed right fold | (4 + (3 + (2 + 1))) |
10 |
As we can see, all four variants give the same result. However, this holds only true for associative operations like addition or multiplication. For
non-associative operations like exponentiation, we get different results:
| Variant | Expression | Result |
|---|---|---|
| left fold | (((1^2) ^ 3 ) ^ 4) |
1 |
| right fold | (1 ^ (2 ^ (3 ^ 4))) |
1 |
| reversed left fold | (((4^3) ^ 2 ) ^ 1) |
4096 |
| reversed right fold | (4 ^ (3 ^ (2 ^ 1))) |
262144 |
I used the following ASP snipped for my example:
set_declare(dummy, my_set).
set_assign(dummy, my_set, val(int, 1..4)).
variable_define(dummy, set_result, FOLD) :-
FUNC = val(function,pow),
SET = variable(my_set),
INIT = val(int, 1),
FOLD = operation(set_fold, (FUNC,(SET,(INIT,())))).
I expected a result of 1 (either from left or right fold), but instead got:
value(set_result,val(int,262144))
This corresponds to the "reversed right fold" variant in my table.
I think this happens because the implementation does a normal left fold, but takes the accumulator as the second instead of the first argument.
Now, my question is: Is this intended behavior?
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by locating the implementation and call sites for set_fold and multimap_fold, then reproduce the supplied ASP example with exponentiation. Compare the observed argument order and nesting with the issue's fold table; done means the intended semantics are established and the behavior or its documentation is aligned with that decision.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- backend
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100