view release on metacpan or  search on metacpan

examples/fibs  view on Meta::CPAN

#!/usr/bin/env perl

# Copyright (c) 2015-2020 Christian Jaeger, copying@christianjaeger.ch
# This is free software. See the file COPYING.md that came bundled
# with this file.

use strict;
use warnings;
use warnings FATAL => 'uninitialized';

# find modules from functional-perl working directory (not installed)
use Cwd 'abs_path';
our ($mydir, $myname);

BEGIN {
    my $location = (-l $0) ? abs_path($0) : $0;
    $location =~ /(.*?)([^\/]+?)_?\z/s or die "?";
    ($mydir, $myname) = ($1, $2);
}
use lib "$mydir/../lib";

use Chj::TEST use => "PadWalker";
use FP::List ":all";
use FP::Ops ":all";
use FP::Lazy ":all";
use FP::Stream ":all";
use FP::BigInt;

use Chj::Backtrace;

# fibs :: [Integer]
# fibs = 1:1:zipWith (+) fibs (tail fibs)
# fib n = fibs!!n

our $fibs;
$fibs = cons bigint(1), cons bigint(1),
    lazy { stream_zip_with \&add, Keep($fibs), rest $fibs };

sub fib {
    my ($n) = @_;
    stream_ref Keep($fibs), $n
}

# The above code creates the sequence only once per program run and
# then keeps it around in the $fibs global; there's no provision to
# set $fibs again thus it has to be protected with Keep() from being
# deleted. While this works, and is arguably efficient since multiple
# calls to fib() do not need to recalculate the stream, it also means
# that the whole stream up to the highest $n ever calculated are kept
# in memory until program exit.

# Here is an alternative definition that doesn't keep the stream tied
# to a global, but instead returns a fresh copy each time fibs() is
# called:

sub fibs {
    my $fibs;
    $fibs = cons bigint(1), cons bigint(1),
        lazy { stream_zip_with \&add, $fibs, rest $fibs };
    $fibs
}

# Note that while it creates a reference cycle, it won't leak, as the
# cycle is broken by stream_zip_with weakening its arguments, which we
# don't protect here (we do not use a Keep() wrapper).

# Here's a variant that relies on self-referencing the subroutine (a
# package variable) instead of mutating a lexical variable:

sub fibs2 {
    cons bigint(1), cons bigint(1), lazy {
        my $fibs = fibs2();
        stream_zip_with \&add, $fibs, rest $fibs
    }
}

# But it's less efficient: it recalculates parts multiple times, as
# can be seen with CPU timings, or with the number of times that it
# calls \&add; you can check for the latter by replacing \&add with
# \&counting_add and look at $addcount before and after the
# calculation: