Understanding fold-left and fold-right in Scheme

foldfunctional programmingscheme

So my task is to implement the most basic version of the 'map' function and the 'filter' functions in Scheme using fold-left or fold-right. I am having a really hard time understanding what exactly these functions are doing. Here is what I have:

(define (myMap f l)
    (fold-left (lambda (f a) (f a)) '() l))

(define (myFilter f l)
    (fold-left f '() l))

The bottom one is what I intuitively thought it should be. Apply a filter (say number? to every element of l and put the result in the null list). The top is just completely wrong but I feel like that is more on the right track. Using some kind of lambda function to apply the function to a number?

Here is an example of the output I am looking for:

(myMap sqrt '(4 9 16 25)) ; (2 3 4 5)
(myFilter odd? '(1 2 3 4 5)) ; (1 3 5)

Best Answer

Both fold-left and fold-right reduces one or more list with a reducing procedure from first to last element, but the order it is applied is kept in fold-right while it is reversed in fold-left. It's easily shown if you do the following:

#!r6rs
(import (rnrs))

;; helper for R6RS fold-left since argument order is swapped
(define (xcons d a) 
  (cons a d))

(fold-left xcons '() '(1 2 3 4)) ; ==> (4 3 2 1)
(fold-right cons '() '(1 2 3 4)) ; ==> (1 2 3 4)

The reason I made xcons is that for left-fold the accumulator is the first argument. In SRFI-1 List library fold-left equvivalent is just called fold and has the same argument order as fold-right:

(import (rnrs base)
        (only (srfi :1) fold fold-left))

(fold cons '() '(1 2 3 4))       ; ==> (4 3 2 1)
(fold-right cons '() '(1 2 3 4)) ; ==> (1 2 3 4)

A left fold is tail recursive since it processes the first element and it becomes the accumulator for the next iteration. A right fold need to cons the last element to the accumulator before consing the second last all the way to the first. This means a right fold should be avoided if possible and in many cases where the order of the result or you fold down to a single value (eg. finding max element) a left fold is ok.

In the case of map and filter you expect the result to be in the same order so you need to always use a fold-right.

For a map you need to make a procedure that cons the result of applying the supplied procedure to an element with the accumulator. This is what fold-right needs to get a list in the end. Your current solution doesn't have any cons so you won't get a list.

For a filter you need to make a procedure that cons the original element to the accumulator if the result of the predicate is a true value and just evaluate the accumulator if it isn't.

Since I think this is homework I'll leave you to do the actual implementation. Happy hacking.

Related Solutions

How to know when to use fold-left and when to use fold-right

You can transfer a fold into an infix operator notation (writing in between):

This example fold using the accumulator function x

fold x [A, B, C, D]

thus equals

A x B x C x D

Now you just have to reason about the associativity of your operator (by putting parentheses!).

If you have a left-associative operator, you'll set the parentheses like this

((A x B) x C) x D

Here, you use a left fold. Example (haskell-style pseudocode)

foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative

If your operator is right-associative (right fold), the parentheses would be set like this:

A x (B x (C x D))

Example: Cons-Operator

foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3]

In general, arithmetic operators (most operators) are left-associative, so foldl is more widespread. But in the other cases, infix notation + parentheses is quite useful.

Truly understanding the difference between procedural and functional

Functional Programming

Functional programming refers to the ability to treat functions as values.

Let's consider an analogy with "regular" values. We can take two integer values and combine them using the + operator to obtain a new integer. Or we can multiply an integer by a floating point number to get a floating point number.

In functional programming, we can combine two function values to produce a new function value using operators like compose or lift. Or we can combine a function value and a data value to produce a new data value using operators like map or fold.

Note that many languages have functional programming capabilities -- even languages that are not usually thought of as functional languages. Even Grandfather FORTRAN supported function values, although it did not offer much in the way of function-combining operators. For a language to be called "functional", it needs to embrace functional programming capabilities in a big way.

Procedural Programming

Procedural programming refers to the ability to encapsulate a common sequence of instructions into a procedure so that those instructions can be invoked from many places without resorting to copy-and-paste. As procedures were a very early development in programming, the capability is almost invariably linked with the style of programming demanded by machine- or assembly-language programming: a style that emphasizes the notion of storage locations and instructions that move data between those locations.

Contrast

The two styles are not really opposites -- they are just different from one another. There are languages that fully embrace both styles (LISP, for example). The following scenario may give a sense of some differences in the two styles. Let's write some code for a nonsense requirement where we want to determine if all of the words in a list have an odd number of characters. First, procedural style:

function allOdd(words) {
  var result = true;
  for (var i = 0; i < length(words); ++i) {
    var len = length(words[i]);
    if (!odd(len)) {
      result = false;
      break;
    }
  }
  return result;
}

I'll take it as a given that this example is comprehensible. Now, functional style:

function allOdd(words) {
  return apply(and, map(compose(odd, length), words));
}

Working from the inside out, this definition does the following things:

compose(odd, length) combines the odd and length functions to produce a new function that determines whether the length of a string is odd.
map(..., words) calls that new function for each element in words, ultimately returning a new list of boolean values, each indicating whether the corresponding word has an odd number of characters.
apply(and, ...) applies the "and" operator to the resulting list, and-ing all of the booleans together to yield the final result.

You can see from these examples that procedural programming is very concerned with moving values around in variables and explicitly describing the operations needed to produce the final result. In contrast, the functional style emphasizes the combination of functions required to transform the initial input to the final output.

The example also shows the typical relative sizes of procedural versus functional code. Furthermore, it demonstrates that the performance characteristics of procedural code might be easier to see than that of functional code. Consider: do the functions compute the lengths of all of the words in the list, or does each stop immediately after finding the first even length word? On the other hand, the functional code permits a high-quality implementation to perform some pretty serious optimization since it primarily expresses intent rather than an explicit algorithm.

Further Reading

This question comes up a lot... see, for example:

John Backus' Turing award lecture spells out the motivations for functional programming in great detail:

Can Programming Be Liberated from the von Neumann Style?

I really shouldn't mention that paper in the present context because it gets pretty technical, pretty quickly. I just couldn't resist because I think it is truly foundational.

Addendum - 2013

Commentators point out that popular contemporary languages offer other styles of programming over and above procedural and functional. Such languages often offer one or more of the following programming styles:

query (e.g. list comprehensions, language-integrated query)
dataflow (e.g. implicit iteration, bulk operations)
object-oriented (e.g. encapsulated data and methods)
language-oriented (e.g. application-specific syntax, macros)

See the comments below for examples of how the pseudo-code examples in this response can benefit from some of the facilities available from those other styles. In particular, the procedural example will benefit from the application of virtually any higher-level construct.

The exhibited examples deliberately avoid mixing in these other programming styles in order to emphasize the distinction between the two styles under discussion.

Best Answer

Related Solutions

How to know when to use fold-left and when to use fold-right

Truly understanding the difference between procedural and functional

Related Topic