/
list.pl
137 lines (129 loc) · 3.26 KB
/
list.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#!/usr/bin/perl
use strict; use warnings;
{
package List;
use Sub::Call::Tail;
sub new {
my $class = shift;
return bless \@_, $class;
}
sub to_string {
my ($list, $acc) = @_;
$acc ||= '';
my $head = $list->head;
my $tail = $list->tail;
return "${acc}${head}" unless $tail;
tail $tail->to_string( "${acc}${head}," );
}
sub to_string_it {
my $list = shift;
# fake tail recursion with iteration
my $acc = '';
{
$acc .= $list->head;
if (my $tail = $list->tail) {
$acc .= ',';
$list = $tail;
redo
}
}
return $acc;
}
sub nth {
my ($list, $n) = @_;
if ($n) {
return $list->tail->nth($n-1);
}
else {
return $list->head;
}
}
}
{
package List::List;
our @ISA = 'List';
sub head {
my $list = shift or return;
return $list->[0];
}
sub tail {
my $list = shift or return;
return $list->[1];
}
}
{
package List::Array;
our @ISA = 'List';
sub head {
my $self = shift;
return $self->[0]->[ $self->[1] || 0 ];
}
sub tail {
my $self = shift;
my $array = $self->[0];
my $offset = ($self->[1] || 0) + 1;
if ($offset <= $#$array) {
return bless [ $array, $offset ], 'List::Array';
}
else {
return;
}
}
sub nth {
my ($self, $n) = @_;
my ($list, $offset) = @$self;
return $list->[$offset + $n];
}
sub to_string {
my $self = shift;
my ($list, $offset) = @$self;
my @list = @$list[$offset..$#$list];
return join ',' => @list;
}
}
package main;
use Data::Dumper;
use feature 'say';
# use Variable::Lazy;
use lib '/home/hakim/other_repos/data-thunk/lib/';
use Data::Thunk;
# use Scalar::Defer; # too fucking slow, deep recursion in global destruction
# use Scalar::Lazy; # doesn't defer to methods
sub node ($$) {
# return bless \@_, 'List::List';
return lazy_new 'List::List', args => \@_; # Data::Thunk
}
sub list {
my ($head, @tail) = @_
or return;
# lazy my $tail = { list(@tail) }; # Variable::Lazy
# my $tail = lazy { list(@tail) }; # Scalar::Lazy, and the others. Caveats
my $tail = lazy_object { list(@tail) } class=>'List::List'; # Data::Thunk
# my $tail = list(@tail); # none (blows stack)
return node $head, $tail;
}
sub array {
return bless [\@_, 0], 'List::Array';
}
my @list = (1..10_000);
my $list = list(@list);
my $array = array(@list);
say $list->to_string;
say $array->to_string;
$list->to_string eq $array->to_string or die "EEEK!";
warn $array->nth(50);
warn $list->nth(50);
use Benchmark 'cmpthese';
my $ITERATIONS = -2; # run for 2 seconds
cmpthese $ITERATIONS => { # 8333, 14286
list_create => sub { my $list = list(@list); },
array_create => sub { my $array = array(@list); },
};
cmpthese $ITERATIONS => {
list_to_string => sub { $list->to_string },
array_to_string => sub { $array->to_string },
};
cmpthese $ITERATIONS => {
list_nth => sub { $list->nth(50) },
array_nth => sub { $array->nth(50) },
};