// Imagine you have a function that takes two arguments in
//  its most basic form, like + or *. You may want to generalize
//  this function to any number of arguments, like summing up
//  a list, or otherwise zipping down that list applying your
//  function as you go. Similarly, you may want to get not
//  just a number, but to make a shallow copy of the list,
//  while also applying some operation to its members, or
//  to reverse the list. 

// For any of these tasks, you don't want to write a new special
//  function to work on lists. Traversing a list is a generic
//  operation---after all, whatever you do, you need to take
//  cars and cdrs, and recurse; these parts are alike for list
//  traversals. So you shouldn't have to write that traversal
//  code more than once; less code, fewer bugs.

// Indeed, LISP has a trick for taking a function for a basic
//  operation and making one that works on lists out of it.
//  This trick is called _folding_, and can be done in two
//  ways, from the left, or from the right. The folding function
//  contains all the logic for traversing the list and feeding
//  the right pairs of arguments to your basic operation.

// Folding takes some getting used to, but it's important to
//  understand the LISP recursive way of programming.

$ gcl
GCL (GNU Common Lisp)  2.6.12 ANSI    Nov 27 2014 05:23:43
Source License: LGPL(gcl,gmp), GPL(unexec,bfd,xgcl)
Binary License:  GPL due to GPL'ed components: (READLINE UNEXEC)
Modifications of this banner must retain notice of a compatible license
Dedicated to the memory of W. Schelter

Use (help) to get some basic information on how to use GCL.
Temporary directory for compiler files set to /private/var/folders/1h/3prjrhy96y55j8jrvttgd_kw0000gp/T/

// REDUCE is Common Lisp's native library function for doing folding:

