Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

`[X] @list-of-lists` misbehaves with list of one list #6370

Open
p6rt opened this issue Jul 1, 2017 · 9 comments
Open

`[X] @list-of-lists` misbehaves with list of one list #6370

p6rt opened this issue Jul 1, 2017 · 9 comments
Labels
Bug

Comments

@p6rt
Copy link

@p6rt p6rt commented Jul 1, 2017

Migrated from rt.perl.org#131686 (status was 'open')

Searchable as RT131686$

@p6rt
Copy link
Author

@p6rt p6rt commented Jul 1, 2017

From @mscha

This is OK​:

say [X] ((1,2,3), (4,5,6));
((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6))
say [X*] ((1,2,3), (4,5,6));
(4 5 6 8 10 12 12 15 18)

... but this is incorrect​:

say [X] ((1,2,3),);
((1 2 3))
say [X*] ((1,2,3),);
(6)

Expected output is​:
((1) (2) (3))
and
((1) (2) (3))

Note that [*] behaves as expected​:

say [*] ((1,2,3),(4,5,6));
9
say [*] ((1,2,3),);
3

... since this is equivalent to​:

say [*] (3, 3);
9
say [*] (3,);
3

@p6rt
Copy link
Author

@p6rt p6rt commented Jul 1, 2017

From @AlexDaniel

I think this is related​: Raku/doc#1400

On 2017-07-01 12​:25​:39, perl6@​mscha.org wrote​:

This is OK​:

say [X] ((1,2,3), (4,5,6));
((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6))
say [X*] ((1,2,3), (4,5,6));
(4 5 6 8 10 12 12 15 18)

... but this is incorrect​:

say [X] ((1,2,3),);
((1 2 3))
say [X*] ((1,2,3),);
(6)

Expected output is​:
((1) (2) (3))
and
((1) (2) (3))

Note that [*] behaves as expected​:

say [*] ((1,2,3),(4,5,6));
9
say [*] ((1,2,3),);
3

... since this is equivalent to​:

say [*] (3, 3);
9
say [*] (3,);
3

@p6rt
Copy link
Author

@p6rt p6rt commented Jul 1, 2017

The RT System itself - Status changed from 'new' to 'open'

@p6rt
Copy link
Author

@p6rt p6rt commented Jul 1, 2017

From @mscha

That may indeed explain why it works the way it does, but that doesn't
mean it isn't a bug. IMO it certainly is; [X] and [X*] don't work as
advertised.

Let me explain how I found this bug.
I'm generating a list of divisors for a number. I already have the
prime factorization of that number, and a list of all the "prime powers".
Examples​:
  24 = 2³×3¹​: ((1, 2, 4, 8), (1, 3))
  42 = 2¹×3¹×7​: ((1, 2), (1, 3), (1, 7))
  64 = 2⁶​: ((1, 2, 4, 8, 16, 32, 64),)
Now it's easy to generate the divisors​:

say [X*] ((1, 2, 4, 8), (1, 3));
(1 3 2 6 4 12 8 24)

say [X*] ((1, 2), (1, 3), (1, 7));
(1 7 3 21 2 14 6 42)

say [X*] ((1, 2, 4, 8, 16, 32, 64),)
(2097152)
Oops...

@p6rt
Copy link
Author

@p6rt p6rt commented Jul 1, 2017

From @AlexDaniel

I'd agree that it is a bug, yes. Well, the reason why it happens might be justified, but this is probably one of the fattest traps I've seen so far. I really think we should come up with a way to eliminate this trap somehow. Not sure how, but there must be a way and I really recommend anybody reading this to think in this direction (instead of writing a lot of text to come up with excuses to reject this ticket). Maybe it's something we can fix in v6.d, or maybe we can add some kind of warning right now. I don't know, but I truly hope that there is a solution.

On 2017-07-01 13​:17​:58, perl6@​mscha.org wrote​:

That may indeed explain why it works the way it does, but that doesn't
mean it isn't a bug. IMO it certainly is; [X] and [X*] don't work as
advertised.

Let me explain how I found this bug.
I'm generating a list of divisors for a number. I already have the
prime factorization of that number, and a list of all the "prime powers".
Examples​:
24 = 2³×3¹​: ((1, 2, 4, 8), (1, 3))
42 = 2¹×3¹×7​: ((1, 2), (1, 3), (1, 7))
64 = 2⁶​: ((1, 2, 4, 8, 16, 32, 64),)
Now it's easy to generate the divisors​:

say [X*] ((1, 2, 4, 8), (1, 3));
(1 3 2 6 4 12 8 24)

say [X*] ((1, 2), (1, 3), (1, 7));
(1 7 3 21 2 14 6 42)

say [X*] ((1, 2, 4, 8, 16, 32, 64),)
(2097152)
Oops...

@p6rt
Copy link
Author

@p6rt p6rt commented Jul 2, 2017

From @smls

I agree that things like

  my @​divisors = [X] @​prime-factor-powers;
 
  my @​transpose = [Z] @​matrix;

look perfectly reasonable and elegant, and the fact that the single-sub-list edge-case ruins them is regrettable. Nor can I image any scenario where the current behavior of that edge-case is useful.

