Stevan Little

NAME

fp - a library for programming in a functional style

SYNOPSIS

  use fp;
  
  # filter out all be the even numbers
  filter(function { is_even(head(@_)) }, range(1, 100));
  
  # split the string, get unique list out of it
  # then get that list's length, and then check
  # that is equal to 26 
  is_equal_to(len(unique(explode("the quick brown fox jumped over the lazy dog and ran on down the road"))), 26);
  
  # the sum of the numbers 1 through 10 is 55
  is_equal_to(sum(range(1, 10)), 55);

DESCRIPTION

This module is an experiment in functional programming in perl. It uses nothing but a combination of; subroutines, the @_ array and a few built in operators to implement a style of functional programming.

None of the code above is all that interesting until you consider that at no point was variable assignment (=), if statements, or non-recursive iteration used. Although, do be entirely honest, there is actually two times when the = operator is used in the entire module. The first time is to assign the module's version, the second time is within the import routine, but those are really not parts of this library and really more infastructure anyway.

Variable assignment is not utilized, instead the contents of the @_ argument array are accessed/manipulated and passed along as the return of values from functions. Recursion is the only means of iteration, we do not use any of perl's built in iteration mechanisms (for, foreach, while, etc.). All functions are non-destructive to their inputs, and just about everything returns an array of some sort, so function call chaining works quite well. It operates only on flat lists only, since perl will flatten any arrays given as arguments.

This code is also written without side-effects. Meaning that each function is written to express an algorithm that produces its result rather than produce its result through the coercion of side-effects. Here is an example of what i mean, using even/odd predicate functions.

with side effects:

  sub is_even { (($_[0] % 2) == 0); }
  sub is_odd { (($_[0] % 2) != 0); }

without side efffects:

  sub is_even { ($_[0] <= 0) ? true : is_odd($_[0] - 1); }      
  sub is_odd { ($_[0] <= 0) ? false : is_even($_[0] - 1); }

The side-effect version uses the side effects of the mathematical calculation of (x % 2) to test if x is even or odd. Where the side-effect free version uses mutual recursion to continually subtract 1 from x until it reaches 0, at which point it will be either odd or even based upon the function it stops in.

FUNCTIONS

constants

true

Represents a true value.

false

Represents a false value.

nil

Represents an empty list.

constructors

list (@items)

Constructs a list out of the elements passed to it.

range ($lower, $upper)

Constructs a list spanning from the first argument to the second argument.

function (&block)

Constructs a function.

list operations

len (@list)

Returns the length of the list.

rev (@list)

Reverses the list given to it.

append ($element, @list)

Appends an element to a list.

prepend ($element, @list)

Prepends an element to a list.

head (@list)

Returns the element at the head of the list.

tail (@list)

Returns the list, less the first element.

nth ($n, @list)

Returns the nth element of the list.

first (@list)

Returns the first element of the list.

second (@list)

Returns the second element of the list.

third (@list)

Returns the third element of the list.

fourth (@list)

Returns the fourth element of the list.

fifth (@list)

Returns the fifth element of the list.

sixth (@list)

Returns the sixth element of the list.

reduce

Reduce a list by removing the head of the list.

end (@list)

Returns the element at the end of the list.

is_empty (@list)

Returns true if the given list is empty (equal to nil).

is_not_empty (@list)

Returns true if the given list is not empty (equal to nil).

member ($element, @list)

Tests for the existence of a given element in the list.

filter (&function, @list)

Filter a list with a predicate function.

apply (&function, @list)

Apply a function to each element in a list.

slice_by ($number)

Divides a number up into its individual numeric components.

explode ($string)

Divides a string into characters.

concat (@list_of_strings)

Given a list of strings, it combines them into a single string.

sum (@list_of_numbers)

Sums a list of numbers

product (@list_of_numbers)

Returns the product of all the elements in the list.

combine (@list, @list)

Combine two lists into one.

unique (@list)

Only return the unique elements of a given list.

unique_combine (@list, @list)

Returns a unique list of two lists.

unique_prepend ($element, @list)

Prepends the element to the list, while retaining uniqueness.

unique_append ($element, @list)

Appends the element to the list, while retaining uniqueness.

set operations

union (@list, @list)

Returns a union of two lists.

adjoin (@list, @list)

