読者です 読者をやめる 読者になる 読者になる

Haskell 勉強中

引越し後、一向に工作環境が整わないのでZ80プロジェクトも絶賛放置中。ベッドもまだないけど、いい加減に作業机買わないと……。

そんなわけで?最近の家での時間潰しはPCにかじりついてソフトウェア関係の勉強です。「Deep Learning やりたい!」から始まったはずが「なんか関数言語触っておかなきゃ」という所に落ち着いて Haskell 弄ってます。すごいH本も買いましたよ。

手応えとしては、普段 JavaScript で Function を投げつけ合うコードを書いているせいか、関数型言語の世界観に意外とすんなり入れている気がします。もちろんこの先に壁は有るんでしょうが。

再帰によるリスト処理

すごいH本は現在1/4を過ぎたあたり。ここまでだと標準のリスト処理関数を再帰で実装するくだりのところがパズルを解いてるみたいで面白かったです。「カリー化された関数」という世界観に慣れるため JavaScript でも実装しながら理解を確かめました。以下、メモ的にそのコードを載せてみます。

まずはコードからノイズを減らすためにちょっとしたイディオムを定義。

// リストの先頭要素を返す
Object.defineProperty(Array.prototype, 'head', {
  get : function _head () {
    if (this.length <= 0) throw new Error("empty list!");
    return this[0];
  }
});

// 先頭を除いた残りのリストを返す
Object.defineProperty(Array.prototype, 'tail', {
  get : function _tail () {
    if (this.length <= 0) throw new Error("empty list!");
    return this.slice(1);
  }
});

// リストが空かどうかを返す
Object.defineProperty(Array.prototype, 'isEmpty', {
  get : function _isEmpty () {
    return this.length <= 0;
  }
});

次のように使います。

["Miho", "Saori", "Hana", "Yukari", "Mako"].head;
//=> "Miho"

["Miho", "Saori", "Hana", "Yukari", "Mako"].tail;
//=> ["Saori", "Hana", "Yukari", "Mako"]

["Miho", "Saori", "Hana", "Yukari", "Mako"].isEmpty;
//=> false
[].isEmpty;
//=> true
sum

まずは小手調べ、リストの要素の合計値を出す sum です。

function sum (list) {
  if (list.isEmpty) return 0;
  return list.head + sum(list.tail);
}

sum([1,2,3,4,5,6,7,8,9,10]);
//=> 55

sum に渡すリストがどんどん短くなっていき、最後にsum([]) = 0再帰呼び出しが止まって計算の解決が始まります。 実行順はそうなんですが、考え方としてはまず「空のリストの合計値はどう考えても 0 だよね」という自明な部分から出発するのがポイントのよう。

再帰の部分は問題を分解して考えます。 「リストの合計値は、先頭の要素と先頭以外の要素からなるリストの合計値を足したもの」と考えて、 【先頭以外の要素からなるリスト】に対して再び「リストの合計値は、~」を適用していくことで全体の合計値を計算します。

maximum

リスト中の最大値となる要素を返す。リストを引数に取って値を返す点では sum と同じです。

function maximum(list) {
  if (list.isEmpty) throw new Error("empty list!");
  if (list.length === 1) return list.head;
  return Math.max(list.head, maximum(list.tail));
}

maximum([6,1,3,10,8,2,50000,7,9,4]);
//=> 50000

「空のリストに最大値も何もねーだろ(エラー)」「リストに要素が1個しかなければそれが最大値」が、自明な部分。 「リストの最大値は、先頭の要素と、先頭以外の要素からなるリストの最大値のうち、大きい方」が、再帰の部分。


とりあえずここまで。1引数関数の実装だけだったのでカリー化がまだ未登場、つまり Haskell っぽいことはほとんど出てきてなくて、ただ JavaScript を書いただけです。何だこの記事。次回ではその辺りを……。