CODEWITHSUNDEEP
schemereducefoldmit-scheme
Anandamide
Anandamide

Reputation: 243

What direction is the fold procedure in MIT Scheme?

If I want to reverse a list in MIT Scheme, I can do it with (fold cons '() list) such that if list is (define lis '(1 2 3 4)), then (fold cons '() lis) gives (4 3 2 1). There are two kinds of folds, left and right folds, but if I use (fold-right cons '() lis), I get (1 2 3 4) so the plain fold can't be that one. Also if I use (fold-left cons '() lis) I get ((((() . 1) . 2) . 3) . 4) so that also cannot be the fold in the original example. what kind of fold is needed to reverse a list?

I ask because I want to be able to make a generic fold such that:

(define ls '((1 2 3) (4 5 6)))
(gen-fold cons '() ls)
=> ((6 5 4) (3 2 1))
(define l2 '(((1 2) (2 3)) ((3 4) (4 5))))
(gen-fold cons '() ls)
=> (((5 4) (4 3)) ((3 2) (2 1)))

Edit: Inorder to better present the questions, these diagrams depict the rotation of the list that I believe to be happening when '(fold cons '() '(1 2 3)) is called assuming that fold is a modified fold-left as per alexis king:

(define lis (list '(1 2 3))

     cons
    /   \
   1    cons
        /  \
       2   cons
           /  \
          3   '()

(cons lis '())

         cons
        /  \
      cons '()
     /  \
    1   cons
       /   \
      2    cons
           /  \
          3   '()

(fold-left (cons lis '()))

        cons
       /    \
    cons     cons
   /  \      /  \
  2   cons  1   '()
      /  \
     3   '()


        cons
       /    \
    cons     cons
   /  \       /  \
  3   '()    2    cons
                  /   \
                1     '()

   cons
  /  \
 3   cons
     /  \
    2   cons
        /  \
       1   '()

Upvotes: 1

Views: 360

Answers (1)

Alexis King
Alexis King

Reputation: 43872

MIT Scheme does not include a fold function in its base library, only fold-left and fold-right. However, there does exist a fold function as declared by SRFI-1, which is supported by MIT Scheme and exhibits the behavior you describe.

The fold function is a left fold—that is, it accumulates the list by left-to-right iteration—but it differs from MIT Scheme's fold-left function in that the argument order of the accumulator procedure is flipped. That is, fold applies the supplied procedure with the accumulator argument last, while fold-left applies the procedure with the accumulator argument first.

To illustrate that point, this is how one could define fold in terms of fold-left:

(define (fold proc init lst)
  (fold-left (lambda (x acc) (proc acc x)) init lst))

In my experience, the fold argument order tends to be more common among Lisp implementations, while the fold-left argument order tends to be more common among other functional languages. The reason for the acc argument to be supplied last is for precisely the reason you discovered: it makes it easier to use fold with cons-like procedures that accept the accumulated value as their second argument.

As an aside, you appear to have mixed up fold-left and fold-right in your original question: it is fold-right that returns the list unchanged and fold-left that returns the inverted set of pairs. If you understand how fold-left and fold-right are defined, this makes sense.

In a certain sort of way, both fold-left and fold-right fold over lists starting from the left, since Scheme lists are singly-linked and cannot be read from the right. The difference is that left folding is iterative while right folding is recursive.

A left fold applies a procedure to each element one by one, then threads the result into the next application. This ends up reversing the order of the elements when viewed as nested applications:

(proc eN ... (proc e1 (proc e0 init)) ...)

In contrast, a right fold applies the procedure recursively, keeping the order consistent in nested applications:

(proc e0 (proc e1 ... (proc eN init) ...))

When used with cons, the left fold reverses, but the right fold is just the identity.

(This is potentially more interesting in lazy languages like Haskell because right folding does not depend on the entire list despite supposedly starting "from the right", so it can operate on infinite streams... however, this is much less relevant in Scheme.)

Upvotes: 5

Related Questions