57. map, filter, und reduce

Iteratoren erlauben uns auch, die aus Python bekannten Funktionen map und filter zu schreiben, ohne etwas von der Listenimplementation wissen zu müssen.

List *map(char *(*mapFun)(char *arg), List *l)
{
  List *new=list_new();  char *item;
  Iterator *it=list_iteratorNew(l);

  while ((item=list_iteratorNext(it))) {
    list_append(new, mapFun(item));
  }
  list_iteratorFree(it);
  return new;
}

List *filter(int (*filterFun)(char *arg),
  List *l)
{
  List *new=list_new(); char *item;
  Iterator *it=list_iteratorNew(l);

  while ((item=list_iteratorNext(it))) {
    if (filterFun(item)) {
      list_append(new, item);
    }
  }
  list_iteratorFree(it);
  return new;
}

Auch reduce wäre denkbar – allerdings ist das für Strings etwas müßig. Mit Zahlen ist sowas interessanter, allerdings verlieren wir dann etwas von der Eleganz des reduce-Konzepts. Brauchbar könnte sowas sein:

int reduceFloat(double (*reduceFun)(double accum, char *arg2), List *l)
{
  double result=0;
  Iterator *it=list_iteratorNew(l);
  char *item;

  while ((item=list_iteratorNext(it))) {
    result = reduceFun(result, item);
  }
  list_iteratorFree(it);
  return result;
}

– es wird also eine Funktion mit einem “Akkumulator” übergeben, in dem jeweils das Ergebnis der Anwendung auf das vorherige Element steht. Wozu das gut sein kann, mag im unten stehenden Beispiel klar werden.

Wir haben hier auf Fehlerbehandlung verzeichtet, an sich müssten natürlich die Rückgabewerte von list iteratorNew und Freunden geprüft werden.

Nützlich sind außerdem Varianten, die die alten Listen gleich freigeben:

List *mapAndFree(char *(*mapFun)(char *arg), List *l)
{
  List *res = map(mapFun, l);

  list_free(l);
  return res;
}

List *filterAndFree(int (*filterFun)(char *arg), List *l)
{
  List *res = filter(filterFun, l);

  list_free(l);
  return res;
}

Eine Funktion, die die mittlere Länge der groß geschriebenen Wörter in einem Text berechnet, könnte dann etwa so aussehen:

int isupperStr(char *s)
{
  return isupper(*s);
}

double addLen(double accum, char *s)
{
  return accum+strlen(s);
}

void processStuff(char *fname)
{
  List *wordList = getWordList(fname);
  List *upCaseWords;

  if (!wordList) { return; }
  printf("Now looking at %s...\n", fname);
  upCaseWords = filterAndFree(isupperStr,
    mapAndFree(strip, wordList));
  printf("Avg length of uppercase words: %f\n",
    reduceFloat(addLen, upCaseWords)/
    (float)list_len(upCaseWords));
  list_free(upCaseWords);
}

Nachzutragen bleibt noch die Implementation für die verwendeten Funktionen getWordList und strip:

#define MAX_WORD_LEN 80

char *strip(char *word)
{
  static char stripped[MAX_WORD_LEN];
  char *sp=word, *dp=stripped;

  while (isspace(*sp)) {
    sp++;
  }
  while (*sp && (dp-stripped)<MAX_WORD_LEN-1) {
    *dp++ = *sp++;
  }
  *dp = 0;
  while (isspace(*--dp)) {
    *dp = 0;
  }
  return stripped;
}

List *getWordList(char *fname)
{
  FILE *inF = fopen(fname, "r");
  List *words = list_new();
  char *w;

  if (!inF) {
    if (words) {
      list_free(words);
    }
    return NULL;
  }
  while ((w=getNextWord(inF))) {
    list_append(words, w);
  }
  fclose(inF);
  return words;
}