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

p6rt commented 11 years ago

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

Searchable as RT116186$

p6rt commented 11 years ago

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 commented 10 years ago

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 commented 10 years ago

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

p6rt commented 7 years ago

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 commented 7 years ago

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 commented 7 years ago

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

Raku / old-issue-tracker