I assumed that because it was the natural result of a core Perl 6 design decision which is surely not under discussion anymore (the "single-argument rule" for list-munging routines like `zip` and `cross`), we would have to live with it.

But Aleks-Daniel is right, it really would be great to find some way to "fix" this edge-case. Here's a first idea​:


Maybe `reduce` could simply introspect the operator and if sees that the signature starts with a "single-argument slurpy" parameter (`+foo` / `+@​foo`), adapt the calls to it accordingly?

At first glance that seems LTA (special cases are icky), but consider that​:

1) `reduce` *already* introspects its operator and adapts its operation accordingly, in order to provide maximum DWIM regarding associativity, unity, etc.

2) The "single-argument rule" can be seen as just another calling convention. When we write `zip @​foo`, the the parser may think a function is being called with one argument... but *we* know that we're sending all the sub-lists of @​foo to be zipped, and that if we had wanted to send the single list @​foo we would have had to write `zip (@​foo,)` or `zip $@​foo`.
`reduce` also knows that it wants to apply the operator to a single item in the edge-case in question, and it could adapts its call to make that happen for whatever calling convention the operator uses.

Point (2) raises the question if other built-ins like `map` and `grep` would have to learn about different calling conventions as well, for consistency.
But I don't think that's necessarily the case. Things like `map` are very generic in the sense that they don't understand anything about what is being piped through them... the user is fully in charge of controlling the inputs and outputs of the callback. (Also, the current behavior is actually useful there.)
`reduce` is more high-level, in the sense that it knows it's dealing with an operator and a list of elements to fold, and wants to call the operator with either zero, one or two of those elements at a time.

This shouldn't be interpreted as an RFC yet, just some thoughts. Someone would have to thoroughly think through the implications, and test the spectest/ecosystem fallout.

@p6rt
Copy link
Author

@p6rt p6rt commented Jul 18, 2017

From joshuamy@gmail.com

... it really would be great to find some way to "fix" this edge-case.

I don't think anything needs to be fixed. This is along the same vein as the misguided thinking that `[Z] (3,2)` should yield `(2,3)`.

I also think the comparison to [*] is invalid since it operates on number-y things, and [X] explicitly operates on 2 or more lists or iterables.

My thinking is that doing `[X] ((3,2),)` is kinda like doing `[X] ((3,2),Empty)`... Not exactly equivalent, but almost.

The Cartesian product of singleton sets is again a singleton set (ie. product [[1]; [2]; [3]] is [1; 2; 3]

My feeling is that current behavior is fine. At most, perhaps a warning in a similar vein to `sink context` warnings, eg. 'Useless use of meta-reduce [X] on single list' or something

@p6rt
Copy link
Author

@p6rt p6rt commented Jul 18, 2017

From @smls

On Tue, 18 Jul 2017 07​:45​:16 -0700, joshuamy@​gmail.com wrote​:

My thinking is that doing `[X] ((3,2),)` is kinda like doing `[X] ((3,2),Empty)`...

Assuming I understand your analogy correctly, that's exactly what's *not* happening, and is why this RT exists. See​:

  dd [X] 3, 2; # ((3, 2),).Seq
  dd [X] (3, 2); # ((3, 2),).Seq
  dd [X] ((3, 2),); # ((3, 2),).Seq

The first two are unsurprising, but note how the third one is *also* being treated as the Cartesian product between the two sets `3` and `2`, rather than the single set `(3, 2)`.

Also, scenarios where the argument list to `[X]` or `[Z]` is fixed-sized (like in these examples), isn't what is tripping people up (because there's no reason to write that in the single-sublist case anyway). The problem is with crossing or zipping a variable-sized list of lists, like in `my @​transpose = [Z] @​matrix;`, which works fine for most inputs but breaks down for the "@​matrix has exactly one row" edge-case. I've explained why this is happening and why it ruins people's day in this docs ticket​: [1], and this StackOverflow answer​: [2].


[1] Raku/doc#1400
[2] https://stackoverflow.com/questions/44821983/recursive-generator-manual-zip-vs-operator/44831926#44831926

@p6rt
Copy link
Author

@p6rt p6rt commented Jul 18, 2017

From @mscha

In my opinion, to decide whether it's a bug, you shouldn't look at the
implementation of [X] and [X*], but rather at its practical use.
In what cases would you use it, and what do you expect it to return when
your list of lists happens to be one list?
That's what I was trying to do with my example to determine the divisors
of a number, given the prime factorization. (That was a simplified
version of my actual code where I encountered the bug, and lost about
half an hour figuring out what was happening.)

If someone states the current behaviour is correct, I'd like them to
come up with a practical example where [X] or [X*] currently does the
right thing.

But perhaps an even easier way to look at it is​:

[X] (@​a, @​b, @​c) is equivalent to @​a X @​b X @​c
[X] (@​a, @​b) is equivalent to @​a X @​b
so [X] (@​a,) is equivalent to @​a

and

[X*] (@​a, @​b, @​c) is equivalent to @​a X* @​b X* @​c
[X*] (@​a, @​b) is equivalent to @​a X* @​b
so [X*] (@​a,) is equivalent to @​a

@p6rt p6rt added the Bug label Jan 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
1 participant
You can’t perform that action at this time.