lib/FP/StrictList.pm

filter: Statementstmt 96.6% 200 / 207 Branchbran 57.6% 15 / 26 Conditioncond 72.7% 8 / 11 MC/DCmcdc 40.0% 2 / 5 Subroutinesub 94.5% 70 / 74 Podpod 0.0% 0 / 7 totaltotal 89.3% 295 / 330 CC 17 SCAR 5.6
CC
17
Cov
91%
is_strictlist
6.3
strictlist
6.0
__ANON__
3.0
CRAP 1.7
« functional_XML/testlazy ↑ Summary lib/Chj/Packages.pm »
1 #
2 # Copyright (c) 2015-2021 Christian Jaeger, copying@christianjaeger.ch
3 #
4 # This is free software, offered under either the same terms as perl 5
5 # or the terms of the Artistic License version 2 or the terms of the
6 # MIT License (Expat version). See the file COPYING.md that came
7 # bundled with this file.
8 #
9  
10 =head1 NAME
11  
12 FP::StrictList - an FP::List that enforces list semantics
13  
14 =head1 SYNOPSIS
15  
16 1 ▶ use FP::StrictList;
Subroutine BEGIN: called CC=1 SCAR=0.0
17 1 ▶ use FP::Div 'inc'; use FP::List;
Subroutine BEGIN: called CC=1 SCAR=0.0
Subroutine BEGIN: called CC=1 SCAR=0.0
18  
19 my $l = strictlist (4,5)->map(\&inc);
20 ok is_strictlist $l; # O(1)
21  
22 1 ▶ use FP::Equal qw(equal is_equal); use FP::List 'null';
Subroutine BEGIN: called CC=1 SCAR=0.0
Subroutine BEGIN: called CC=1 SCAR=0.0
23 is_equal strictnull->cons(1), cons (1, strictnull);
24 ok not equal strictnull->cons(1), cons (1, null);
25 # false: `cons` from `FP::List` and `FP::StrictList` are the same
26 # function but it takes the type of their second argument into
27 # consideration.
28  
29  
30 =head1 DESCRIPTION
31  
32 FP::List does not enforce its pairs to only contain pairs or null in
33 their rest (cdr) position. Which means that they may end in something
34 else than a null (and operations encountering these will die with
35 "improper list"). FP::StrictList does, which means that
36 `is_strictlist` only needs to check the head pair to know whether it's
37 a proper list.
38  
39 Also, FP::StrictList maintains the list length within each pair, thus
40 its `length` operation has O(1) complexity instead of O(n) like the
41 `length` from FP::List.
42  
43 Both of these features dictate that a StrictList can't be lazy, since
44 (in a dynamically typed language) it's impossible to know the type
45 that a promise will give without evaluating it, or know the length of
46 the unevaluated tail.
47  
48 Keep in mind that destruction of strict lists requires space on the C
49 stack proportional to their length. You will want to increase the C
50 stack size when handling big strict lists, lest your program will
51 segfault.
52  
53 Currently FP::StrictList mostly only offers method based
54 functionality. It inherits all the methods from FP::List, but only
55 re-exports those basic functions that are basic and don't have "list_"
56 prefixes, and only on demand. The only special functions (and the only
57 ones exported by default) are `strictnull`, `is_strictlist` and
58 `strictlist`. Since StrictList enforcess list structure, methods are
59 guaranteed to always work on the rest field of a pair. Hence, the
60 suggestion is to simply use method calls and `the_method` from
61 `FP::Ops` to pass methods as first class functions.
62  
63 =head1 SEE ALSO
64  
65 Implements: L<FP::Abstract::Sequence>.
66  
67 L<FP::List>, L<FP::Ops>, L<FP::Array>, L<FP::PureArray>
68  
69 =head1 NOTE
70  
71 This is alpha software! Read the status section in the package README
72 or on the L<website|http://functional-perl.org/>.
73  
74 =cut
75  
76 package FP::StrictList;
77 3 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
78 3 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
79 3 ▶use warnings FATAL => 'uninitialized';
Subroutine BEGIN: called CC=1 SCAR=0.0
80 3 ▶use Exporter "import";
Subroutine BEGIN: called CC=1 SCAR=0.0
81  
82 3 our @EXPORT = qw(strictnull is_strictlist strictlist);
83 3 our @EXPORT_OK = qw(
84 cons
85 first second rest car cdr car_and_cdr first_and_rest
86 strictlist_reverse__map_with_length_with_tail
87 strictlist_reverse__map_with_length
88 strictlist_array__reverse__map_with_length
89 strictlist_array__map_with_length
90 );
91 3 our %EXPORT_TAGS = (all => [@EXPORT, @EXPORT_OK]);
92  
93 3 ▶use FP::List;
Subroutine BEGIN: called CC=1 SCAR=0.0
94 3 ▶use Chj::TEST;
Subroutine BEGIN: called CC=1 SCAR=0.0
95 3 ▶use FP::Combinators qw(flip2of3 flip);
Subroutine BEGIN: called CC=1 SCAR=0.0
96 3 ▶use Scalar::Util qw(blessed);
Subroutine BEGIN: called CC=1 SCAR=0.0
97 3 ▶use FP::Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
98  
99 3 package FP::StrictList::List {
100 3 ▶ use FP::Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
101 3 ▶ use Chj::NamespaceCleanAbove;
Subroutine BEGIN: called CC=1 SCAR=0.0
102  
103 4 ▶ sub is_proper_sequence {
Subroutine is_proper_sequence: called CC=1 SCAR=0.0
104 4 1
105 }
106  
107 0 ▶ sub is_list {
Subroutine is_list: not called CC=1 SCAR=6.9
108 0 1
109 }
110  
111 0 ▶ sub strictlist {
Subroutine strictlist: not called CC=2 SCAR=17.9
112 0 ▶ @_ == 1 or fp_croak_arity 1;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or fp_croak_arity(1) 0 0 0
113 0 my $s = shift;
114 0 $s
115 }
116  
117 2 ▶ sub list {
Subroutine list: called CC=2 SCAR=7.1
118 2 ▶ @_ == 1 or fp_croak_arity 1;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or fp_croak_arity(1) 2 0 2
119 2 my $s = shift;
120  
121 # Should it *really* convert to a non-strict list? This is
122 # just a list with the added information that it's proper,
123 # after all; equality should work just fine, in fact the
124 # current FP_Equal_equal for FP::List is not sensitive on
125 # subclasses (looks like has different issues though); *but*,
126 # `equal` itself will short cut to an `undef` if the types are
127 # not the same, so that won't work. XX should this change??
128 2 FP::List::list($s->values)
129 }
130  
131 4 ▶ sub stream {
Subroutine stream: called CC=2 SCAR=7.1
132 4 ▶ @_ == 1 or fp_croak_arity 1;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or fp_croak_arity(1) 4 0 4
133 4 my ($l) = @_;
134  
135 # XX isn't this stupid? Same as above. The current load test
136 # in FP::Abstract::Sequence::t requires this behaviour.
137 4 FP::Stream::stream($l->values)
138 }
139 }
140  
141 3 package FP::StrictList::Null {
142 3 our @ISA = qw(FP::StrictList::List FP::List::Null);
143  
144 3 ▶ use FP::Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
145 3 ▶ use Chj::NamespaceCleanAbove;
Subroutine BEGIN: called CC=1 SCAR=0.0
146  
147 60 ▶ sub pair_namespace {"FP::StrictList::Pair"}
Subroutine pair_namespace: called CC=1 SCAR=0.0
148 3 *null = \&FP::StrictList::strictnull;
149  
150 60 ▶ sub cons {
Subroutine cons: called CC=2 SCAR=7.1
151 60 ▶ @_ == 2 or fp_croak_arity 2;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 2 or fp_croak_arity(2) 60 0 60
152 60 my $s = shift;
153  
154 # different than FP::List::Null::cons in that it needs to set
155 # the length field, too:
156 60 bless [$_[0], $s, 1], $s->pair_namespace
157 }
158  
159 # simply inherit FP_Equal_equal
160  
161 0 ▶ sub FP_Show_show {
Subroutine FP_Show_show: not called CC=1 SCAR=6.9
162 0 my ($s, $show) = @_;
163 0 "strictnull"
164 }
165  
166 3 ▶ use FP::Interfaces;
Subroutine BEGIN: called CC=1 SCAR=0.0
167 3 FP::Interfaces::implemented qw(FP::Abstract::Equal);
168 }
169  
170 3 package FP::StrictList::Pair {
171 3 our @ISA = qw(FP::StrictList::List FP::List::Pair);
172  
173 3 ▶ use FP::Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
174 3 ▶ use Chj::NamespaceCleanAbove;
Subroutine BEGIN: called CC=1 SCAR=0.0
175  
176 3 *null = \&FP::StrictList::strictnull;
177  
178 # represented as blessed [ v, pair-or-null, length]
179  
180 80 ▶ sub cons {
Subroutine cons: called CC=2 SCAR=7.1
181 80 ▶ @_ == 2 or fp_croak_arity 2;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 2 or fp_croak_arity(2) 80 0 80
182 80 my $s = shift;
183 80 bless [$_[0], $s, $$s[2] + 1], ref $s
184 }
185  
186 53 ▶ sub length {
Subroutine length: called CC=1 SCAR=0.0
187 53 $_[0][2]
188 }
189  
190 # simply inherit FP_Equal_equal
191  
192 1 ▶ sub FP_Show_show {
Subroutine FP_Show_show: called CC=1 SCAR=0.0
193 1 my ($s, $show) = @_;
194 1 ("strictlist(" . $s->map($show)->strings_join(", ") . ")")
195 }
196  
197 3 ▶ use FP::Interfaces;
Subroutine BEGIN: called CC=1 SCAR=0.0
198 3 FP::Interfaces::implemented qw(FP::Abstract::Equal);
199 }
200  
201 # nil
202 3 my $null = bless [], "FP::StrictList::Null";
203  
204 60 ▶sub strictnull () {
Subroutine strictnull: called CC=1 SCAR=0.0
Pod undocumented
205  
206 # @_ == 0 or fp_croak_arity 0;
207 # no, is also called as a method
208 60 $null
209 }
210  
211 1 ▶TEST { strictnull->cons(1)->cons(2)->array }
Subroutine __ANON__: called CC=1 SCAR=0.0
212 3 [2, 1];
213  
214 1 ▶TEST { strictnull->length }
Subroutine __ANON__: called CC=1 SCAR=0.0
215 3 0;
216 1 ▶TEST { strictnull->cons(8)->length }
Subroutine __ANON__: called CC=1 SCAR=0.0
217 3 1;
218 1 ▶TEST { strictnull->cons(1)->cons(9)->length }
Subroutine __ANON__: called CC=1 SCAR=0.0
219 3 2;
220  
221 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
222 1 require FP::Show;
223 1 FP::Show::show(cons 1, cons 2, strictnull)
224 }
225 3 "strictlist(1, 2)";
226  
227 24 ▶sub strictlist {
Subroutine strictlist: called CC=2 SCAR=6.9
Pod undocumented
228 24 my $res = strictnull;
229 24 ▶ for (my $i = $#_; $i >= 0; $i--) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i >= 0) 86 24 110
230 86 $res = $res->cons($_[$i]);
231 }
232 24 $res
233 }
234  
235 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
236 2 ▶ strictlist(4, 5)->map (sub { $_[0] + 1 })
Subroutine __ANON__: called CC=1 SCAR=0.0
237 1 }
238 3 cons(5, cons(6, strictnull));
239  
240 46 ▶sub is_strictlist {
Subroutine is_strictlist: called CC=6 SCAR=18.5
Pod undocumented
241 46 ▶ @_ == 1 or fp_croak_arity 1;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or fp_croak_arity(1) 46 0 46
242 46 my ($v) = @_;
243 46 ▶ my $r = blessed($v) // return;
Condition50%1/2
builtin::blessed($v) // (return)
l!l
460
MC/DC0%0/1
builtin::blessed($v) // (return)
builtin::blessed($v)
Truth table50%1/2
A
A= builtin::blessed($v)
Aresult
11
00
244 (
245 46 ▶ $r eq "FP::StrictList::List"
Branch: 1 branch
BranchTrueFalseTotal
$r eq "FP::StrictList::List" or $v->isa("FP::StrictList::List") or $v->isa("FP::Lazy::Promise") and &is_strictlist($v->force) 40 6 46
Condition77%7/9
$r eq 'FP::StrictList::List' || $v->isa('FP::StrictList::List') || $v->isa('FP::Lazy::Promise') && &is_strictlist($v->force)
l!l&&r!l&&!r
4015
$r eq "FP::StrictList::List" or $v->isa("FP::StrictList::List")
l!l&&r!l&&!r
0406
$v->isa("FP::Lazy::Promise") and &is_strictlist($v->force)
!ll&&!rl&&r
501
MC/DC50%2/4
$r eq 'FP::StrictList::List' || $v->isa('FP::StrictList::List') || $v->isa('FP::Lazy::Promise') && &is_strictlist($v->force)
$r eq "FP::StrictList::List" $v->isa("FP::StrictList::List") $v->isa("FP::Lazy::Promise") &is_strictlist($v->force)
Truth table60%3/5
A or B || C and D
A= $r eq "FP::StrictList::List"B= $v->isa("FP::StrictList::List")C= $v->isa("FP::Lazy::Promise")D= &is_strictlist($v->force)
ABCDresult
1XXX1
01XX1
00111
000X0
00100
246 or $v->isa("FP::StrictList::List")
247 or $v->isa("FP::Lazy::Promise") && &is_strictlist(force $v)
248 )
249 }
250  
251 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
252 [
253 1 map { is_strictlist $_ } null,
254 strictnull,
255 cons(1, null),
256 cons(1, strictnull)
257 ]
258 }
259 3 ['', 1, '', 1];
260  
261 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
262 1 ▶ is_strictlist(strictlist(4, 5)->map (sub { $_[0] + 1 }))
Subroutine __ANON__: called CC=1 SCAR=0.0
263 }
264 3 1;
265  
266 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
267 1 ▶ is_strictlist(list(4, 5)->map (sub { $_[0] + 1 }))
Subroutine __ANON__: called CC=1 SCAR=0.0
268 }
269 3 '';
270  
271 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
272 1 require FP::Lazy;
273 1 ▶ is_strictlist(FP::Lazy::lazy { cons 1, strictnull })
Subroutine __ANON__: called CC=1 SCAR=0.0
274 1 }
275 3 1;
276  
277 # heh, can cheat it this way:
278 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=1.2
279 0 ▶ is_strictlist(cons 0, FP::Lazy::lazy { cons 1, cons 2, strictnull })
Subroutine __ANON__: not called CC=1 SCAR=6.9
280 1 }
281 3 '';
282  
283 # interesting, +-luck:
284 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
285 1 require FP::List;
286 1 ▶ FP::List::is_list(cons 0, FP::Lazy::lazy { cons 1, cons 2, strictnull })
Subroutine __ANON__: called CC=1 SCAR=0.0
287 1 }
288 3 1;
289  
290 3 ▶use FP::DumperEqual;
Subroutine BEGIN: called CC=1 SCAR=0.0
291  
292 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
293 1 dumperequal strictnull->cons(1), cons(1, strictnull)
294 }
295 3 1;
296  
297 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
298 1 dumperequal strictnull->cons(1), cons(1, null)
299 }
300 3 '';
301  
302 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
303 1 my $l = strictlist(7, 8, 9)->reverse;
304 1 [is_strictlist($l), $l->car, $l->length]
305 }
306 3 [1, 9, 3];
307  
308 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
309 1 strictlist(7)->reverse_with_tail(8)
310 }
311  
312 # falls back on the default list type since '8' is not a List (a
313 # strictlist would not accept such a value as the tail anyway; hm,
314 # hopefully nobody expects this operation to give an exception?)
315 3 bless([7, 8], 'FP::List::Pair');
316  
317 20 ▶sub make_reverse__map_with_length_with_tail {
Subroutine make_reverse__map_with_length_with_tail: called CC=1 SCAR=0.0
Pod undocumented
318 20 my ($cons) = @_;
319  
320 19 ▶ sub {
Subroutine __ANON__: called CC=3 SCAR=11.0
321 19 ▶ @_ == 3 or fp_croak_arity 3;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 3 or fp_croak_arity(3) 19 0 19
322 19 my ($fn, $l, $tail) = @_;
323 19 my $a;
324 19 ▶ while (!$l->is_null) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($l->is_null) 21 19 40
325 21 my $i = $l->length;
326 21 ($a, $l) = $l->first_and_rest;
327 21 $tail = &$cons(&$fn($a, $i), $tail);
328 }
329 $tail
330 19 }
331 20 }
332  
333 sub strictlist_reverse__map_with_length_with_tail;
334 3 *strictlist_reverse__map_with_length_with_tail
335 = make_reverse__map_with_length_with_tail(\&cons);
336  
337 3 *FP::StrictList::List::reverse__map_with_length_with_tail
338 = flip2of3 \&strictlist_reverse__map_with_length_with_tail;
339  
340 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
341 my $l = strictlist(qw(a b c))
342 1 ▶ ->reverse__map_with_length_with_tail(sub { [@_] }, null);
Subroutine __ANON__: called CC=1 SCAR=0.0
343 1 [is_strictlist($l), $l->array]
344 }
345 3 ['', [[c => 1], [b => 2], [a => 3]]];
346  
347 1 ▶sub strictlist_reverse__map_with_length {
Subroutine strictlist_reverse__map_with_length: called CC=2 SCAR=7.1
Pod undocumented
348 1 ▶ @_ == 2 or fp_croak_arity 2;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 2 or fp_croak_arity(2) 1 0 1
349 1 my ($fn, $l) = @_;
350 1 strictlist_reverse__map_with_length_with_tail($fn, $l, strictnull)
351 }
352  
353 3 *FP::StrictList::List::reverse__map_with_length
354 = flip \&strictlist_reverse__map_with_length;
355  
356 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
357 1 ▶ my $l = strictlist(qw(a b c))->reverse__map_with_length(sub { [@_] });
Subroutine __ANON__: called CC=1 SCAR=0.0
358 1 [is_strictlist($l), $l->array]
359 }
360 3 [1, [[c => 1], [b => 2], [a => 3]]];
361  
362 16 ▶sub strictlist_array__reverse__map_with_length {
Subroutine strictlist_array__reverse__map_with_length: called CC=2 SCAR=7.0
Pod undocumented
363 16 ▶ @_ == 2 or fp_croak_arity 2;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 2 or fp_croak_arity(2) 16 0 16
364 16 my ($fn, $l) = @_;
365 16 my $i = $l->length;
366 make_reverse__map_with_length_with_tail(
367 12 ▶ sub {
Subroutine __ANON__: called CC=1 SCAR=0.0
368 12 my ($v, $ary) = @_;
369  
370 #unshift @$ary, $v; is this faster?:
371 12 $$ary[--$i] = $v;
372 12 $ary
373 }
374 16 )->($fn, $l, []);
375 }
376  
377 3 *FP::StrictList::List::array__reverse__map_with_length
378 = flip \&strictlist_array__reverse__map_with_length;
379  
380 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
381 1 ▶ strictlist(qw(a b c))->array__reverse__map_with_length(sub { [@_] });
Subroutine __ANON__: called CC=1 SCAR=0.0
382 }
383 3 [[c => 1], [b => 2], [a => 3]];
384  
385 1 ▶sub strictlist_array__map_with_length {
Subroutine strictlist_array__map_with_length: called CC=2 SCAR=6.9
Pod undocumented
386 1 ▶ @_ == 2 or fp_croak_arity 2;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 2 or fp_croak_arity(2) 1 0 1
387 1 my ($fn, $l) = @_;
388 1 my $i = 0;
389 1 my $len = $l->length;
390 1 my $ary = [];
391 1 $$ary[$len - 1] = undef; # preallocate array, faster?
392 make_reverse__map_with_length_with_tail(
393 3 ▶ sub {
Subroutine __ANON__: called CC=1 SCAR=0.0
394 3 my ($v, $ary) = @_;
395  
396 #push @$ary, $v;
397 3 $$ary[$i++] = $v;
398 3 $ary
399 }
400 1 )->($fn, $l, $ary);
401 }
402  
403 3 *FP::StrictList::List::array__map_with_length
404 = flip \&strictlist_array__map_with_length;
405  
406 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
407 1 ▶ strictlist(qw(a b c))->array__map_with_length(sub { [@_] });
Subroutine __ANON__: called CC=1 SCAR=0.0
408 }
409 3 [[a => 3], [b => 2], [c => 1]];
410  
411 3 1
« functional_XML/testlazy ↑ Summary lib/Chj/Packages.pm »