potassco / potassco/constraint-handler

Fold implementation as intended?

Open
#101 3 comments 0 reactions 0 assignees View on GitHub

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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.