Hatena::Grouperlang

檜山正幸のErlang未確認情報 RSSフィード

 | 

2009-03-17 (火)

Before/Afterリスト方式によるストリーム風処理

| 09:42

データ処理の中間結果を引数に保持しながら、再帰呼び出しを次々と行う方式はすごく多用される。データはリストや文字列整数のリストに過ぎない)だが、ストリームのイメージで扱うときにこの方法が使われる。

まずは実例、文字列の大文字化(string:to_upper/1と同じ)。

%% -*- coding: utf-8 -*-

%% @doc
-module(toupper).
-export([to_upper/1]).

%% @doc アスキー英小文字を大文字にする
%% @spec char_to_upper(char()) -> char()
char_to_upper(C) ->
  if ($a =< C andalso C =< $z) -> 
      C - 32;
     true ->
      C
  end.

%% @doc 文字列を大文字化する
%% @spec to_upper(string()) -> string()
to_upper(S) ->
  to_upper(S, []).

to_upper([Before1|BeforeRest], After) ->
  to_upper(BeforeRest, [char_to_upper(Before1)|After]);
to_upper([], After) ->
  lists:reverse(After).

まだ処理してないデータを第1引数、処理後のデータを最後の引数、必要なら中間結果を保持する引数を何個か入れる。要素に対する処理をFunとすると、

  • [B|Bs], A → Bs, [Fun(B)|As]

というステップを重ねるのが基本。

で、何が言いたいかというと、最後にreverseが必要。僕は毎度忘れる^^;

Erlangに限らずリスト処理では、先頭への追加(cons)は軽いが、末尾への追加は重い。とはいえフィルター処理では、入力ストリーム先頭から読んだモノは、出力ストリーム末尾に吐き出すのであって、「入力ストリーム先頭→加工→出力ストリーム先頭」では、出力側が逆順になる。そこでreverseが登場するわけだ。

Erlangのlists:reverseがメチャガンバッテ最適化されているのは、この用途に多用するからでしょ、たぶん。

[追記]追加サンプル

これは Before/Afterと雰囲気が違う。が、スタックにまず展開してから、それを畳みながら計算するのとも違う。

index(A, List)  ->
  index(A, 1, List).

index(_A, _N, []) ->
  -1;
index(A, N, [A|_]) ->
  N;
index(A, N, [_|Rest]) ->
  index(A, N + 1, Rest).

[/追記]

 |