JavaScript

JavaScript 再帰による実装例いろいろ

  • 昔Haskellをみていた時に、ループなしで再帰だけでなんでもできるんだなーと思ってjsで色々実装した思い出が発掘されたので移設
  • コメントのa -> [a] -> [a]みたいなやつは、Haskellの...なんというやつだったかな
  • (この場合、値と値の配列を渡すと値の配列が帰ることを表現している..はず)
  • 型の推移を最初に意識して実装ができれば、Javaなどでも役に立つのではと思った記憶があり。
  • 業務のコードで勝手に再帰しばりをやっていたら失職するでしょう。
//***準備開始

//a -> [a] -> [a]
function con(v, ary) {
  return [v].concat(ary);
}

//a -> [a] -> [a]
function con2(ary, v) {
  return ary.push(v);
}

//(Ord a) => a -> a -> Bool
function max(a, b) {
  return a > b ? a : b;
}
//***準備終了

//最大値取得
//(Ord a) => [a] -> a
function getMaximum(ary) {
  if (!ary) {
    throw "error bad param.";
  }

  if (ary.length == 0) {
    throw "error empty.";
  } else if (ary.length == 1) {
    return ary[0];
  } else {
    var x = ary.shift();

    //再帰呼出し
    return max(x, getMaximum(ary));
  }
}

//値を指定個数繰り返し配列に
//Int -> a -> [a]
function replicate(n, v) {
  if (n <= 0) {
    return [];
  } else {
    //再帰呼出
    return con(v, replicate(n - 1, v));
  }
}

//配列の要素を先頭から取得
//(Num n, Ord n) => n -> [a] -> [a]
function take(n, ary) {
  if (n <= 0) {
    return [];
  } else if (ary.length == 0) {
    return [];
  } else {
    var v = ary.shift();

    //再帰呼出
    return con(v, take(n - 1, ary));
  }
}

//配列の要素を逆転
//[a] -> [a]
function reverse(ary) {
  if (ary.length == 0) {
    return [];
  } else {
    var v = ary.shift();

    //再帰呼出
    return reverse(ary).concat([v]);
  }
}

//2つの配列の要素をまとめて配列の要素に
//[a] -> [b] -> [(a,b)]
function zip(ary1, ary2) {
  if (ary1.length == 0) {
    return [];
  } else if (ary2.length == 0) {
    return [];
  } else {
    var v1 = ary1.shift();
    var v2 = ary2.shift();
    var v = [v1, v2];

    return con(v, zip(ary1, ary2));
  }
}

//配列に値が存在するか
//(Eq a) => a -> [a] -> Bool
function elem(v, ary) {
  if (ary.length == 0) {
    return false;
  } else {
    var x = ary.shift();

    if (v == x) {
      return true;
    } else {
      return elem(v, ary);
    }
  }
}

//テスト開始
var a = [3, 2, 5, 20, 4, 2];
var b = [1, 2, 3, 4];

//a.slice(0)は、配列の複製です。参照渡しでaの中身が変わらないようにしてます。

console.log(getMaximum(a.slice(0))); //20

console.log(replicate(3, 5)); //[5,5,5]

console.log(take(2, a.slice(0))); //[3,2]

console.log(reverse(a.slice(0))); //[2,4,20,5,2,3]

console.log(zip(a.slice(0), b.slice(0))); //[[3,1],[2,2],[5,3],[20,4]]

console.log(elem(5, a.slice(0))); //true

console.log(elem(999, a.slice(0))); //false

//step2

//配列の要素それぞれに関数を適用し、新しい配列を返す
//(a -> b) -> [a] -> [b]
function map(f, ary) {
  if (ary.length == 0) {
    return [];
  } else {
    var v = ary.shift();

    return con(f(v), map(f, ary));
  }
}

var a = [3, 2, 5, 20, 4, 2];

console.log(map(function(n) {
    return n * 2;
  }, a.slice(0))
); //[6,4,10,40,8,4]