Re: useful list functions

[Maciej Stachowiak <mjs eazel com>]

John Cupitt <john.cupitt@ng-london.org.uk> writes:

> Maciej Stachowiak wrote:
> > /* Just like `map' in Lisp, Scheme or Perl, i.e. like for_each but
> >    return a list of the results. (non-destructive) */
> 
> I realise this has zero change of inclusion, but I thought I'd share my
> favorite two 'missing' g_?list_*() functions with you as well ;-)
> 
> The idea for these two functions is that, like lisp, explicit recursion
> or iteration over lists is a bad thing, and should be encapsulated in
> higher order functions. I use this pair, and (I don't think) my app (not
> small, 60k lines) has any list loops in it at all.
> 
>   typedef gpointer (*ListMapFn)( gpointer, gpointer ); 
>   gpointer slist_map( GSList *list, 
>     ListMapFn user_func, gpointer user_data );
> 
> This is like for_each, but has a 'bail out'. If user_func returns NULL,
> _map() tries the next element. If user_func returns non-NULL, the loop
> stops and slist_map() returns that value as its result. If user_func
> returns NULL for all elements, _map() returns NULL.

That's very different from the usual meaning of `map'. In fact, it is
kind of similar to g_list_find_custom.

> You can express search-for-item loops, repeat-until-full loops and
> others. Also handy for trapping errors .. eg. "scan all input fields ...
> if a field contains a format error, bail out immediately and pop up an
> alert box over the offending field."
> 
>   typedef gpointer (*ListFoldFn)( gpointer, gpointer, gpointer );
>   gpointer slist_fold( GSList *list, 
>     gpointer start, ListFoldFn user_function, gpointer user_data );
> 
> This is like _map(), but it folds the list up with a dyadic function.
> For example, for the input list:
> 
>   [a,b,c]
> 
> it returns:
> 
>   fn (fn (fn start a) b) c
> 
> ie. fn is given two arguments: an accumulated value, and the next list
> element. 'start' is the initial value for the accumulator. Given an
> empty list, the function returns 'start'. Like _map(), _fold() has a
> bail out: this time if user_func returns NULL, iteration terminates
> immediately and the whole function returns NULL. 
> 
> Using fold you can find the maximum value in a list, write Maciej's
> _map() function, sum a list, erm, and other stuff.

Yes, I was considering adding `fold' (also known as `reduce'), but it
brings up tricky memory management issues when you don't have GC,
i.e. how to ensure all the intermediate values are freed if necessary.

> There are a few variants as well: slist_map2 and slist_fold2 take two
> user_data arguments. slist_map_rev() maps in reverse order.
> slist_foldr() folds a list with a right-associative function.

Shhh! I'm trying to turn glib into Lisp one small step at a time!
Don't give away the game :-)

 - Maciej