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

In a recursive List, should a term be allowed to depend on a later term? #3005

Open
p6rt opened this issue Dec 24, 2012 · 6 comments
Open

In a recursive List, should a term be allowed to depend on a later term? #3005

p6rt opened this issue Dec 24, 2012 · 6 comments
Labels

Comments

@p6rt
Copy link

p6rt commented Dec 24, 2012

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

Searchable as RT116186$

@p6rt
Copy link
Author

p6rt commented Dec 24, 2012

From tim.bollman@live.com

Rakudo Version​: 2012.12-38-gc8de2eb

Story​:

I was attempting to write a different solution to the Collatz Sequence problem in this years Advent Calendar. I figured it was a sequence of numbers, the sequence operation should be able to rock this problem efficiently. I'm not sure if this is supposed to be supported by the implementation, but if it is, I believe the problem comes down to Rakudo not liking to vivify later elements in the sequence in order to vivify the current element.

Works​:
my @​collatz;
@​collatz := Inf, 1, (2 .. *).map​: -> $n {@​collatz[$n - 1] + 1}
say @​collatz[0 .. 5]

Inf 1 2 3 4 5

Doesn't Work​:
my @​collatz;
@​collatz := Inf, 1, (2 .. *).map -> $n { $n %% 2 ?? @​collatz[$n div 2] !! @​colatz[3 * $n + 1] }
say @​collatz[0 .. 5]
splice() not implemented in class 'Mu'
  in method reify at src/gen/CORE.setting​:5409
  in method reify at src/gen/CORE.setting​:5407
  in method gimme at src/gen/CORE.setting​:5797
  in method exists at src/gen/CORE.setting​:5786
  in method at_pos at src/gen/CORE.setting​:5766
  in method postcircumfix​:<[ ]> at src/gen/CORE.setting​:1337
  in method postcircumfix​:<[ ]> at src/gen/CORE.setting​:1384
  in method postcircumfix​:<[ ]> at src/gen/CORE.setting​:5042

-Tim
irc​: Tim-Tom

 

@p6rt
Copy link
Author

p6rt commented Jan 23, 2014

From mark@kli.org

It isn't so much computing later values in the sense of higher numbered ones. It's computing ones that haven't been computed yet. The first example doesn't work either, if you don't access the values sequentially​:

my @​collatz := Inf, 1, (2 .. *).map​: -> $n {@​collatz[$n - 1] + 1} ;1
1
@​collatz[5]
use of uninitialized value of type Nil in numeric contextuse of uninitialized...

(On my system the error string is in an endless loop)

When you accessed it with ^5, you allowed each element to be computed before it was needed by others. It doesn't have to be linear​:

my @​collatz := Inf, 1, (2 .. *).map​: -> $n {@​collatz[$n div 2] } ;1
1
@​collatz[0]
Inf
@​collatz[1]
1
@​collatz[2]
1
@​collatz[4]
1
@​collatz[8]
1
@​collatz[16]
1

@p6rt
Copy link
Author

p6rt commented Jan 23, 2014

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

@p6rt
Copy link
Author

p6rt commented Aug 11, 2016

From @coke

On Sun Dec 23 16​:28​:31 2012, TimTom wrote​:

Rakudo Version​: 2012.12-38-gc8de2eb

Story​:

I was attempting to write a different solution to the Collatz Sequence
problem in this years Advent Calendar. I figured it was a sequence of
numbers, the sequence operation should be able to rock this problem
efficiently. I'm not sure if this is supposed to be supported by the
implementation, but if it is, I believe the problem comes down to
Rakudo not liking to vivify later elements in the sequence in order to
vivify the current element.

Works​:
my @​collatz;
@​collatz := Inf, 1, (2 .. *).map​: -> $n {@​collatz[$n - 1] + 1}
say @​collatz[0 .. 5]

Inf 1 2 3 4 5

Doesn't Work​:
my @​collatz;
@​collatz := Inf, 1, (2 .. *).map -> $n { $n %% 2 ?? @​collatz[$n div 2]
!! @​colatz[3 * $n + 1] }
say @​collatz[0 .. 5]
splice() not implemented in class 'Mu'
in method reify at src/gen/CORE.setting​:5409
in method reify at src/gen/CORE.setting​:5407
in method gimme at src/gen/CORE.setting​:5797
in method exists at src/gen/CORE.setting​:5786
in method at_pos at src/gen/CORE.setting​:5766
in method postcircumfix​:<[ ]> at src/gen/CORE.setting​:1337
in method postcircumfix​:<[ ]> at src/gen/CORE.setting​:1384
in method postcircumfix​:<[ ]> at src/gen/CORE.setting​:5042

-Tim
irc​: Tim-Tom

Neither of these work now (2016.07.1)

The first outputs​:

(Inf 1 (...) Nil Nil Nil)

And the second

===SORRY!=== Error while compiling /Users/coke/p6
Unexpected block in infix position (missing statement control word before the expression?)
at /Users/coke/p6​:2
------> @​collatz := Inf, 1, (2 .. *).map⏏ -> $n { $n %% 2 ?? @​collatz[$n div 2] !
  expecting any of​:
  infix
  infix stopper

--
Will "Coke" Coleda

@p6rt
Copy link
Author

p6rt commented Aug 12, 2016

From @smls

The first one still works in current Rakudo if you add a | to slip the `map` sequence into the parent list.
Here it is in slightly simplified form​:

  ➜ my @​collatz = Inf, 1, |(2 .. *).map​: { @​collatz[$_ - 1] + 1 }; say @​collatz[0 .. 5];
  (Inf 1 2 3 4 5)

As for the second one, after giving it the same treatment (and fixing its two syntax typos), it simply hangs indefinitely after the third term​:

  ➜ my @​collatz = Inf, 1, |(2 .. *).map​: { $_ %% 2 ?? @​collatz[$_ div 2] !! @​collatz[3 * $_ + 1] }; say @​collatz[$_] for 0 .. 5;
  Inf
  1
  1

So it seems that Timothy Bollman's key observation in the original ticket is still correct​: Rakudo won't reify a later term of a sequence, in order to reify an earlier term.

I have no idea if it *should* work (ask TimToady), or if it would even be feasible given how lists/sequences work (ask jnthn).

@p6rt
Copy link
Author

p6rt commented Aug 12, 2016

From @smls

Here is a simpler test-case demonstrating the issue (i.e. recursive out-of-order reification not working)​:

  ➜ my @​a = (0..*).map({ $_ == 0 ?? 10 !! 5 }); say @​a[^5];
  (10 5 5 5 5)

  ➜ my @​a = (0..*).map({ $_ == 0 ?? 2 * @​a[1] !! 5 }); say @​a[^5]; # This one generates junk results
  (5 5 10 5 5)

  ➜ my @​a = (0..*).map({ $_ %% 2 ?? 2 * @​a[$_ + 1] !! 5 }); say @​a[^5]; # This one hangs

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

No branches or pull requests

1 participant