Problem-specifications: list-ops: add simpler foldl/foldr tests to create gentler difficulty slope?

[stkent]

Context

• Prior discussion that touches lightly on the topic at hand
• kotlin PR that generated this x-common issue

Description

The current canonical data for list-ops includes the following non-degenerate cases for the foldl and foldr functions:

{
  "description": "division of integers",
  "property": "foldl",
  "list": [1, 2, 3, 4],
  "initial": 24,
  "function": "value / accumulator",
  "expected": 64
}

and

{
  "description": "division of integers",
  "property": "foldr",
  "list": [1, 2, 3, 4],
  "initial": 24,
  "function": "value / accumulator",
  "expected": 9
}

The folding captured by these tests is quite tricky to reason about due to

1. the oscillating nature of the accumulating result, and
2. the fact that the input and expected output values are _all_ integers, even though most solutions (at least in statically typed languages) will need to use higher-precision numerical representations.

Since folding is one of the more complex operations we're asking implementors to build in this exercise, I propose (h/t @sdavids13) that we insert _at least one_ simpler test right before each of the division-based tests captured above. In particular, we could follow the example of xpython (which is currently not compliant with the canonical data), and have implementors first pass a test that uses a simpler operation (addition, subtraction, multiplication, or all of the above) whose expected result is easier to validate and whose implementation can be integer-only. Examples for foldl:

{
  "description": "addition of integers",
  "property": "foldl",
  "list": [1, 2, 3, 4],
  "initial": 5,
  "function": "accumulator + value",
  "expected": 15
}

and/or

{
  "description": "subtraction of integers",
  "property": "foldl",
  "list": [1, 2, 3, 4],
  "initial": 5,
  "function": "accumulator - value",
  "expected": -5
}

and/or

{
  "description": "multiplication of integers",
  "property": "foldl",
  "list": [1, 2, 3, 4],
  "initial": 5,
  "function": "accumulator * value",
  "expected": 120
}

Inviting feedback on this idea; happy to handle any changes resulting from discussion :)

[Insti]

Why is division even necessary to test? This is list-ops not complex-expression-parsing

[NobbZ]

There is no expression parsing involved from the students point of view. Just a passed in function f. And this function f shall be passed in as \value acc -> accumulator / value or whatever representation the implementing language uses for lambdas, closures, procs or just function references.

Personally, I think it is important to find a way to test if foldl/foldr are folding in the right direction. In the domain of integral numbers, I do only see the integral division as a function which we can use to check for the direction of the fold. Only using this, we can construct a function that will yield different results for the same list and initial when swapping foldl with foldr.

[stkent]

@NobbZ is correct regarding how the division is expressed in this exercise. However, I'm struggling to find an example using integer division that uses the same initial value and list to differentiate between foldl and foldr. @NobbZ are you able to provide one?

[NobbZ]

Quick play in the Haskell-REPL:

Prelude> foldr div 5 [2, 5]
2
Prelude> foldl div 5 [2, 5]
0

[stkent]

Ah, right, I forgot we were using value / accumulator rather than accumulator / value. Thanks! So we may want to add this sort of test too to verify directionality is handled properly 👍

[stkent]

Ah, right, I forgot we were using value / accumulator rather than accumulator / value.

Just to clarify; actually, we're using both. If you look at the type signatures for foldl and foldr you'll note that we have to use value / accumulator or accumulator / value depending upon whether we're folding from the left or folding from the right.

I'll post tomorrow regarding the changes I made to xkotlin to see whether they would be acceptable in x-common.

[stkent]

Here's what I ended up with in xkotlin (pseudo-canonical entries):

{
  "description": "multiplication with empty list",
  "property": "foldl",
  "list": [],
  "initial": 2,
  "function": "(x, y) -> x * y",
  "expected": 2
},
{
  "description": "addition of integers",
  "property": "foldl",
  "list": [1, 2, 3, 4],
  "initial": 5,
  "function": "(x, y) -> x + y",
  "expected": 15
},
{
  "description": "division of integers",
  "property": "foldl",
  "list": [2, 5],
  "initial": 5,
  "function": "(x, y) -> x / y",
  "expected": 0
}

{
  "description": "multiplication with empty list",
  "property": "foldr",
  "list": [],
  "initial": 2,
  "function": "(x, y) -> x * y",
  "expected": 2
},
{
  "description": "addition of integers",
  "property": "foldr",
  "list": [1, 2, 3, 4],
  "initial": 5,
  "function": "(x, y) -> x + y",
  "expected": 15
},
{
  "description": "division of integers",
  "property": "foldr",
  "list": [2, 5],
  "initial": 5,
  "function": "(x, y) -> x / y",
  "expected": 2
}

Feedback welcome on these specific suggestions.

[Insti]

Super @stkent.
As someone who has not done this exercise but is interested in tests, I have a few questions:

Do there need to be 6 tests?
Is there a way to make one of these tests pass that would not also cause the others to pass?

What needs to be tested?

• foldr works correctly.
• foldl works correctly.

What are the important properties of these functions?

What are these tests testing? The descriptions seem to suggest that it has something to do with the function, but that seems to me like it is a bit of a red herring, as what the function is should not be important to the folding.

Is the function used relevant to the tests?

[stkent]

Great questions!

• The empty tests verify that the initial value is returned correctly when the list is empty. I can imagine that a common error here might be to return 0 or 1, the additive or multiplicative identities resp., by mistake. The operation here is not significant since it should never be performed. These tests could be passed by an implementation that returns the initial value and ignores the passed list entirely.
• The addition tests verify that folding is working correctly for a direction-independent function. I can imagine common errors here being off-by-one when iterating or recursing, or forgetting to include the initial value. The significant part of the chosen function is that when it is used to fold, the end result is not equal to the initial value passed to our fold implementations. These tests could be passed by an implementation that always folds from the left, rather than folding from the left/right as appropriate.
• The division tests verify that folding is working correctly for a direction-dependent function. I can imagine common errors here being incorrect or misleading type signatures, or realizing both fold functions actually traverse the list in the same direction. The significant part of the chosen functions (both equivalent to Int::div) is that when they are used to fold, the end result depends on the direction in which you traverse the list.

Does the above breakdown sufficiently address your questions, @Insti?

[ErikSchierboom]

I really like the idea of introducing more tests for the foldl/foldr cases.

[Insti]

Does the above breakdown sufficiently address your questions, @Insti?

Yes, thankyou.
Perhaps the test descriptions could be enhanced by including some of this information that describes what the test is for rather than what it does.

[stkent]

Definitely agree; these are the names I used in Kotlin tests:

testFoldLeftWithDirectionIndependentOperationOnNonEmptyList
testFoldLeftWithDirectionDependentOperationOnNonEmptyList
testFoldRightOnEmptyList
testFoldRightWithDirectionIndependentOperationOnNonEmptyList
testFoldRightWithDirectionDependentOperationOnNonEmptyList

Do those capture enough of the details, do you think? If so, I'll turn them back into English language descriptions and open up a PR (I think we're ready for that?)

[Insti]

Yes, they look like more helpful names.

[stkent]

Awesome! I'll open a PR to resolve this issue this evening.