On Fri, Sep 7, 2012 at 8:37 PM, Stephen Tetley <stephen.tetley@gmail.com> wrote:
For foldr see Olivier Danvy and Michael Spivey's "On Barron and
Strachey’s Cartesian Product Function" crediting a discovery to David
Barron and Christopher Strachey.

http://www.brics.dk/RS/07/14/BRICS-RS-07-14.pdf

That gives the date as 1966.

APL had the fold operator -- called 'reduce' in APL terminology and notated with a slash '/' -- from around 1960
http://www.softwarepreservation.org/projects/apl/book/APROGRAMMING%20LANGUAGE/view
is the 1962 book. Apl as a notation had existed some time before that.