= Prelude - a Haskell-like functional library

$Id: README 17 2006-09-17 18:03:15Z prelude $

*WARNING* <tt>The project is still in a very preliminary state. Only
List was partially implemented. Feel free to contribute.</tt>

Project home is at http://rubyforge.org/projects/prelude/

== The goal

The general idea is that functional programming provides many
benefits, which are not directly available in Ruby out of the
box. This library will, hopefully, provide an infrastructure for the
use of most Haskell's functional idioms. It will also facilitate a
more or less direct port to Ruby of algorithms and data structures
already developed by functional community. I deem infinite lists,
monads, and higher-level functions to be most useful functional
contribution to the general purpose programming.

I do believe the old math's maxim that "new notation leads to new
results."

== Features

As of right now, i.e., release 0.0.x, the feature list is pretty much
a wish list, so treat it accordingly.

=== Rather curious collection of operations on lists

Haskell's lists are different from Ruby's arrays in many ways. First
of all, there are more operations defined on lists and the naming
convention is different. Since Haskell's (or Lisp's) lists play a
fundamental role in everything functional, their implementation seems
necessary. Here are the goals for list's implementation:

* Most, if not all, functions, i.e., +head+, +tail+, +last+, +first+, +concat+, etc.

* Assignment compatibility with Ruby's native arrays. For example,
  these operations should be correct:

   List a = List.new([1, 2, 3])
   b = [3, 4, 5]
   List c = a+b
   a[1] = 10
   b[2] = a[3]
   a << 3 << 4
  ...and so on.
    
* List comprehension. It's mostly covered by Ruby's own functionality,
  but some semantic refinements may be needed.

* Infinite lists. It might look like this:

   List ones = List.new([1]) { ones } # => [1,... ]
   ones.take 3                        # => [1, 1, 1]

  This functionality is being developed by the Lazilists project, see
  http://lazylist.rubyforge.org

* What else?

===  Reinforced Ruby's Lambda-calculus

While implementing majority of the Lambda world is relatively trivial
in Ruby, some of the recursive beauty might be lost. Consider +foldl+,
for example. The classic recursive definition like this

   def foldl(s, &block)
     empty? ? s : tail.foldl(block.call(s, head), &block)
   end

croaks on about 800+ elements integer lists, but more rubyish and
compact

   def foldl(s, &block)
     inject(s){ |a,b| block.call(a,b) }
   end

does not possess any of the classic's functional elegance. It means that
for practical applications Ruby's recursions need to be fixed or
somehow re-implemented in the Prelude library.

===  Higher-order functions

It is a very good thing, that Ruby allows functions to be good
citizens including being passed to other functions and returned from
them. These need to be added to complete the picture:

* Function combinations. Consider:

   add5 = proc {|x| x+5}
   add6 = proc {|x| x+6}
   add11 = add5 << add6

  I.e., the <tt>add5</tt> is an absolutely generic algorithm expressed
  in terms of other functions as long as <tt>add5</tt> takes as an
  argument and <tt>add6</tt> returns an object for which operation
  <tt>+</tt> is defined.

* Currying, as in

    add5 = (proc {|x,y,z| x+y+z}).curry(5)
    add5.call(3, 2)      # => 10

  More convenient syntax is desirable.

* What else?

===  Monads

This is where all the previous trouble should start paying off
allowing an application to be structured like this:

   result << connect << do_something << delete_something << with(params)

Writing tutorials for monadic computations became a little industry in
itself, see http://nomaware.com/monads/html/index.html to get
started. More monadic resources are here:
http://haskell.org/haskellwiki/Books_and_tutorials#Using_monads

=== What else?

These features will be nice to have in a second release of the library:

* General purpose monadic parser library similar to Parsec, see http://www.cs.uu.nl/~daan/parsec.html

* Tools for automatic program verification and algebraic proofs

* What else?


== What's in a name

Since most of the functionality to be implemented here is defined in
Haskell's prelude package, the name *Prelude* seemed natural.

== Download

The latest Prelude library version can be downloaded from
http://rubyforge.org/frs/?group_id=2096


== Installation

You can install Prelude library with the following command.

  % gem install prelude

== License

Prelude library is released under the Lesser GPL license, see
http://www.gnu.org/licenses/lgpl.txt


== Support

Please use the following:

* forums on Rubyforge for general discussions, http://rubyforge.org/forum/?group_id=2096
* trackers to submit bugs or feature requests, http://rubyforge.org/tracker/?group_id=2096
* to contact the author, send mail to prelude rubyforge org

== References

The authors of the project were inspired by the following works:

1. An article, probably by Gavin Sinclair, at http://blogs.pragprog.com/cgi-bin/pragdave.cgi/Tech/Ruby/ToProc.rdoc regarding Symbol#to_proc function in Ruby Extension project, http://extensions.rubyforge.org
2. An elaborate port of Perl's Sub::Curry library by Ross Bamford, http://rubyforge.org/projects/rubymurray
3. An early implementation of Haskell's lists as Ruby arrays by Hipster (a.k.a. Michel van de Ven). His original sketch can be found at http://www.xs4all.nl/~hipster/lib/ruby/haskell
4. An article by Christopher Williams "Late to the Party" posted at http://cwilliams.textdriven.com/pages/monads
5. Several articles on monads by MenTaLguY, see http://moonbase.rydia.net/mental/writings/programming/monads-in-ruby/00introduction.html