| 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
| |||||||||||||||||||||||
| 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 | # 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
| |||||||||||||||||||||||
| 45 | 1 | my $sieve; | |||||||||||||||||||||
| 46 | 11 | ▶ | $sieve = func($p_xs) { | ||||||||||||||||||||
|
Subroutine
__ANON__: called CC=3 SCAR=11.3
Branch: 2 branches
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 145 | |||||||||||||||||||||||
| 146 | 13 | ▶ | func primes() { | ||||||||||||||||||||
|
Subroutine
__ANON__: called CC=3 SCAR=11.4
Branch: 2 branches
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 157 | 4 | ▶ | lazy { nonprimes() } | ||||||||||||||||||||
|
Subroutine
__ANON__: called CC=4 SCAR=14.3
Branch: 3 branches
| |||||||||||||||||||||||
| 158 | 4 | ) | |||||||||||||||||||||
| 159 | 4 | ) | |||||||||||||||||||||
| 160 | 2 | } | |||||||||||||||||||||
| 161 | 4 | ▶ | |||||||||||||||||||||
|
Subroutine
__ANON__: called CC=3 SCAR=11.4
Branch: 2 branches
| |||||||||||||||||||||||
| 162 | 9 | ▶ | func nonprimes() { | ||||||||||||||||||||
|
Subroutine
__ANON__: called CC=3 SCAR=11.4
Subroutine
__ANON__: called CC=3 SCAR=11.4
Branch: 4 branches
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 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
| |||||||||||||||||||||||
| 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 \ℙ | ||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||
| 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 | } | ||||||||||||||||||||||