erlang foldl

日本語で読める Haskell の入門書といえば今では
@kazu_yamamoto訳のプログラミングHaskellなわけです
何が素晴らしいって

オーム社の方曰く「ソフトカバーなのに、ハードカバーのように平たく開ける特殊な製本」だそうです。

もぉこれが気になって気になって買ってしまいました
や、無いんです、近所に、立ち読みとかできそうなところが

原著も素晴らしいんですが訳も素晴らしくって
付録に「訳者による関数の解説」とかまで付いてて至れりつくせり

で、Haskell っつったらモナドですよモナド
この本だと第8章「関数型パーサー」、第9章「対話プログラム」で
モナドっぽいものをすこーしずつ見ながら
第10章「型とクラスの定義」で「モナド型」の説明が出てきます。

でもね、(>>=) とかはもぉ第8章から出てるの

type Parser a = String -> [(a, String)]

parse :: Parser a -> String -> [(a, String)]
parse p inp = p inp

(>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= f = \inp -> case parse p inp of
                          [] -> []
                          [(v, out)] -> parse (f v) out

みたいな感じで

原著のサポートページみたいのでは第8章で使ってるコード載せてるんだけど

> instance Monad Parser where
>    return v                   =  P (\inp -> [(v,inp)])
>    p >>= f                    =  P (\inp -> case parse p inp of
>                                                []        -> []
>                                                [(v,out)] -> parse (f v) out)

インスタンスにしてる!!
なんでもぉあれですよ、本を写経してみても実行しようとしたら

*Main> :t (>>=)

<interactive>:1:0:
    Ambiguous occurrence `>>='
    It could refer to either `Main.>>=', defined at ggutter.hs:7:2
                          or `Prelude.>>=', imported from Prelude

みたいなこと言われて
「>>= あいまいだからちゃんとモジュール指定すれ」って怒られちゃうの

むきー!! ということで Erlang で写経し直してみました

-module(parser).
-compile(export_all).

return(V) -> fun(Inp) -> [{V, Inp}] end.

failure() -> fun(_) -> [] end.

item() ->
  fun(X) ->
    case X of
      [] -> [];
      [H|T] -> [{H,T}]
    end
  end.

parse(P, Inp) -> P(Inp).

bind(A, F) ->
  fun(Inp) ->
    case parse(A, Inp) of
      [] -> [];
      [{V, Out}] -> parse(F(V), Out)
    end
  end.

l_or_r(P, Q) ->
  fun(Inp) ->
    case parse(P, Inp) of
      [] -> parse(Q, Inp);
      [{V, Out}] -> [{V, Out}]
    end
  end.

sat(P) ->
  bind(
    item(), fun(X) ->
      case P(X) of
        true -> return(X);
        false -> failure()
      end
    end).

is_digit(X) -> (X >= $0) and (X =< $9).
is_lower(X) -> (X >= $a) and (X =< $z).
is_upper(X) -> (X >= $A) and (X =< $Z).
is_alpha(X) -> is_lower(X) or is_upper(X).
is_alphanum(X) -> is_digit(X) or is_alpha(X).
is_space(X) -> X =:= $ .

digit() -> sat(fun is_digit/1).
lower() -> sat(fun is_lower/1).
upper() -> sat(fun is_upper/1).
letter() -> sat(fun is_alpha/1).
alphanum() -> sat(fun is_alphanum/1).

char(X) -> sat(fun(Y) -> X =:= Y end).
string([]) -> return([]);
string([H|T]) ->
  bind(char(H), fun(_) ->
  bind(string(T), fun(_) ->
       return([H|T])
  end) end).

many(P) ->
  l_or_r(many1(P), return([])).
many1(P) ->
  bind(P, fun(H) -> 
  bind(many(P), fun(T) ->
       return([H|T])
  end) end).

ident() ->
  bind(lower(), fun(H) ->
  bind(many(alphanum()), fun(T) ->
       return([H|T])
  end) end).

nat() ->
  bind(many1(digit()), fun(X) ->
       {Nat, _} = string:to_integer(X),
       return(Nat)
  end).

space() ->
  bind(many(sat(fun is_space/1)), fun(_) ->
       return({}) end).

token(P) ->
  bind(space(), fun(_) ->
  bind(P, fun(V) ->
  bind(space(), fun(_) ->
       return(V)
  end) end) end).

identifier() -> token(ident()).
natural() -> token(nat()).
symbol(X) -> token(string(X)).

int() ->
  l_or_r(
    bind(char($-), fun(_) ->
    bind(space(), fun(_) ->
    bind(nat(), fun(N) ->
         return(-N)
    end) end) end),
    nat()).

integer() -> token(int()).

見所は do notation っぽく見せようとしているところ

パーサーの部品とかは関数として定義しようかと思ったところ

token(fun nat/0)

みたいに
fun って付けてアリティーもどうにかしなきゃいけないのが面倒なので
関数返す関数にしてみた

で、8.8 で簡単な数式計算するのを作りましたので

-module(expr).
-compile(export_all).
-import(parser, [parse/2, item/0, symbol/1, l_or_r/2, bind/2, return/1, integer/0, l_or_r/2, many/1]).

eval(X) ->
  case parse(expr(), X) of
    [{N, []}] -> N;
    [{_, out}] -> throw("unused input " ++ out);
    [] -> throw("invalid input")
  end.

expr() ->
  bind(term(), fun(T) ->
    l_or_r(
      bind(
        many(
          bind(l_or_r(symbol("+"), symbol("-")), fun(Bin) ->
          bind(term(), fun(T1) ->
            case Bin of
              "+" -> return(T1);
              "-" -> return(-T1)
            end
          end) end)
        ), fun(List) ->
        return(lists:sum([T|List]))
      end),
      return(T)
    )
  end).

term() ->
  bind(factor(), fun(F) ->
    l_or_r(
      bind(
        many(
          bind(l_or_r(symbol("*"), symbol("/")), fun(Bin) ->
          bind(factor(), fun(F1) ->
               return({Bin, F1})
          end) end)
        ), fun(List) ->
        {P, D} = lists:splitwith(fun({X, _}) -> X =:= "*" end, List),
        TMP = lists:foldl(fun({_,X},Y) -> Y*X end, F, P),
        return(lists:foldl(fun({_,X},Y) -> Y/X end, TMP, D))
      end),
    return(F)
    )
  end).

factor() ->
  bind(atom(), fun(A) ->
  l_or_r(
    bind(symbol("^"), fun(_) ->
    bind(factor(), fun(F) ->
         return(math:pow(A,F))
    end) end),
    return(A)
  )
  end).

atom() ->
  l_or_r(
    bind(symbol("("), fun(_) ->
    bind(expr(), fun(E) ->
    bind(symbol(")"), fun(_) ->
         return(E)
    end) end) end),
    integer()).

で、動かしてみると

1> expr:eval("1-2/9-3/2^3^2-4").
-3.2280815972222223

Haskellで検算

Prelude> 1-2/9-3/2^3^2-4
-3.2280815972222223

おぉ、なんか、動いてるみたい

左再帰なんて始めてググったので何か色々間違ってるかもしれないけど動いたヨ!!

Erlang で Parsec っぽいことしようとしている
freesourcecode - Erlang Parsec library とか
Erlang 付属のパーサジェネレータ Yecc を使ってみた - muddy brown thang とか
まぁ、色々あるんだと思うんですが
lists:foldl とかやっとこさ使ったんでちょっと楽しかった

教訓: do notation は便利