Comparison of Foreach, Map, Filter, and Fold

Consider a list val xs = List(1, 2, 3) to compare the effects of map, filter, foreach, and fold:

Map

val r = xs.map(x => s"x=$x")

Function map produces a list of the same length as its input list, so r.length == 3 is true. The type of the result list is determined by the transformation function passed to map. In the example above, the type of r is List[String] because function x => s"x=$x" transforms the integer x into a string.

Filter

val r = xs.filter(x => x>=2)

Function filter produces a sub-list of at most the length of its input list, so r.length <= 3 is true. The type of the result list is the same as the type of the input list. In the example above, the type of r is List[Int] because the list xs has type List[Int].

Foreach

val r = xs.foreach(x => println(x))

Function foreach visits all elements of a list to apply a function for its side-effect (e.g., print). The type of the result is always Unit, which means we cannot do anything meaningful with r in the example above.

Fold

val r = xs.foldLeft(0)((acc,x) => acc+x)
val r = xs.foldRight(0)((x,acc) => x+acc)
val r = xs.fold(0)((x,y) => x+y)

Folding produces an aggregate result from the elements of a list. The type of the result is the same as the type of zero element (in the example above, the type of r is Int because 0 has type Int). Functions foldLeft and foldRight traverse the list from the left/right, respectively. Function fold can perform a tree-like traversal when operating on a parallel collection; for parallel, tree-like traversal to be meaningful, the aggreate function must be commutative.

Summary

For an input list of type List[X] of length l, the list operations can be summarized as follows.

Java Iterator Loop

Java supports iterating over the elements of a collection, rather than accessing them by their index:

List<Int> xs = ...
for (x : xs) {
  // do something with x
}

Higher-order functions in C

Function pointers in C allow us to implement higher-order functions in C. Below, we implement a linked list with higher-order functions foreach, map, filter, foldLeft, and foldRight.

Linked List

A generic linked list stores data using an untyped void* pointer.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
  void* data;
  struct Node* next;
} Node;

Node* cons(void* data, Node* next) {
  Node* node = (Node*)malloc(sizeof(Node));
  node->data = data;
  node->next = next;
  return node;
}

To add int data into a generic list, we use function new and consi.

int* new(int data) {
  int* iptr = (int*)malloc(sizeof(int));
  *iptr = data;
  return iptr;
}

Node* consi(int data, Node* next) {
  return cons(new(data), next);
}

An entire list and its data is deleted with function delete below.

void delete(Node* n) {
  if (n != NULL) {
    delete(n->next); 
    free(n->data); 
    free(n);
  }
}

Function Pointers

The function pointers f, p, and agg allow us to define transformers (for map), predicates (for filter), and aggregators (for fold).

typedef void* (*f)(void*);
typedef bool (*p)(void*);
typedef void* (*agg)(void*, void*);

Higher-Order Functions

Foreach

void foreach(Node* n, f fn) {
  if (n != NULL) {
    (*fn)(n->data);
    foreach(n->next, fn);
  }
}

Map

Node* map(Node* n, f fn) {
  if (n == NULL) return NULL;
  void* v = (*fn)(n->data);
  return cons(v, map(n->next, fn));
}

Filter

Node* filter(Node* n, p p) {
  if (n == NULL) return NULL;
  if ((*p)(n->data)) return cons(n->data, filter(n->next, p));
  else return filter(n->next, p);
}

Fold

void* foldLeft(Node* n, void* z, agg fn) {
  if (n == NULL) return z;
  else return foldLeft(n->next, fn(z, n->data), fn);
}

void* foldRight(Node* n, void* z, agg fn) {
  if (n == NULL) return z;
  else return fn(n->data, foldRight(n->next, z, fn));
}

Use

Next, we define some functions to be passed as arguments to higher-order functions. Note that function add cannot be used with foldLeft and foldRight to avoid memory leaks (functions safeaddl and safeaddr free the intermediate aggregate values).

void* print(void* x) {
  printf("%d\n", *(int*)x);
  return NULL;
}

void* inc(void* x) {
  return new((*(int*)x)+1);
}

bool even(void* x) {
  return (*(int*)x) % 2 == 0;
}

void* add(void* acc, void* x) {
  return new((*(int*)acc) + (*(int*)x));  
}

// use with foldLeft; frees intermediate aggregator
void* safeaddl(void* acc, void* x) {
  void* result = add(acc, x);
  free(acc);
  return result;
}

// use with foldRight; frees intermediate aggregator
void* safeaddr(void* x, void* acc) {
  void* result = add(x, acc);
  free(acc);
  return result;
}

We now set up a list and print the results of calling the higher-order functions.

int main() {
  Node* l1 = consi(1, consi(2, consi(3, consi(4, NULL))));
  printf("foreach\n");
  foreach(l1, &print);
  
  Node* l2 = map(l1, &inc);
  printf("map\n");
  foreach(l2, &print);
  
  Node* l3 = filter(l2, &even);
  printf("filter\n");
  foreach(l3, &print);
  
  printf("sum(l1) = %d\n", *(int*)foldLeft(l1, new(0), &safeaddl));
  printf("sum(l2) = %d\n", *(int*)foldRight(l2, new(0), &safeaddr));
  printf("sum(l3) = %d\n", *(int*)foldLeft(l3, new(0), &safeaddl));

  delete(l1);
  delete(l2);
  delete(l3);  
  
  return 0;
}

Methods and Functions

Methods in Scala must be part of a class structure:

class C:
  def f(x: Int) = x+1

The Scala REPL console allows defining methods seemingly outside classes; they become part of an implicit class TODO.

Curried Definitions

Curried definitions and partial function application allow us to bind some arguments while having other arguments free. This can be used to create factory-like functions that create “objects” (more about this in a later lecture on Closures). For example, below we define a function named add4 that takes an Int and returns a tuple of 3 functions: one for adding, one for multiplying, and one for subtracting.

val add4 = (x:Int) => 
  ((y:Int) => x+y, 
   (y:Int) => x*y, 
   (y:Int) => x-y)

The function add4 can be used in the following way:

val fns = add4(5)
fns._1(4) // 9
fns._2(4) // 20
fns._3(4) // 1

We can also use pattern matching to decompose the tuple of functions into its components like below:

val (add, mul, sub) = add4(5)
add(4) // 9
mul(4) // 20
sub(4) // 1

Partially Defined Functions

Partial functions can be implemented for a subset of the possible argument types. In the example below, a partial function is defined for inputs of type Int and String, but not other subtypes of Matchable. It guarantees to return an Int:

val d : PartialFunction[Matchable, Int]  = {
  case i: Int => i + 1 
  case s: String => s.length
}

Calling this function with d(3) returns 4, d("hello") returns 5, and d(7.0) throws a MatchError because the function is not defined for values of type Float.

The return types of the cases of a partial function can be unified with a common super-type in the type hierarchy. In the example below, a partial function returns Any and therefore allows the implementation of the Int case to return an Int whereas the the implementation of the String case returns a String.

val d : PartialFunction[Matchable, Any]  = {
  case i: Int => i + 1 
  case s: String => s + "!"
}