反復諸法 - 畳み込み、写像（続いた）

[.｡oO(さっちゃんAdvent Calendar) : ATND http://atnd.org/events/22829 ]3日目
[反復諸法 - 繰り返し、イテレータ、再帰、（続く） http://d.hatena.ne.jp/Kureduki_Maari/20111202/1322837213 ]の続き

アキュムレータ

反復（繰り返し構文やイテレータiterator）は、アキュムレータacumlatorを使った反復的再帰の特殊記法であるともいえます。

// D Programming Language
void main(string[] args) {
  int[2] acm;
  int[] list = [3, 1, 4, 1, 5, 9, 2];

  // conuterアキュムレータ
  for (acm[0] = 0, int len = list.length; acm[0] < len; ++ acm[0]) {
    writeln(list[acm[0]]);
  }

  // 意味の有るアキュムレータ
  for (acm = [0, 0], int len = list.length; acm[0] < len; ++acm[0]) {
    acm[1] += list[acm[0]];
  }
  writeln(acm[1]);

  // イテレータ
  acm[1] = 0;
  foreach (item; list) {
    acm[1] += item;
  }
  writeln(acm[1]);
}

反復的な再帰では、繰り返しを数えるだけの、カウンタアキュムレータは要りません。

;Scheme
;再帰的recursive
(let (li (list 3 1 4 1 5 9 2))
     (define (sum items)
       (if (null? items)
           0
           (+ (car items)
              (sum (cdr items)))))
     (sum li))

;反復的iterative
(let (li (list 3 1 4 1 5 9 2))
     (define (sum items acm)
       (if (null? items)
           acm
           (sum (cdr items) (+ (car items) acm))))
     (sum li 0))

畳み込み

反復を一般化してみましょう。

-- Haskell
-- アキュムレータを使った反復的再帰
sum xs = helper 0 xs
         where helper acm (x:xs) = helper (acm + x) xs
               helper acm _      = acm

-- 畳み込み
sum = foldr (+) 0

// JavaScript
// アキュムレーション再帰
function sum (list) {
  function iter (list, acm) {
    if (list.length) {
      return acm;
    } else {
      acm += list.pop();
      return iter(list, acm);
    }
  }

  return iter(list, 0);
}

// 畳み込み
function sum (list) {
  return list.reduceRight(function (left, right) {
    return left + right;
  }, 0);
}

写像

時間切れだし！

-- Haskell
map (\x -> x + 1) [3, 1, 4, 1, 5, 9, 2]

# Ruby
[3, 1, 4, 1, 5, 9, 2].map{|num| num + 1}

// JavaScript
// 再帰
(function (list) {
  var first;

  if (list.length) {
    return [];
  } else {
    first = list.shift();
    return [first + 1].concat(arguments.callee(list));
  }
}([3, 1, 4, 1, 5, 9, 2]));

// アキュムレーション再帰
(function (list) {
  function iter (list, acm) {
    var last;

    if (list.length) {
      return acm;
    } else {
      last = list.pop();
      return iter(list, acm.concat(last + 1));
    }
  }

  return iter(list, []);
}([3, 1, 4, 1, 5, 9, 2]));

// 写像
[3, 1, 4, 1, 5, 9, 2].map(function (num) {
  return num + 1;
});

// 畳み込みに依る写像
[3, 1, 4, 1, 5, 9, 2].reduce(function (left, right) {
  return left.concat(right + 1);
}, []);

もういやだ続きません