When would you use functional programming?

[Ovid]

I've been doing a little research into the strange world of functional programming using Haskell. It's an interesting language and I was playing with it to improve my understanding of how functional programming works with Perl. I feel that I have a fine grasp on map, grep, sort, closures and other aspects of Perl that are related to functional programming. Further, I'm familiar with Why I like Functional Programming by tilly. However, I would love to see more examples of how things are done in a functional manner in Perl. For example, in Perl, to compute the product of all of the elements of a list, we might do the following:

my @list = qw/ 7 5 2 2 /;
my $prod = shift @list;
$prod *= $_ foreach @list;

In Haskell, this would be illegal because variables are defined, not assigned values. In other words, if you have x = 3, then 'x' is always equal to three. You cannot change the value and last two lines of code above would not have a direct equivalent (shifting an element of off the list changes the list in the second line).

Let's say that I want the first element of a list. The first line below is bad, the second is good.

# bad.  Alters @_
sub head { shift }

# good.  Preserves @_
sub head { $_[0] }

This leads to interesting properties of the language. In the following example, 'i' is set to seven, even though 'j' is not listed yet. This is because these variables are defined at compile time.

i = j + 1
j = 6

Needless to say, a similar construct in Perl would not perform the same. We can think of these variables as being analogous to what we experience in our math classes. If we have x + 3 = 7, we know that x is four and that its value will not change.

Another interesting thing about Haskell is that it does not have loop constructs such as while or for. This is because the language is essentially a series of definitions and the compiler or interpreter applies these definitions to the problem at hand and determines how to arrive at the result. Using loops involves having the programmer direct the actions of the computer and typically uses a variable set as a flag to indicate when the loop terminates. Since you cannot change the value of variables in Haskell, you cannot set such a flag. Thus, loops appear to be replaced with recursive definitions. Let's use this to get the product of a list in Haskell.

prodList lst =
    if (length lst)==1 then head lst
else head lst*(prodList (tail lst))

And here's a Perl equivalent of that.

