高階関数
prefix scan(英語版)(あるいは単にscan)とは、リストの各要素に対して繰り返し演算を行い累積した計算結果のリストを返す高階関数である。schemeでの実装例は以下のようになる。
prefix scanの中で、特に和の演算はprefix sum, cumulative sumとも呼ばれる。ここでは先ほど定義したscanを使用して'(1 2 3 4 5 6 7 8 9 10)のprefix sumを求める例を示す。
prefix scanは並列アルゴリズム、GPGPUの分野で研究される。またprefix sumの特殊系としてsegmented scan(英語版)もある。