[plt-scheme] what is fold-left?

On Thu, Feb 12, 2009 at 02:56:37PM -0600, Bill wrote:
> On Thu, 2009-02-12 at 14:54 -0500, hendrik at topoi.pooq.com wrote:
> > On Wed, Feb 11, 2009 at 09:11:17PM -0600, Mike Eggleston wrote:
> > > Morning,
> > > 
> > > I'm looking at some code at
> > > <http://funcall.blogspot.com/2007/08/naive-bayesian-classifier.html>. This
> > > code by default will not run in DrScheme. The code is using (fold-left
> > > ...). Looking at the function it looks like a (map ...), but I don't
> > > (yet) know why I can't just use a 'map' instead of the 'fold-left'.
> > > 
> > > Any ideas? What does this function do that 'map' doesn't and why
> > > should it be used?
> > 
> > The name comes from Richard Bird's paper "A Theory of Lists", and he may 
> > have gotten it from ongoing discussins in IFIP WOrking Group 2.1 on 
> > Algorithmic Language.
> > 
> > There's also a fold-right, by the way.
> 
> Another source is Richard Bird and Oege de Moor, _Algebra of
> Programming_, pp. 4 -- 16, where fold functions for the natural numbers,
> lists and trees are discussed.

Trees have natural constructors.
Lists can be viewed as trees, constructed by a concatenation function.
As a tree, a list has a lot of ways it can be so constructed.  fold-left 
and fold-right just deconstruct it in two particularly regular ways.

-- hendrik