File: README

package info (click to toggle)
libsub-recursive-perl 0.05-1
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, stretch
  • size: 128 kB
  • ctags: 5
  • sloc: perl: 60; makefile: 2
file content (253 lines) | stat: -rw-r--r-- 8,464 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
NAME
    Sub::Recursive - Anonymous memory leak free recursive subroutines

SYNOPSIS
        use Sub::Recursive;

        # LEAK FREE recursive subroutine.
        my $fac = recursive {
            my ($n) = @_;
            return 1 if $n < 1;
            return $n * $REC->($n - 1);
        };

        # Recursive anonymous definition in one line, plus invocation.
        print recursive { $_[0] <= 1 ? 1 : $_[0] * $REC->($_[0] - 1) } -> (5);

        # Experimental interface
        use Sub::Recursive qw/ mutually_recursive %REC /;

        my ($odd, $even) = mutually_recursive(
            odd  => sub { $_[0] == 0 ? 0 : $REC{even}->($_[0] - 1) },
            even => sub { $_[0] == 0 ? 1 : $REC{odd }->($_[0] - 1) },
        );

DESCRIPTION
    Recursive closures suffer from a severe memory leak. "Sub::Recursive"
    makes the problem go away cleanly and at the same time allows you to
    write recursive subroutines as expressions and can make them truly
    anonymous. There's no significant speed difference between using
    "recursive" and writing the simpler leaking solution.

  The problem
    The following won't work:

        my $fac = sub {
            my ($n) = @_;
            return 1 if $n < 1;
            return $n * $fac->($n - 1);
        };

    because of the recursive use of $fac which isn't available until after
    the statement. The common fix is to do

        my $fac;
        $fac = sub {
            my ($n) = @_;
            return 1 if $n < 1;
            return $n * $fac->($n - 1);
        };

    Unfortunately, this introduces another problem.

    Because of perl's reference count system, the code above is a memory
    leak. $fac references the anonymous sub which references $fac, thus
    creating a circular reference. This module does not suffer from that
    memory leak.

    There are two more reasons why I don't like to write recursive closures
    like that: (a) you have to first declare it, then assign it thus
    requiring more than a simple expression (b) you have to name it one way
    or another.

  The solution
    This module fixes all those issues. Just change "sub" for "recursive"
    and use "$REC->(...)" for the recursive call:

        use Sub::Recursive;

        my $fac = recursive {
            my ($n) = @_;
            return 1 if $n < 1;
            return $n * $REC->($n - 1);
        };

    It also makes it easy to pass it directly to a subroutine,

        foo(recursive { ... });

    just as any other anonymous subroutine.

EXPORTS
    If no arguments are given to the "use" statement $REC and "recursive"
    are exported. If any arguments are given only those given are exported.
    ":ALL" exports everything exportable.

  $REC - exported by default
    $REC holds a reference to the current subroutine inside subroutines
    created with "recursive". Don't ever touch $REC inside or outside the
    subroutine except for the recursive call.

  "recursive" - exported by default
    "recursive" takes one argument and that's an anonymous sub defined in
    the same package as the call to "recursive" is in. It's prototyped with
    "&" so bare-block calling style is encouraged.

        recursive { ... }

    The return value is an anonymous closure that has "$REC->(...)" working
    in it.

  %REC
    This is an experimental part of the API.

    %REC holds the subroutine references given to &mutually_recursive, with
    the same keys.

    Don't ever touch %REC inside or outside the subroutines except for the
    recursive calls.

  "mutually_recursive"
    This is an experimental part of the API.

    "mutually_recursive" works like "recursive" except it takes a list of
    key/value pairs where the key names are the names used for the keys in
    %REC and the values are the subroutine references. The return values in
    list context are the subroutine references, ordered as given to
    "mutually_recursive".

        my ($odd, $even) = mutually_recursive(
            odd  => sub { $_[0] == 0 ? 0 : $REC{even}->($_[0] - 1) },
            even => sub { $_[0] == 0 ? 1 : $REC{odd }->($_[0] - 1) },
        );

BUGS
    If you follow the rest of the manual you don't have to read this
    section. I include this section anyway to make debugging simpler.

    $REC is a package global and as such there are some gotchas. You won't
    encounter any of these bugs below if you just use

        recursive { ... }

    and don't mention $REC outside of such an expression. In short: it's
    quite unlikely you'll get bitten by any of these bugs.

    "my" and "our"
        Don't declare $REC with "my". That'll make $REC mean your lexical
        variable rather than the global that "Sub::Recursive" uses.

        Don't declare $REC with "our". In particular, problem arise the
        "our" scopes over several packages. If you do

            package Foo;
            use Sub::Recursive;
            our $REC;

            # Below, in the same file:

            package Bar;

            my $fatal = recursive { $REC->() };

        $REC in $fatal will be using the value of $Foo::REC but
        "Sub::Recursive" has no way of knowing that and will think you use
        $Bar::REC.

        If you for some reason need to have $REC declared you can as a last
        resort get around both these issues by fully qualifying $REC to the
        package in which the subroutine is created.

            package Foo;
            use Sub::Recursive;
            my $REC;                                 # Bad.
            my $fatal = recursive { $Foo::REC->() }; # Still works.

    Subroutine reference defined in another package
        This is a really far out edge case.

        If the subroutine reference given to "recursive" is defined in
        another package than the call to "recursive" in it then it won't
        work.

            package Foo;
            my $foo = sub { $REC->() };

            package Bar;
            use Sub::Recursive;
            my $bar = &recursive($foo); # Won't work.

        The subroutine referenced by $foo is using $Foo::REC but "recursive"
        thinks it's using $Bar::REC. Note that you have to circumvent
        prototyping in order to encounter this bug.

        Why you'd want to do this escapes me. Please contact me if you find
        a reason for doing this.

EXAMPLE
    Some algorithms are perhaps best written recursively. For simplicity,
    let's say I have a tree consisting of arrays of array with arbitrary
    depth. I want to map over this data structure, translating every value
    to another. For this I might use

        my $translator = recursive {
            [ map { ref() ? $REC->($_) : $translate{$_} } @{$_[0]} ]
        };

        my $bar = $translator->($foo);

    Now, a tree mapper isn't perhaps the best example as it's a pretty
    general problem to solve, and should perhaps be abstracted but it still
    serves as an example of how this module can be handy.

    A similar but more specialized task would be to find all men who share
    their Y chromosome.

        # A person data structure looks like this.
        my $person = {
            name => ...,
            sons => [ ... ],        # objects like $person
            daughters => [ ... ],   # objects like $person
        };

        my @names = recursive {
            my ($person) = @_;

            return
                $person->{name},
                map $REC->($_), @{$person->{sons}}
        } -> ($forefather);

    This particular example isn't a closure as it doesn't reference any
    lexicals outside itself (and thus could've been written as a named
    subroutine). It's easy enough to think of a case when it would be a
    closure though. For instance if some branches should be excluded. A
    simple flag would solve that.

        my %exclude = ...;

        my @names = recursive {
            my ($person) = @_;

            return if $exclude{$person};

            return
                $person->{name},
                map $REC->($_), @{$person->{sons}}
        } -> ($forefather);

    Hopefully this illustrates how this module allows you to write recursive
    algorithms inline like any other algorithm.

AUTHOR
    Johan Lodin <lodin@cpan.org>

COPYRIGHT
    Copyright 2004-2015 Johan Lodin. All rights reserved.

    This library is free software; you can redistribute it and/or modify it
    under the same terms as Perl itself.

SEE ALSO
    perlref