examples/fibs

filter: Statementstmt 98.1% 103 / 105 Branchbran 66.6% 8 / 12 Conditioncond n/a MC/DCmcdc n/a Subroutinesub 100% 39 / 39 Podpod n/a totaltotal 96.1% 150 / 156 CC 6 SCAR 2.9
CC
6
Cov
95%
BEGIN
3.2
_fib
3.0
_fibonacci
2.1
CRAP 1.3
« .htmlgen/FunctionalPerl/Htmlgen/MarkdownPlus.pm ↑ Summary lib/FP/noLazy.pm »
1 #!/usr/bin/env perl
2  
3 # Copyright (c) 2015-2020 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 1 ▶use Chj::TEST use => "PadWalker";
Subroutine BEGIN: called CC=1 SCAR=0.0
Subroutine BEGIN: called CC=1 SCAR=0.0
23 1 ▶use FP::List ":all";
Subroutine BEGIN: called CC=1 SCAR=0.0
24 1 ▶use FP::Ops ":all";
Subroutine BEGIN: called CC=1 SCAR=0.0
25 1 ▶use FP::Lazy ":all";
Subroutine BEGIN: called CC=1 SCAR=0.0
26 1 ▶use FP::Stream ":all";
Subroutine BEGIN: called CC=1 SCAR=0.0
27 1 ▶use FP::BigInt;
Subroutine BEGIN: called CC=1 SCAR=0.0
28  
29 1 ▶use Chj::Backtrace;
Subroutine BEGIN: called CC=1 SCAR=0.0
30  
31 # fibs :: [Integer]
32 # fibs = 1:1:zipWith (+) fibs (tail fibs)
33 # fib n = fibs!!n
34  
35 1 our $fibs;
36 $fibs = cons bigint(1), cons bigint(1),
37 1 ▶ lazy { stream_zip_with \&add, Keep($fibs), rest $fibs };
Subroutine __ANON__: called CC=1 SCAR=0.0
38  
39 2 ▶sub fib {
Subroutine fib: called CC=1 SCAR=0.0
40 2 my ($n) = @_;
41 2 stream_ref Keep($fibs), $n
42 }
43  
44 # The above code creates the sequence only once per program run and
45 # then keeps it around in the $fibs global; there's no provision to
46 # set $fibs again thus it has to be protected with Keep() from being
47 # deleted. While this works, and is arguably efficient since multiple
48 # calls to fib() do not need to recalculate the stream, it also means
49 # that the whole stream up to the highest $n ever calculated are kept
50 # in memory until program exit.
51  
52 # Here is an alternative definition that doesn't keep the stream tied
53 # to a global, but instead returns a fresh copy each time fibs() is
54 # called:
55  
56 2 ▶sub fibs {
Subroutine fibs: called CC=1 SCAR=0.0
57 2 my $fibs;
58 $fibs = cons bigint(1), cons bigint(1),
59 2 ▶ lazy { stream_zip_with \&add, $fibs, rest $fibs };
Subroutine __ANON__: called CC=1 SCAR=0.0
60 2 $fibs
61 }
62  
63 # Note that while it creates a reference cycle, it won't leak, as the
64 # cycle is broken by stream_zip_with weakening its arguments, which we
65 # don't protect here (we do not use a Keep() wrapper).
66  
67 # Here's a variant that relies on self-referencing the subroutine (a
68 # package variable) instead of mutating a lexical variable:
69  
70 110 ▶sub fibs2 {
Subroutine fibs2: called CC=1 SCAR=0.0
71 108 ▶ cons bigint(1), cons bigint(1), lazy {
Subroutine __ANON__: called CC=1 SCAR=0.0
72 108 my $fibs = fibs2();
73 108 stream_zip_with \&add, $fibs, rest $fibs
74 }
75 110 }
76  
77 # But it's less efficient: it recalculates parts multiple times, as
78 # can be seen with CPU timings, or with the number of times that it
79 # calls \&add; you can check for the latter by replacing \&add with
80 # \&counting_add and look at $addcount before and after the
81 # calculation:
82  
83 1 my $addcount = 0;
84  
85 3239 ▶sub counting_add {
Subroutine counting_add: called CC=1 SCAR=0.0
86 3239 $addcount++;
87 3239 $_[0] + $_[1]
88 }
89  
90 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
91 1 $addcount = 0;
92  
93 # local *add = \&counting_add;
94  
95 # to avoid redefinition warnings, use the glob (alternatively
96 # disable the warning):
97 1 local *add = *counting_add;
98 1 [fibs->ref(80), $addcount]
99 }
100 1 [bigint('37889062373143906'), 79];
101  
102 1 ▶TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
103 1 $addcount = 0;
104 1 local *add = *counting_add;
105 1 [fibs2->ref(80), $addcount]
106 }
107 1 [bigint('37889062373143906'), 3160]; # 3160 == 79*80/2
108  
109 # This is because the recursive call to `fibs2` is creating a second,
110 # independently calculated sequence, which itself at the second
111 # position again is creating another (third), independently calculated
112 # sequence, etc. We want to calculate the same sequence only once,
113 # which `fibs` achieves.
114  
115 1 ▶TEST { Keep($fibs)->take(10)->map(\&stringify)->array }
Subroutine __ANON__: called CC=1 SCAR=0.0
116 1 [1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
117  
118 1 ▶TEST { fib 30 }
Subroutine __ANON__: called CC=1 SCAR=0.0
119 1 bigint(1346269);
120  
121 1 ▶TEST { fibs->ref(30) }
Subroutine __ANON__: called CC=1 SCAR=0.0
122 1 bigint(1346269);
123  
124 1 ▶TEST { fibs2->ref(30) }
Subroutine __ANON__: called CC=1 SCAR=0.0
125 1 bigint(1346269);
126  
127 # ------------------------------------------------------------------
128  
129 # Alright, so there are not only the stupidly slow naive recursive and
130 # the above widespread O(n) algorithm (as well as the fibs2 variant
131 # which is inbetween), but also better ones:
132  
133 # http://www.nayuki.io/page/fast-fibonacci-algorithms
134  
135 # Thus if we wanted something really fast, we'd diverge from standard
136 # examples and instead implement the following:
137  
138 # http://www.nayuki.io/res/fast-fibonacci-algorithms/fastfibonacci.hs
139  
140 # (we're adding this for completeness and some perspective on the
141 # topic of performance, not as a demo of functional-perl)
142  
143 2168 ▶sub _fib {
Subroutine _fib: called CC=3 SCAR=11.0
144 2168 my ($n) = @_;
145 2168 ▶ ($n == 0) ? (bigint(0), bigint(1)) : do {
Branch: 1 branch
BranchTrueFalseTotal
$n == 0 ? : 2 2166 2168
146 1 ▶ no warnings 'recursion';
Subroutine BEGIN: called CC=1 SCAR=0.0
147 2166 my ($a, $b) = _fib($n / 2);
148 2166 my $c = $a * ($b * 2 - $a);
149 2166 my $d = $a * $a + $b * $b;
150 2166 ▶ ($n % 2) == 0 ? ($c, $d) : ($d, $c + $d)
Branch: 1 branch
BranchTrueFalseTotal
$n % 2 == 0 ? : 2154 12 2166
151 };
152 }
153  
154 2 ▶sub _fibonacci {
Subroutine _fibonacci: called CC=2 SCAR=7.2
155 2 my ($n) = @_;
156 2 ▶ ($n >= 0) ? (_fib $n)[0] : die "n < 0";
Branch: 1 branch
BranchTrueFalseTotal
$n >= 0 ? : 2 0 2
157 }
158  
159 2 ▶sub fibonacci {
Subroutine fibonacci: called CC=1 SCAR=0.0
160 2 my ($n) = @_;
161 2 _fibonacci($n + 1)
162 }
163  
164 1 ▶TEST { fibonacci 30 }
Subroutine __ANON__: called CC=1 SCAR=0.0
165 1 bigint(1346269);
166  
167 # With bigger inputs:
168  
169 1 ▶use Chj::time_this;
Subroutine BEGIN: called CC=1 SCAR=0.0
170  
171 1 ▶my $a = lazy {
Subroutine __ANON__: called CC=1 SCAR=0.0
172 1 ▶ time_this { fib(1400) } "fib"
Subroutine __ANON__: called CC=1 SCAR=0.0
173 1 };
174 1 ▶my $b = lazy {
Subroutine __ANON__: called CC=1 SCAR=0.0
175 1 ▶ time_this { fibonacci(1400) } "fibonacci"
Subroutine __ANON__: called CC=1 SCAR=0.0
176 1 };
177  
178 1 ▶TEST { FORCE($a) . "" }
Subroutine __ANON__: called CC=1 SCAR=0.0
179 1 "27682097123729003105677626449505746191732174241149462650923690069660131404640833946850969379619575819465246124164576690629246144675379393573106211382631761722558988596174542778374560842981861789646519389087106627252306193512024601313327314953992743800841043870569935864482663072626507327493026";
180  
181 1 ▶TEST { FORCE($b) } $a;
Subroutine __ANON__: called CC=1 SCAR=0.0
182  
183 1 ▶perhaps_run_tests "main" or do {
Branch: 1 branch
BranchTrueFalseTotal
perhaps_run_tests("main") or do { require FP::Repl::Trap; FP::Repl::repl() } 1 0 1
184 0 require FP::Repl::Trap;
185 0 FP::Repl::repl();
186 };
« .htmlgen/FunctionalPerl/Htmlgen/MarkdownPlus.pm ↑ Summary lib/FP/noLazy.pm »