In Praise of Higher Order Functions
summary
Argues that map fold scan are not just concepts but calculational tools: Haskell code, GHC rewrite rules and QuickSpec find and exploit laws; list fusion via build/fold removes intermediate lists; a classic program (maximum segment sum) rewrites from O(n^3) to O(n). Shows log‑depth scan circuits for parallel GPUs/FPGAs and concrete circuit retiming laws used to implement them, and reports these transformations both compile and run with measurable performance and memory wins.
AI-written summary · about
chapters (39)
- 0:00Intro
- 1:18Map List
- 4:07John McCarthy
- 16:03Cartesian Product
- 21:18Straight Paper
- 22:47APL
- 23:51Books
- 24:35notation as a tool of thought
- 25:17John Backus
- 25:39Fortran
- 27:01Conventional Programming Languages
- 28:53Functional Representations
- 29:50Intermediate Lists
- 31:01Formal Methods
- 31:27Oxford Program Research Group
- 32:27John Hughes
- 34:20Paper Writing
- 35:24Bird Merchants Formalism
- 36:29The Squiggle List
- 36:45The Secret Society
- 37:09Graham Hutton
- 43:10Playing by the Rules
- 44:05Build
- 46:47Scannell
- 47:21Richard Byrd
- 48:26The Fold
- 49:05Maximum Segment Sum
- 49:24Program Calculation
- 50:18Sequential Scan
- 51:13Log Depth Scan
- 52:48Bitwise Operations
- 53:50Log Depth
- 54:26Power of Scan
- 54:55GPU Scan
- 55:09Skeletons
- 56:35Where are we now
- 57:26What should programmers do now
- 57:52Lowlevel details
- 58:29Information security
related talks
44mFunctional Array Funhouse Intensive - Part 5 of 5
58mFunctional Array Funhouse Intensive - Part 2 of 5
24mAccelerating Haskell GPGPU Programming with Haskell
02h 50mFunctional Array Funhouse Intensive - Part 3 of 5
59mLet's Get Lazy
47mFunctional Array Funhouse Intensive - Part 4 of 5
50mIs scala code slow?
01h 37mAn Overview of Program Optimization Techniques