Beefy Boxes and Bandwidth Generously Provided by pair Networks Frank
We don't bite newbies here... much
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
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


In reply to Re: When would you use functional programming? by Dominus
in thread When would you use functional programming? by Ovid

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others avoiding work at the Monastery: (7)
    As of 2014-04-16 11:07 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      April first is:







      Results (424 votes), past polls