sub head { $_[0] }
sub tail { @_[1..$#_] }
sub prod_list { 
  1 == @_ 
    ? head @_ 
    : (head @_) * prod_list( tail @_ ) 
}

So in looking at functional programming as a series of definitions and not as a series of directives, we define a factorial function in terms of the &prod_list function.

sub factorial { prod_list( 1 .. $_[0] ) }

This leads to the following program to determine the factorial of a number supplied on the command line.

#!/usr/bin/perl -w
use strict;

sub head { $_[0] }
sub tail { @_[1..$#_] }
sub prod_list {
  1 == @_ 
    ? head @_ 
    : (head @_) * prod_list( tail @_ ) 
}
sub factorial { prod_list 1 .. $_[0] }

print factorial shift;

Yes, it looks very strange. Also, note that for simplicity, I have left off error checking. Further, functional programming as performed by Haskell is difficult to simulate in Perl as Haskell does many interesting tricks with type checking. I also think that my factorial example may not be the best example as that's a fair amount of overhead to set up a simple function (again without error checking).

sub factorial { 
  my $result = 1;
  $result   *= $_ for 1 .. $_[0];
  $result
}

I realize that I have given some rather simplistic examples above that do not even begin to touch on the power of functional programming, but rather, they illustrate some of the different approach to problem solving. Perhaps a more classic example would appear to be the Schwartzian Transform (ST).

@new_list =
  map  { $_->[0] }
  sort { $a->[1] <=> $b->[1] }
  map  { [ $_, expensive_func( $_ ) ] }
    @old_list;

With the ST, we don't have "loops", per se. Instead, we can think of these as definitions of how to transform a list. Further, we don't have the variables being reassigned to (though they might be in &expensive_func).

I am wondering about the following things.

• What other examples can Monks offer?
• Has anyone developed any guidelines regarding when such a style might be appropriate in Perl?
• Do those small functions in the first factorial example pay off if they are to be heavily reused?
• Can adding the constraint of not altering a variable's value lead to "more correct" code, if done in a non-functional language?
• Is my brief meditation missing the point of functional programming?

Note that there are many things that I have not touched on. I don't know what monads are, for example. Also, I haven't dicussed guards (which appear to be similar to method overloading), lazy evaluation (hurry up, Perl 6! :), or first class functions, to name just a few topics.

Update:

It should be noted that Perl types being based on data structures as opposed to data types definitely causes potential problems here. Also, the &prod_list could be written differently.

# who says Perl has too much punctuation? :)
sub prod_list { 1 == @_ ? $_[0] : $_[0] * prod_list( @_[1..$#_] ) }

Also, much of functional programming involves passing functions to other functions. I haven't discussed that.

This is all a long-winded way of saying "I don't quite grok functional programming."

Cheers,
Ovid

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.

[VSarkiss]

If you're getting interested in functional programming, you should really read John Backus' 1978 Turing Award paper, "Can programming be liberated from the Von Neumann style?", which was really seminal to the whole field. (I don't believe it's available to the general public on the web -- I couldn't find it -- but look for the August 1978 issue of Communications of the ACM.)

In spite of its age, the points it makes are still fresh and interesting. One of the main ideas, which you point out but don't really emphasize above, is that it's not procedural: your program doesn't say, "Copy these bits over there, then if that was zero, copy these others over here." It says something more like, "The result I want can be described like this." The main tool for describing the like this part are functions (in the mathematical and logical sense) and functional composition. (Hence the name. ;-)

In my experience, functional programming doesn't have a steep learning curve, but it does involve an "Aha!" experience. One day, it just starts making sense. Sorry, but I don't have a good way of getting you to that point, other than what you're doing. Like geometry, there is no royal road to non-procedural programming.

[DapperDan]

http://www.stanford.edu/class/cs242/readings/backus.pdf (2396KB)
via http://lambda.weblogs.com/discuss/msgReader$4172,
via http://www.google.com/search?q=neumann+backus+online.

[ignatz]

While I share your fascination with functional programming, I can't help getting the feeling like I'm watching an episode of MacGyver. You know, like how he takes a swiss army knife and uses it in all these bizarre ways that it was never designed for in order to save the day.

I guess I should add that I get a similar feeling looking at OO Perl code. Maybe I'm just an ol' fuddy duddy, but for functional stuff, I'll stick to the other Camel.

I'm not just knocking what you are posting. I do think that it's important to push and stretch a langauge to it's limits. It just gives me kind of an oogee feeling watching you do it. It seems so clean and clear in a functional language, and so ugly and warped in Perl.

()-()
 \"/
  `                                                     

[jordanh]

I'm very attracted to Functional Programming also. If I ever get around to it, I plan to introduce my 11 year old daughter to programming via Scheme. But...

Larry Wall refers to Icon (not a Functional Programming Language - an odd hybrid really between Logic, Functional and Procedural) as a "Cat" language, while Perl is a "Dog" language. I think I agree with that about Icon, and maybe it applies to most Functional languages, as well.

Like a Cat, they are pretty to look at, nice to have around, but aloof and not practical at all. Dogs are loyal and serve many practical functions.

Among Functional Languages, I'm very attracted to Scheme. Ovid noted how Functional programming was all about creating definitions and letting them define the solution for you. I like Lisp and Scheme because the language systems have the most direct support for Meta-Programming. There is no distinction between programs and data in these languages, so you can create definitions that create definitions in the most straightforward way possible. This is applicable to generating new language systems and programming paradigms on top of the base system. I've never seen languages where whole object systems and Logic programming systems can be defined in so few lines as you can in Scheme.

The possibilities are limitless. Scheme has even captured the essence of control structures and goto in a completely functional manner with continuations. It's amazing, heady stuff really.

I do think it's important to be exposed to this stuff and take away what's good, but I still feel that for much of what I do, Perl will make me more productive. Perhaps I would devote all my hobbyist programming time to Scheme if productivity weren't so important to me. Perhaps not...

Oh, and check out Icon, too! Look at the 8-queens problem in Icon sometime... wonderful...

[DapperDan]

Hi Ovid-

This isn't really a direct answer to your query but it is related to the intersection between functional programming languages and Perl.

I believe Dominus (aka MJD) is the man who knows most about this (though tilly deserves mention also) from having read his website, Perl Paraphenalia.

I am waiting (but not holding my breath as I would have died by now) for mjd to finish Perl Advanced Techniques Handbook. He does a course on the topic as well.

I think that this book, if it ever comes off the presses would cause a renaissance/revolution in the world of Perl on the order of when thedamian did his book on OO Perl. And, no I don't think that's overstating it.

(If you read this Mark, please take it as tacit encouragement rather than a flame; I fear it will never be possible for me to take your PATH class because I am neither stateside nor working for a potential customer of yours so I have to twiddle my thumbs 'til the book comes.)

Peace.

[diotalevi]

I learned about the book while the iterators chapter was online. Has it /ehem/ iterated past that by now?

__SIG__
printf "You are here %08x\n", unpack "L!", unpack "P4", pack
  "L!", B::svref_2object(sub{})->OUTSIDE;

[DapperDan]

Nope, as far as I'm aware there hasn't been anything since the iterators chapter (5?). I think I'm subscribed to an announce mailing list for the PATH book but I haven't seen anything on it.

[gjb]

A long time ago I was using the computer algebra system Mathematica (Wolfram Research, ltd.). It has it's own programming language which is quite elegant. It is a functional language at heart, but with an imperative layer on top of it. Moreover, since it's a CAS, one can use logic programming techniques as well. Unfortunately, it lacked an OO layer.

It was very nice to work with since it allowed to mix and match programming paradigms as needed. One could write a function in functional style, imperative style or a mixture of both without being hampered by the programming language.

In this sense it was a very good example of "there's more than one way to do it" which I appreciate very much in Perl.

Perl has its functional components such as map, grep and closures. List;:Util also helps.

I really appreciate a language in which it is possible to use the style most appropriate to the problem, rather than having to wrestle to get matters done. Perl does a reasonable job at this, but still leaves a number of things to be desired.

As an aside, to illustrate the elegance of functional languages, consider the quicksort in Haskell.

qsort []     = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
                 where
                   elts_lt_x   = [y | y <- xs, y < x]
                   elts_greq_x = [y | y <- xs, y

Just my point of view, -gjb-

[Dominus]

Says gjb:

As an aside, to illustrate the elegance of functional languages, consider the quicksort in Haskell.

  qsort []     = []
  qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_gr_x
                   where
                     elts_lt_x   = [y | y <- xs, y < x]
                     elts_gr_x = [y | y <- xs, y > x]

There's a very cool thing about this that you didn't mention. Sometimes in newsgroups or on this web site you see beginners do this:

      ($minimum) = sort {$a <=> $b} @items;

when they want to find the minimum value in an array of numbers. And then other folks usually tell them that that is a bad move, because the sort takes O(n log n) time, but to scan the array looking for the minimum only takes O(n) time. This means that if you double the length of the array, the scan will take exactly twice as much time, but the sort will take more than twice as much time, and so no matter how fast your sorting is, for sufficiently large lists, the scan will be faster. Unfortunately, the array scan requires more code and isn't as transparently obvious.

The astonishing thing about the Haskell implementation is that you can write the analogous code:

    minimum = head(qsort array);

and it will run in O(n) time. Sorting the whole list would require O(n log n) time, but Haskell figures out that it doesn't need to sort the entire list, and it manages to run the qsort function partially, just enough to sort the first element to the front. I find it incredible that this optimization just falls out naturally from Haskell's way of doing things.

This isn't a result of the fact that Haskell's a functional language, but rather that it's a lazy language. But it's difficult to imagine a usefully lazy language that wasn't also functional. The quest for useful laziness like this is one of the primary motivators for studying functional languages in the first place. A simpler example looks like this:

    sub zero {
      return 0;
    }

    $x = zero(SOME_VERY_LONG_COMPLICATED_EXPRESSION);

Here Perl, in spite of claiming the virtue of laziness, computes the value of the long complicated expression, but then throws it away and assigns zero to $x. The analogous code in Haskell never computes the value of the long complicated expression at all.

(Translation of the qsort for non-Haskell users: [] is the empty list; [x] is a list that has just x and nothing else; ++ is the operator that appends two lists head-to-tail, and x:xs is the list you get by taking the list xs and appending x to the front. (So [x] and x:[] mean exactly the same thing.) gjb left a little bit of code off the end of the function, which I added back. [y | y <- xs, y > x] is something like Perl's map plus grep. It makes a list of all the y values from the list xs, subject to the constraint that y > x must be true. So [BLAH(y) | y <- xs, COND(y)] is very much like perl's map BLAH($_), grep COND($_), xs construction. Now you know Haskell. :) )

--
Mark Dominus
Perl Paraphernalia

[thraxil]

the prod_list function could be implemented much more simply in many functional languages using a 'foldl' or 'foldr' construct.

check out the CPAN module Functional. it provides a whole slew of useful functional constructs. including foldl:

use Functional;
sub prod_list {foldl1(sub {$_[0]*$_[1]},[@_])}

print prod_list(3,2,1,10);

anders pearson