| 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
| |||||||||||
| 17 | 1 | ▶ | $location =~ /(.*?)([^\/]+?)_?\z/s or die "?"; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 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
| |||||||||||
| 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
| |||||||||||
| 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
| |||||||||||
| 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
| |||||||||||
| 184 | 0 | require FP::Repl::Trap; | |||||||||
| 185 | 0 | FP::Repl::repl(); | |||||||||
| 186 | }; | ||||||||||