NAME

FP::List - singly linked (purely functional) lists

SYNOPSIS

    use FP::Div qw(inc square); use FP::Ops qw(div); use FP::Equal 'is_equal';
    use FP::Combinators qw(flip);
    use FP::Predicates qw(is_pure);

    use FP::List ':all';

    my $l = cons("H", cons("e", cons("l", cons("l", cons("o", null)))));
    is_equal $l, list("H", "e", "l", "l", "o");
    is_equal list_to_string($l), "Hello";
    ok is_pure $l;

    is_equal list(1,2,3)->map(sub{ $_[0] * $_[0] }),
             list(1,4,9);
    is_equal list(1,2,3)->map(\&square)->array,
             [1,4,9];

    is list(qw(a b c))->first, "a";
    is_equal list(qw(a b c))->rest,
             list("b", "c");

    is list(1,2,3,4)->sum, 1+2+3+4;
    is list(1,2,3,4)->product, 1*2*3*4;
    is list(2,4,6)->reduce(flip \&div), 2/4/6;
    is list(2,4,6)->reduce_right(flip \&div), 2/4/6;
    # etc.

    # The `cons` function checks whether its second argument is an object
    # with a `cons` method, if so, it invokes it, otherwise it creates an
    # FP::List::Pair object holding both values (there's also a `pair`
    # function that doesn't check for a method and always directly
    # creates the pair)
    is cons("a","b")->rest, "b";
    is cons("a","b")->cdr, "b";
    is list(5,6,7)->caddr, 7;

DESCRIPTION

Purely functional (immutable) singly linked lists are interesting in functional programs because they can be extended and walked directly via recursion. They do not offer efficient random access (O(len)), also there is a constant space overhead and access indirection compared to arrays. They are most appropriate for maintaining smaller but frequently updated chains, for example maintaining a link chain to parent scopes while recursing into a tree datastructure (which, if it's a pure data structure, doesn't have parent links built into it).

FP::List does not enforce its pairs to only contain pairs or null in their rest (cdr) position. Which means that they may end in something else than a null (and operations encountering these will die with "improper list"). The `show` function (or the `:s` mode in `FP::Repl::Repl`) displays those as `improper_list`, e.g.:

 # a normal, 'proper', list:
 is_equal cons(5, cons(6, cons(7, null))), list(5, 6, 7);

 # an 'improper' list:
 is_equal cons(5, cons(6, 7)), improper_list(5, 6, 7);

Note that destruction of linked lists in Perl requires space on the C stack proportional to their length. You should either avoid dropping a long linked list at once (dropping it one cell at a time intermixed with doing any other operation avoids the issue), or will want to increase the C stack size limit, lest your program will segfault.

PURITY

`FP::List` cells are created to be immutable by default, which enforces the functional purity of the API. This can be disabled by setting `$FP::List::immutable` to false when creating lists; slots in pairs can then be mutated. Only ever use this during development (), if at all; if you need to update sequences in the middle efficiently , use another data structure (like FP::Vec).

In either case, `FP::List` implements `FP::Abstract::Pure` (`is_pure` from `FP::Predicates` returns true).

NAMING

Most functional programming languages are using either the `:` or `::` operator to prepend an item to a list. The name `cons` comes from lisps, where it's the basic (lisp = list processing!) "construction" function.

Cons cells (pairs) in lisps can also be used to build other data structures than lists: they don't enforce the rest slot to be a pair or null. Lisps traditionally use `car` and `cdr` as accessors for the two fields, to respect this feature, and also because 'a' and 'd' combine easily into composed names like `caddr`. This library offers `car` and `cdr` as aliases to `first` and `rest`.

Some languages call the accessors `head` and `tail`, but `tail` would conflict with `Sub::Call::Tail`, hence those are not used here.

SEE ALSO

Implements: FP::Abstract::Pure, FP::Abstract::Sequence, FP::Abstract::Equal, FP::Abstract::Show

FP::Stream, FP::Array, FP::PureArray

NOTE

This is alpha software! Read the status section in the package README or on the website.