Warp wrote:

>   In the haskell case, it's not at all clear what you are doing. In fact,
> I don't even think that your haskell example is correct. I can't find the
> function "fold", but the closest thing I can find is the (rather unclearly
> named): http://www.zvon.org/other/haskell/Outputprelude/foldl1_f.html
> 
>   It seems that, as the name clearly implies, the difference between
> foldl and foldl1 is that the first one applies the function to the
> second parameter and the first element of the list, then applies the
> function to the result and the second element of the list, and so on,
> while foldl1 there's only a function and a list and the first element
> of the list is now in the role of the second parameter to foldl.

printf() is short for "print formatted".

foldl is "fold-left", while foldr is "fold-right". Similarly foldl1 and 
foldr1 only work for non-empty lists (and thus don't require a start 
value; foldr returns the start value unaltered in the case of an empty 
list). More subtle is foldl', which causes the subtotal to *actually 
compute* at each step, rather than just building a giant expression 
which is only evaluated right at the end.

The other name for a fold is "catamorphism", but we won't worry about 
that. ;-)

You can use folds for all kinds of interesting things. E.g., "foldr1 
max" finds the highest element of a list, and "foldr (++) []" takes a 
list of lists and returns a flatterned list. A huge number of standard 
list processing functions are or theoretically can be defined as folds. 
For example:

   filter p = foldr (++) [] . map (\x -> if p x then [x] else [])

That is, take a list. For every element where "p" returns true, make a 
1-element list, otherwise make an empty list. Now just the list of lists 
together...

Map itself can be similarly defined, as can reverse and lookup. In fact, 
just about any process that involves linearly traversing a list (i.e., 
almost all list processing!) can be implemented as a fold. This is quite 
possible not the most *efficient* implementation, but it demonstrates 
the power of the abstraction.

Many other Haskell datatypes also have "fold" functions too. It's a 
common idiom.

>   I think it would be perfectly possible to simulate the same thing in C++
> with something like:
> 
>     int result = foldl1(plus, intContainer);
> 
> with proper implementations of the 'foldl1' and 'plus' templates. The
> foldl function would be equally easy:
> 
>     int result = foldl(plus, 64, intContainer);

It sounds plausible to me...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message