Adjoin a set with mutliple new elements

intersection (@list, @list)

Intersection of two sets is a list of all elements found in both.

predicates

is_even ($number)

This along with its mutually recursive mate is_odd will determine if a given number is even.

is_odd ($number)

This along with its mutually recursive mate is_even will determine if a given number is odd.

is_equal_to ($element, $element)

This attempts to determine if two elements are equal.

is_not_equal_to ($element, $element)

This attempts to determine if two elements are not equal.

is_digit ($element)

This attempts to discern if a given element is a digit.

is_whitespace ($element)

This attempts to discern if a given element is whitespace.

is_alpha ($element)

This attempts to discern if a given element is an alphabetical character.

TO DO

This library is missing two set operations, because I cannot yet figure out a way to accomplish them without resorting to assignment statements.

Differnce of two sets is a list of elements from the first lists that are not contained in the second list. This cannot be implemented because of perl's auto-list-flatening.
xor of two sets is a list of elements not found in both. This cannot be implemented because of perl's auto-list-flatening.

BUGS

None that I am currently aware of. Of course, that does not mean that they do not exist, so if you find a bug, let me know, and I will be sure to fix it.

CODE COVERAGE

I use Devel::Cover to test the code coverage of my tests, below is the Devel::Cover report on this module test suite.

 ---------------------------- ------ ------ ------ ------ ------ ------ ------
 File                           stmt   bran   cond    sub    pod   time  total
 ---------------------------- ------ ------ ------ ------ ------ ------ ------
 fp.pm                         100.0   88.0    n/a  100.0  100.0   69.7   97.1
 fp/functionals.pm             100.0  100.0    n/a  100.0  100.0    0.3  100.0
 fp/lambda.pm                  100.0    n/a    n/a  100.0    n/a   29.7  100.0
 fp/lambda/utils.pm            100.0    n/a    n/a  100.0  100.0    0.3  100.0
 ---------------------------- ------ ------ ------ ------ ------ ------ ------
 Total                         100.0   89.3    n/a  100.0  100.0  100.0   98.7
 ---------------------------- ------ ------ ------ ------ ------ ------ ------

SEE ALSO

This module was inspired by reading one to many books about functional programming. Here is a short list of those books, all of which I recommend reading if you are insterested in such things.

ANSI Common Lisp - Paul Graham

This was really my first introduction to LISP and functional programming as a style/paradigm. It is an both informative and entertaining. Not to be missed, is Paul's web site http://www.paulgraham.com, it has many a good article on it.

Functional Programming and its Applications

This is a collection of essays for a advanced course in functional programming given at Newcastle Univeristy in the summer of 1981. Some of the essay highlights are one by Gerald Jay Susseman (of MIT fame), and one by John H. Williams about John Backus's FP language. I got this gem on Ebay a few years ago, I doubt it is still in print, but here is the ISBN number if you want to try and track it down: 0-521-24503-6.

Programming Language Pragmatics - Micheal L. Scott

While not specifically about functional programming, but rather about all kinds of programming, this book is a must have for any programming language enthusiast (like myself). Its 800+ pages of densly packed inforamtion on all sorts of programming langauges.

Concurrent Programming in ERLANG

Erlang is a language developed by Ericson's research labs for use in soft-real-time programming. It is part-functional, part-declarative, and an extremely interesting langauge. This book, written by the 4 researchers who created Erlang, is well written and gives a great introduction into how to code, real world applications in a more functional style.

ML for the Working Programmer - L. C. Paulson

Standard ML is one of the more interesting functional langauges out there, and this book is an excellent reference on the langauge. I have to say that it does at times get very dense with theory and math, but it is a book I still refer to often, even when not programming functionally.

Can Programming Be Liberated from the von Neumann Style? - John Backus

Not really a book, but instead the speech given by John Backus at the 1977 Turing Awards. This speech introduced FP, a very interesting (although somewhat odd) functional language. This was a very influential speech in the world of functional programming. It can be found in PDF form at http://www.stanford.edu/class/cs242/readings/backus.pdf.

AUTHOR

stevan little, <stevan@iinteractive.com>

COPYRIGHT AND LICENSE

Copyright 2004, 2005 by Infinity Interactive, Inc.

http://www.iinteractive.com

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




Hosting generously
sponsored by Bytemark