Xah Talk Show 2025-10-25 Ep706 Fold and Reduce, in Wolfram Language, Emacs Lisp, JavaScript
Video Summary (AI Generated, Reviewed by Human)
This video explains fold (also known as reduce) in functional programming. The creator highlights that fold/reduce is a general way to represent any loop you would typically use in imperative languages (2:25, 9:54, 11:13, 34:21).
Here's a breakdown of the key points:
- Purpose: Unlike map, which is limited, fold (or reduce) can handle more complex loop scenarios, especially when you need to maintain a "state" or track indices (7:17, 8:01, 11:01, 13:46).
- Mechanism: It takes an initial value (the starting "state") and a function that processes each item from a list along with the accumulated "state" from the previous iteration (8:50, 9:12, 19:30, 20:20, 1:05:08).
- Demonstrations: The video shows examples of fold in Wolfram Language (17:30) and reduce in JavaScript (22:29) and Emacs Lisp (28:47).
- Terminology: The creator discusses why some languages use "fold" and others use "reduce." Historically, both terms come from theoretical computer science (33:36).
- Some languages even have both, with "fold" typically taking an initial value and "reduce" not (36:02, 38:09).
- The creator argues "fold" is a better term because "reduce" can be misleading, implying only a "many-to-one" transformation rather than a general loop (40:10, 1:04:17).
- Parallel Computation: The video clarifies that fold/reduce itself is inherently sequential and not parallel.
- However, if the operation used within the fold/reduce has commutative (order of arguments doesn't matter, e.g., a+b = b+a) and associative (grouping of operations doesn't matter, e.g., (a+b)+c = a+(b+c)) properties, then the computation can be done in parallel (41:56, 45:00, 50:59, 55:05).
- The creator criticizes Google's "MapReduce" for misleading people into thinking reduce inherently means parallelism (58:48).
- Fold (aka Reduce) is Functional Form of Loop (2025)
- Programing Language: Fold vs Reduce
- Cpp Doc on Reduce. Incomprehensible (2025)
// loop , is fundamental in programing languages. // typically , in prodecural programing language , aka imperative languages, the most popular way of loop is the for loop. for (let i = 0; i < 9; i++) { console.log( i ) } // now in functional programing languages, the most well known form of loop is via map function [1,2,3,4].map( ((x) => { console.log( x )}) ) // but, map is not a general purpose loop // because , for example , if you are given a list, and you want to skip every other element, and apply a function to only those. // in this case, you can not use map, usually, because, you do not have the index of the element. // (in JavaScript, it actualy can do this because the function also receives the index ) // now, the functional programing form of a general purpose loop, is fold, aka reduce . // it passes the previous state to the function }
Range[6] (* {1, 2, 3, 4, 5, 6} *) Fold[f, {1, 2, 3, 4, 5, 6} ] (* f[f[f[f[f[1, 2], 3], 4], 5], 6] *) Fold[f, {1, 2, 3} ] (* f[f[1, 2], 3] *) Fold[f, {1, 2, 3, 4} ] (* f[f[f[1, 2], 3], 4] *) Fold[f, 0, {1, 2, 3, 4} ] (* f[f[f[f[0, 1], 2], 3], 4] *) (* HHHH------------------------------ *) FoldList[f, {1, 2, 3, 4} ] (* {1, f[1, 2], f[f[1, 2], 3], f[f[f[1, 2], 3], 4] } *)
const xarray = ["1","2","3","4","5"] const xresult = xarray. reduce( ((a,b) => (a+b)) ) console.log( xresult ) // 12345 // xarray. reduce( ((a,b) => (a+b)), initialValue ) const xx = [1, 2, 3, 4]; const f = ((x, y) => `f(${x},${y})`); console.log(xx.reduce(f) === "f(f(f(1,2),3),4)"); // true
(setq xx (vector "a" "b" "c")) (seq-reduce (lambda (x y) (concat x y)) xx "") ;; "abc"