examples/primes

filter: Statementstmt 98.8% 173 / 175 Branchbran 54.3% 50 / 92 Conditioncond n/a MC/DCmcdc n/a Subroutinesub 100% 52 / 52 Podpod n/a totaltotal 86.2% 275 / 319 CC 46 SCAR 9.6
CC
46
Cov
84%
t_merge
5.3
__ANON__
4.2
merge
4.0
CRAP 2.6
« lib/PXML/Util.pm ↑ Summary .htmlgen/FunctionalPerl/Htmlgen/Htmlparse.pm »
1 #!/usr/bin/env perl
2  
3 # Copyright (c) 2015-2019 Christian Jaeger, copying@christianjaeger.ch
4 # This is free software. See the file COPYING.md that came bundled
5 # with this file.
6  
7 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
8 1 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
9 1 ▶use warnings FATAL => 'uninitialized';
Subroutine BEGIN: called CC=1 SCAR=0.0
10  
11 # find modules from functional-perl working directory (not installed)
12 1 ▶use Cwd 'abs_path';
Subroutine BEGIN: called CC=1 SCAR=0.0
13 1 our ($mydir, $myname);
14  
15 1 ▶BEGIN {
Subroutine BEGIN: called CC=3 SCAR=11.7
16 1 ▶ my $location = (-l $0) ? abs_path($0) : $0;
Branch: 1 branch
BranchTrueFalseTotal
-l $0 ? : 0 1 1
17 1 ▶ $location =~ /(.*?)([^\/]+?)_?\z/s or die "?";
Branch: 1 branch
BranchTrueFalseTotal
$location =~ m[(.*?)([^/]+?)_?\z]s or die "?" 1 0 1
18 1 ($mydir, $myname) = ($1, $2);
19 }
20 1 ▶use lib "$mydir/../lib";
Subroutine BEGIN: called CC=1 SCAR=0.0
21  
22 # gracefully fail when run as a test and Method::Signatures is not
23 # available
24 1 ▶use Chj::TEST use => 'Method::Signatures';
Subroutine BEGIN: called CC=1 SCAR=0.0
Subroutine BEGIN: called CC=1 SCAR=0.0
25 1 ▶use Chj::Backtrace;
Subroutine BEGIN: called CC=1 SCAR=0.0
26 1 ▶use FP::List ":all";
Subroutine BEGIN: called CC=1 SCAR=0.0
27 1 ▶use FP::Ops ":all";
Subroutine BEGIN: called CC=1 SCAR=0.0
28 1 ▶use FP::Lazy ":all";
Subroutine BEGIN: called CC=1 SCAR=0.0
29 1 ▶use FP::Stream ":all";
Subroutine BEGIN: called CC=1 SCAR=0.0
30  
31 # Another translation of (a) Haskell example(s) (see also `fibs`).
32  
33 # ------------------------------------------------------------------
34 # (A) From https://www.haskell.org/?new :
35  
36 # Note that this is *not* an efficient algorithm to calculate primes;
37 # see https://news.ycombinator.com/item?id=9052514 and the solution
38 # further down in this file.
39  
40 # primes = sieve [2..]
41 # where sieve (p:xs) =
42 # p : sieve [x | x <- xs, x `mod` p /= 0]
43  
44 1 ▶func primes_naive1() {
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine primes_naive1: called CC=2 SCAR=7.1
Branch: 1 branch
BranchTrueFalseTotal
if scalar @_ > 0 0 1 1
45 1 my $sieve;
46 11 ▶ $sieve = func($p_xs) {
Subroutine __ANON__: called CC=3 SCAR=11.3
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 11 11
if scalar @_ > 1 0 11 11
47 11 my ($p, $xs) = first_and_rest $p_xs;
48 10 ▶ lazy {
Subroutine __ANON__: called CC=1 SCAR=0.1
49 cons $p, &$sieve(
50 80 ▶ stream_filter func($x)
Subroutine __ANON__: called CC=3 SCAR=11.4
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 80 80
if scalar @_ > 1 0 80 80
51 80 {
52 $x % $p != 0
53 10 },
54 $xs
55 )
56 1 }
57 };
58  
59 1 # XXX Weakened($sieve)
60 $sieve->(stream_iota 2)
61 }
62  
63 # or simpler, by lifting `sieve` to the toplevel:
64 1 ▶ 
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine primes_naive: called CC=2 SCAR=7.0
Branch: 1 branch
BranchTrueFalseTotal
if scalar @_ > 0 0 1 1
65 1 func primes_naive() {
66 sieve(stream_iota 2)
67 }
68 1 ▶ 
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine sieve: called CC=3 SCAR=11.2
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 11 11
if scalar @_ > 1 0 11 11
69 11 func sieve($p_xs) {
70 10 ▶ my ($p, $xs) = first_and_rest $p_xs;
Subroutine __ANON__: called CC=1 SCAR=0.1
71 lazy {
72 80 ▶ cons $p, sieve(
Subroutine __ANON__: called CC=3 SCAR=11.4
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 80 80
if scalar @_ > 1 0 80 80
73 80 stream_filter func($x)
74 {
75 10 $x % $p != 0
76 },
77 $xs
78 11 )
79 }
80 1 ▶}
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine t_primes: called CC=3 SCAR=11.2
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 3 3
if scalar @_ > 1 0 3 3
81 3 ▶ 
Subroutine __ANON__: called CC=1 SCAR=0.0
82 3 func t_primes($primes) {
83 TEST { stream_to_array stream_take &$primes(), 10 }
84 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
85 1 }
86 1  
87 t_primes \&primes_naive1;
88 t_primes \&primes_naive;
89  
90 # ------------------------------------------------------------------
91 # (B) Now let's use a better algorithm:
92  
93 # http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell)
94  
95 # merge :: (Ord a) => [a] -> [a] -> [a]
96 # merge xs@(x:xt) ys@(y:yt) =
97 # case compare x y of
98 # LT -> x : (merge xt ys)
99 # EQ -> x : (merge xt yt)
100 # GT -> y : (merge xs yt)
101 #
102 # diff :: (Ord a) => [a] -> [a] -> [a]
103 # diff xs@(x:xt) ys@(y:yt) =
104 # case compare x y of
105 # LT -> x : (diff xt ys)
106 # EQ -> diff xt yt
107 # GT -> diff xs yt
108 #
109 # primes, nonprimes :: [Integer]
110 # primes = [2, 3, 5] ++ (diff [7, 9 ..] nonprimes)
111 # nonprimes = foldr1 f $ map g $ tail primes
112 # where
113 # f (x:xt) ys = x : (merge xt ys)
114 1 ▶# g p = [ n * p | n <- [p, p + 2 ..]]
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine merge: called CC=4 SCAR=13.9
Branch: 3 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 25 25
unless scalar @_ > 1 0 25 25
if scalar @_ > 2 0 25 25
115 18 ▶ 
Subroutine __ANON__: called CC=3 SCAR=11.0
116 18 func merge($xs, $ys) {
117 18 lazy {
118 my ($x, $xt) = first_and_rest $xs;
119 18 ▶ my ($y, $yt) = first_and_rest $ys;
Branch: 2 branches
BranchTrueFalseTotal
if ($x < $y) { } 10 8 18
elsif ($x == $y) { } 2 6 8
120 10  
121 if ($x < $y) {
122 2 cons($x, merge($xt, $ys))
123 } elsif ($x == $y) {
124 6 cons($x, merge($xt, $yt))
125 } else {
126 cons($y, merge($xs, $yt))
127 25 }
128 }
129 1 ▶}
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine diff: called CC=4 SCAR=13.9
Branch: 3 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 61 61
unless scalar @_ > 1 0 61 61
if scalar @_ > 2 0 61 61
130 56 ▶ 
Subroutine __ANON__: called CC=3 SCAR=11.0
131 56 func diff($xs, $ys) {
132 56 lazy {
133 my ($x, $xt) = first_and_rest $xs;
134 56 ▶ my ($y, $yt) = first_and_rest $ys;
Branch: 2 branches
BranchTrueFalseTotal
if ($x < $y) { } 28 28 56
elsif ($x == $y) { } 24 4 28
135 28  
136 if ($x < $y) {
137 24 cons($x, diff($xt, $ys))
138 } elsif ($x == $y) {
139 4 diff($xt, $yt)
140 } else {
141 diff($xs, $yt)
142 61 }
143 }
144 1 ▶}
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine primes: called CC=2 SCAR=7.1
Branch: 1 branch
BranchTrueFalseTotal
if scalar @_ > 0 0 3 3
145  
146 13 ▶func primes() {
Subroutine __ANON__: called CC=3 SCAR=11.4
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 13 13
if scalar @_ > 1 0 13 13
147 13 stream_append(
148 array_to_list([2, 3, 5]),
149 diff(
150 stream_map(
151 2 ▶ func($x)
Subroutine __ANON__: called CC=1 SCAR=0.0
152 {
153 3 $x * 2 + 7
154 },
155 stream_iota
156 1 ▶ ),
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine nonprimes: called CC=2 SCAR=7.1
Branch: 1 branch
BranchTrueFalseTotal
if scalar @_ > 0 0 2 2
157 4 ▶ lazy { nonprimes() }
Subroutine __ANON__: called CC=4 SCAR=14.3
Branch: 3 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 4 4
unless scalar @_ > 1 0 4 4
if scalar @_ > 2 0 4 4
158 4 )
159 4 )
160 2 }
161 4 ▶ 
Subroutine __ANON__: called CC=3 SCAR=11.4
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 4 4
if scalar @_ > 1 0 4 4
162 9 ▶func nonprimes() {
Subroutine __ANON__: called CC=3 SCAR=11.4
Subroutine __ANON__: called CC=3 SCAR=11.4
Branch: 4 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 9 9
if scalar @_ > 1 0 9 9
unless scalar @_ > 0 0 9 9
if scalar @_ > 1 0 9 9
163 4 my $f = func($x_xt, $ys) {
164 2 my ($x, $xt) = first_and_rest $x_xt;
165 2 cons $x, merge($xt, $ys)
166 };
167 my $g = func($p) {
168 stream_map(func($n) { $n * $p }, stream_map(func($q) { $p + $q * 2 },
169 stream_iota));
170 };
171 stream_foldr1 $f, stream_map $g, rest primes
172 1 ▶}
Subroutine __ANON__: called CC=1 SCAR=0.1
173  
174 10 ▶# And tests...
Subroutine __ANON__: called CC=3 SCAR=11.4
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 10 10
if scalar @_ > 1 0 10 10
175 10  
176 # from http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell) :
177 1  
178 TEST {
179 stream_to_array stream_take(
180 diff(
181 stream_iota(1),
182 1 stream_map func($x)
183 {
184 1 ▶ $x * 2
Subroutine __ANON__: called CC=1 SCAR=0.1
185 },
186 15 ▶ stream_iota(1)
Subroutine __ANON__: called CC=3 SCAR=11.4
Branch: 2 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 15 15
if scalar @_ > 1 0 15 15
187 15 ),
188 10
189 1 )
190 }
191 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
192  
193 TEST {
194 1 stream_to_array stream_take(
195 diff(
196 stream_iota(10),
197 stream_map func($x)
198 1 ▶ {
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine t_merge: called CC=5 SCAR=16.6
Branch: 4 branches
BranchTrueFalseTotal
unless scalar @_ > 0 0 3 3
unless scalar @_ > 1 0 3 3
unless scalar @_ > 2 0 3 3
if scalar @_ > 3 0 3 3
199 3 $x * 2
200 },
201 stream_iota(1)
202 ),
203 1 ▶ 10
Subroutine __ANON__: called CC=1 SCAR=0.0
204 1 )
205 }
206 1 ▶[11, 13, 15, 17, 19, 21, 23, 25, 27, 29];
Subroutine __ANON__: called CC=1 SCAR=0.0
207 1  
208 # merge:
209 1 ▶ 
Subroutine __ANON__: called CC=1 SCAR=0.0
210 1 func t_merge($a1, $a2, $n) {
211 stream_to_array stream_take(
212 merge(array_to_stream($a1), array_to_stream($a2),), $n);
213 }
214 1  
215 TEST { t_merge [1, 2, 99], [3, 4, 99], 4 }
216 [1, 2, 3, 4];
217  
218 TEST { t_merge [1, 3, 99], [3, 4, 99], 4 }
219 [1, 3, 4, 99]; # not [1,3,3,4]
220  
221 TEST { t_merge [1, 3, 99], [2, 4, 99], 4 }
222 [1, 2, 3, 4];
223  
224 # and the whole thing:
225  
226 1 ▶t_primes \&primes;
Branch: 1 branch
BranchTrueFalseTotal
perhaps_run_tests("main") or do { require FP::Repl; FP::Repl::repl() } 1 0 1
227 0  
228 0 # Benchmarking:
229 # [[times], stream_ref (primes_naive, 1000), [times]] -> 8.86 sec user time
230 # also, the above prints many deep recursion warnings (why exactly?)
231 # [[times], stream_ref (primes, 1000), [times]] -> 0.78 sec user time
232  
233 # [[times], stream_ref (primes, 10000), [times]] -> 17.46 sec user time
234 # (versus ghc compiled code which takes 0.1 sec for the same)
235  
236 # ------------------------------------------------------------------
237 # for the test suite:
238 perhaps_run_tests "main" or do {
239 require FP::Repl;
240 FP::Repl::repl();
241 }
« lib/PXML/Util.pm ↑ Summary .htmlgen/FunctionalPerl/Htmlgen/Htmlparse.pm »