>(help 'REDUCE)

-----------------------------------------------------------------------------
REDUCE                                                             [Function]
(not found "gcl.info")
From ((REDUCE . Sequences and Arrays and Hash Tables) gcl-si.info):

 -- Function: REDUCE (function sequence &key (from-end nil) (start 0)
          (end (length sequence)) initial-value)
     Package:LISP

     Combines all the elements of SEQUENCE using a binary operation
     FUNCTION. If INITIAL-VALUE is supplied, it is logically placed
     before the SEQUENCE.
-----------------------------------------------------------------------------

// In its basic form, REDUCE takes a binary function and a list,
//   and applies that function to the first pair of members in the
//   list, then to the result and the third member, and so on, 
//   until the list is exhausted. 

// To wit:

>(reduce '* '(1 2 3 4))

24

>(reduce '+ '(1 2 3 4))

10

>(reduce 'max '(1 2 3 4))

4

>(reduce 'max '(100 2 3 4))

100

// You can see the order in which it does it by feeding it CONS
//  as the basic two-argument function:

>(reduce 'cons '(100 2 3 4))

(((100 . 2) . 3) . 4)

>(reduce 'cons '(a b c d))

(((A . B) . C) . D)

// It works similarly with LIST:

>(reduce 'list '(a b c d))

(((A B) C) D)

// With an optional keyword argument, it can work from
//  the other direction, first making (C . D), then (cons B (C .D)),
//  which produced (B C . D), then (cons A (B C . D)), i.e.,
//  the final result (A B C . D):

>(reduce 'cons '(a b c d) :from-end t)

(A B C . D)

// The same with LIST (be sure to step through it to understand how
//  the result comes about!)

>(reduce 'list '(a b c d) :from-end t)

(A (B (C D)))

// Feeding CONS to folding/reducing from the right _almost_ makes
//   a shallow copy of the list. The dotted pair with D spoils it;
//   if only we could start with our own value to feed in first,
//   so that the first operation is not (cons C D) making the ugly (C . D),
//   but (D . nil):

>(reduce 'cons '(a b c d) :from-end t)

(A B C . D)

>(reduce 'cons '(a b c d nil) :from-end t)

(A B C D)

// Luckily, these is an option to provide this extra value. 
// This is a "shallow copy" of the original list!

>(reduce 'cons '(a b c d) :from-end t :initial-value nil)

(A B C D)

// Applying LIST helps understand the order. First you
//  get (list D nil), then (list C (list D nil)), then
//  (list B (list C (list D nil))), etc:

>(reduce 'list '(a b c d) :from-end t :initial-value nil)

(A (B (C (D NIL))))

// So we can make a shallow copy of the list. Can we reverse
//  it with folding? We should be able to. Of course, there
//  is a standard library function for reversing a list---
//  also look up NREVERSE---but we want to do it with folding.

>(help 'reverse)

-----------------------------------------------------------------------------
REVERSE                                                            [Function]
(not found "gcl.info")
From ((REVERSE . Sequences and Arrays and Hash Tables) gcl-si.info):

 -- Function: REVERSE (sequence)
     Package:LISP

     Returns a new sequence containing the same elements as SEQUENCE but
     in reverse order.
-----------------------------------------------------------------------------

// So let's try to make reverse with reduce.

>(reduce 'cons '(a b c d) :from-end t :initial-value nil)

(A B C D)

// reversing a list means taking its car and putting it behind the rest
//  of the list. Our first try was:

>(reduce (lambda (x y) (cons y x)) '(a b c d) :from-end t :initial-value nil)

((((NIL . D) . C) . B) . A)

// Looks like we are on the right track, but there are extra cons cells
//  being created along the way. A couple more tries:

>(reduce (lambda (x y) (cons y x)) '(a b c d) :from-end t)

(((D . C) . B) . A)

>(reduce (lambda (x y) (list y x)) '(a b c d) :from-end t)

(((D C) B) A)

// If you want to see the most efficient solution, skip to (**) below.
//   Long story short, it works much better working from the beginning of
//   the list, not the end!

// The order of arguments seems right, but we want to consume these
//   extra cons cells somehow. A bit of cheating:

>(help 'append)

-----------------------------------------------------------------------------
APPEND                                                             [Function]
(not found "gcl.info")
From ((APPEND . Lists) gcl-si.info):

 -- Function: APPEND (&rest lists)
     Package:LISP

     Constructs a new list by concatenating its arguments.
-----------------------------------------------------------------------------

>(append '(1) '(2))

(1 2)

>(append '(1) '(2 3))

(1 2 3)

// So append removes some unwanted cons cells. Let's try it:

>(reduce (lambda (x y) (append y x)) '(a b c d) :from-end t)

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by APPEND.
Condition in APPEND [or a callee]: INTERNAL-SIMPLE-TYPE-ERROR: D is not of type LIST: 

Broken at APPEND.  Type :H for Help.
    1  Return to top level. 
>>1

>(reduce (lambda (x y) (append y x)) '(a b c d) :from-end t :initial-value nil)

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by APPEND.
Condition in APPEND [or a callee]: INTERNAL-SIMPLE-TYPE-ERROR: D is not of type LIST: 

Broken at APPEND.  Type :H for Help.
    1  Return to top level. 
>>1

Top level.

// trying things around---see why each fails!

>(reduce (lambda (x y) (append (list y) x)) '(a b c d) :from-end t :initial-value nil)

((((NIL . D) . C) . B) . A)

>(reduce (lambda (x y) (append (list y) x)) '(a b c d) :from-end t )

(((D . C) . B) . A)

>(reduce (lambda (x y) (append (list y) (list x))) '(a b c d) :from-end t )

(((D C) B) A)

>(reduce (lambda (x y) (append y (list x))) '(a b c d) :from-end t )

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by APPEND.
Condition in APPEND [or a callee]: INTERNAL-SIMPLE-TYPE-ERROR: D is not of type LIST: 

Broken at APPEND.  Type :H for Help.
    1  Return to top level. 
>>1

Top level.

// Finally it works.

>(reduce (lambda (x y) (append y (list x))) '(a b c d) :from-end t :initial-value nil)

(D C B A)

// Yay! We have reverse. Note that this is inefficient, because 
//  what we want is a function FOO such that (FOO 'D nil) gives us (D), then (FOO 'C '(D)) 
//  gives us (D C), (FOO 'B '(D C)) gives (D C B), and so on. APPEND with flipped arguments does that above,
//  but APPEND (or NCONC) needs to chase the list to its end to append another list!

// Note that we've been folding from the end of the list. Maybe working from
//  the front will be easier? 

>(reduce (lambda (x y) (cons y x))  '(a b c d) )

(D C B . A) 

// Almost there! We just need to feed in the initial value of nil:
// (**)

>(reduce (lambda (x y) (cons y x))  '(a b c d) :initial-value nil)

(D C B A)

// OK, this finally works right.

// Now length can also come from folding. Figure out why this works,
//  and what would happen if you used (lambda (x y) (+ y 1)) instead
//   (I mistyped so in my notes).

>(reduce (lambda (x y) (+ x 1)) '(a b c d) :initial-value 0)

4

>(reduce (lambda (x y) (+ x 1)) '() :initial-value 0)

0

>(reduce (lambda (x y) (+ x 1)) '(a) :initial-value 0)

1

>(reduce (lambda (x y) (+ x 1)) '(a b) :initial-value 0)

2

>(reduce (lambda (x y) (+ x 1)) '(a b c) :initial-value 0)

3

// Implementing folding from scratch. REDUCE is folding from the left by default,
//  from the right if :from-end t is used.

$ gcl
GCL (GNU Common Lisp)  2.6.12 ANSI    Nov 27 2014 05:23:43
Source License: LGPL(gcl,gmp), GPL(unexec,bfd,xgcl)
Binary License:  GPL due to GPL'ed components: (READLINE UNEXEC)
Modifications of this banner must retain notice of a compatible license
Dedicated to the memory of W. Schelter

Use (help) to get some basic information on how to use GCL.
Temporary directory for compiler files set to /private/var/folders/1h/3prjrhy96y55j8jrvttgd_kw0000gp/T/

// This is folding from the _right_ (skip to the example with LIST to see it clearly).
//  Note that in these examples the initial value is always given explicitly, while in REDUCE it's optional.

// In my first attempt, I forgot FUNCALL:

>(defun foldr (op lst init) (cond ((null lst) init) (t (op (car lst) (foldr op (cdr lst) init)))))

; Properly indented:
;(defun foldr (op lst init) 
;  (cond ((null lst) init) 
;        (t (op (car lst) 
;               (foldr op (cdr lst) init)))))

FOLDR

>(foldr '+ '(1 2 3 4) 0)

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by COND.
Condition in COND [or a callee]: INTERNAL-SIMPLE-UNDEFINED-FUNCTION: Cell error on OP: Undefined function: 

Broken at COND.  Type :H for Help.
    1  Return to top level. 
>>1

Top level.
>(defun foldr (op lst init) (cond ((null lst) init) (t (funcall op (car lst) (foldr op (cdr lst) init)))))

; Properly indented:
; (defun foldr (op lst init) 
;   (cond ((null lst) init) 
;         (t (funcall op (car lst) 
;                     (foldr op (cdr lst) init)))))

FOLDR

>(foldr '+ '(1 2 3 4) 0)

10

>(foldr '* '(1 2 3 4) 1)

24

>(foldr 'cons '(1 2 3 4) nil)

(1 2 3 4)

>(foldr 'cons '() nil)

NIL

>(foldr 'cons '(1) nil)

(1)

>(foldr 'list '(1 2 3 4) nil)

(1 (2 (3 (4 NIL))))


// When implementing folding from the left, I forgot it again...

>(defun foldl (op lst init) (cond ((null lst) init) (t (foldl op (cdr lst) (op init (car lst))))))

FOLDL

>(foldl 'list '(a b c d) nil)

Error: 
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by COND.
Condition in COND [or a callee]: INTERNAL-SIMPLE-UNDEFINED-FUNCTION: Cell error on OP: Undefined function: 

Broken at FOLDL.  Type :H for Help.
    1  Return to top level. 
>>1

Top level.
>(defun foldl (op lst init) (cond ((null lst) init) (t (foldl op (cdr lst) (funcall op init (car lst))))))

; Propely indented:
; (defun foldl (op lst init) 
;   (cond ((null lst) init) 
;         (t (foldl op (cdr lst) 
;                   (funcall op init (car lst))))))

FOLDL

>(foldl 'list '(a b c d) nil)

((((NIL A) B) C) D)

>(foldl '+ '(1 2 3 4) 0)

10

>

// We will revisit folding with Haskell, where it yields theorems 
//  (cf. http://www.cantab.net/users/antoni.diller/haskell/units/unit06.html)