Re: useful list functions

[Maciej Stachowiak <mjs eazel com>]

Peter Lund <firefly@diku.dk> writes:

> On Mon, 7 Aug 2000, John Cupitt wrote:
> 
> First off:  I love functional programming languages -- I've done my share
> of programming imperative languages (since the mid-eighties) but I find
> that I'm far more productive in ML than in C.  Part of this is because of
> a nicer type system, pattern matching, automatic memory management and the
> ability to use recursion in real-world programs -- part of it is due to
> the wonderful higher-order functions available in the standard libraries.
> 
> If I wrote the functions John and I suggest, would they stand a chance at
> getting included?

I think most of them are redundant with the ones I already suggested,
and some of the others would be very hard to get right because of the
memory management issues.

> 
> > 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) */
> 
> >   gpointer slist_map( GSList *list, 
> >     ListMapFn user_func, gpointer user_data );
> 
> Great -- I like having the bail-out option, could be used for simulating
> exceptions :)

I disapprove of the way the bail-out option is implemented, as it uses
in-band signalling (NULL is a valid list value) and this definition is
foreign to the way `map' normally defined. If you need to "bail out"
what you really want is to do a _find_custom and then operate on the
value.
 
> >   typedef gpointer (*ListFoldFn)( gpointer, gpointer, gpointer );
> >   gpointer slist_fold( GSList *list, 
> >     gpointer start, ListFoldFn user_function, gpointer user_data );
> 
> This is even better stuff :)
> 
> > Using fold you can find the maximum value in a list, write Maciej's
> > _map() function, sum a list, erm, and other stuff.
> 
> Yep, lots of other stuff :)
> 
> (I have programmed some small programs in ML, only up to a couple of
> thousand lines -- they would have been so much longer in low-level
> language like C using only the standard libraries)
> 
> > 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.
> > 
> 
> Great :)
> 
> What about equivalents to the take, drop, filter, mappartial, and
> partition functions often found in functional programming languages?
> 
> take(l:list, n:integer) -- returns a list containing the first n elements
>                            in l.
> 
> drop(l:list, n:integer) -- returns a list with the first n elements
>                            dropped from l.

I suggested _copy_sublist which is more general than these.

> filter(l:list, f:filterfunction) -- returns a list of the elements for
>                                     which the filterfunction returns true.

My suggested g_list_partition handles this functionality - however,
for ease of memory management, it returns both the list for which the
predicate was true, and separately the list for which it was false.

> mappartial(l:list, f:optmapfunc) -- returns a list of the elements in l
>                                     mapped onto a new domain (i.e. after
>                                     conversion by the mapfunc).  Elements
>                                     can be dropped/filtered out by the
>                                     mapfunction.

Disapprove of in-band signalling here, you can always partition and
then map. Note again also the memory management issues.

> These should go a long way towards eliminating loops in (the application
> programmers' part of) GTK+ programs.

My proposed functions were meant to work towards this goal. :-)

 - Maciej