関数型言語ってこわい？C#erがLINQでパーサーに挑戦(2)

註：この記事は、「ごはんはおかずLINQはモナド」と聞いたことがあるけど、モナドって何なのかは特に知りたくない、でもLINQがモナドだと何ができるのかはちょっとだけ知りたい、という奇特な人向けに、「簡単なパーサーを実装する」というお題でコードを見てみようという、まったくPVの伸びなさそうな記事です。

前記事（関数型言語ってこわい？C#erがLINQでパーサーに挑戦(1) - 猫とC#について書くmatarilloの雑記）ではF#のリスト FList<T> を用意しておいた。

ではパーサーの型を定義してみよう。パーサーは文字列を受け取って、文字列の先頭からいくつかの文字を消費し、パース結果、および、消費しなかった残りの文字列を返すものとする。

  public class Parser<T>
  {
    public Tuple<T, string> Parse(string input)
    {
      // TODO: あとで実装
    }
  }

パースには失敗することもあるが、その場合はnullを返すものとしておく。
上のメソッドではstringを使っているが、これをcharのリスト（F#のリスト）に変えておく。

  using FString = FList<char>;

  public class Parser<T>
  {
    public Tuple<T, string> Parse(string input)
    {
      var r = this.Parse(input.ToFList());
      return Tuple.Create(r.Item1, new string(r.Item2.ToArray()));
    }

    public Tuple<T, FString> Parse(FString input)
    {
      // TODO: あとで実装
    }
  }

パーサーの本体は（合成しやすいように）関数で実現する。

  using FString = FList<char>;

  public class Parser<T>
  {
    private readonly Func<FString, Tuple<T, FString>> f;

    public Parser(Func<FString, Tuple<T, FString>> f)
    {
      this.f = f;
    }

    public Tuple<T, string> Parse(string input)
    {
      var r = this.Parse(input.ToFList());
      return Tuple.Create(r.Item1, new string(r.Item2.ToArray()));
    }

    public Tuple<T, FString> Parse(FString input)
    {
      return this.f(input);
    }
  }

さて、ここからが本題。パーサーはLINQを使って構築したい。そこで、標準クエリ演算子の一部を実装する。
今回は、Select, SelectMany, そしてWhereを実装しよう。なお、SelectManyは、クエリ構文を使える版のオーバーロードを実装する*1。
Selectはパース結果の型を変更する。パースに失敗する場合はnullを返す。

    public Parser<TResult> Select<TResult>(Func<T, TResult> f)
    {
      return new Parser<TResult>(input =>
      {
        var r = this.Parse(input);
        if (r == null) return null;
        return Tuple.Create(f(r.Item1), r.Item2);
      });
    }

SelectManyは2つのパーサーを合成（＝連続適用）した上で、パース結果の型を変更する。どちらかのパーサーがパースに失敗する場合はnullを返す。

    public Parser<TResult> SelectMany<T1, TResult>(Func<T, Parser<T1>> k, Func<T, T1, TResult> f)
    {
      return new Parser<TResult>(input =>
      {
        var r1 = this.Parse(input);
        if (r1 == null) return null;
        var r2 = k(r1.Item1).Parse(r1.Item2);
        if (r2 == null) return null;
        return Tuple.Create(f(r1.Item1, r2.Item1), r2.Item2);
      });
    }

Whereはパース結果に対してフィルタリングを行う。パース結果が条件に合わなかった場合はnullを、条件に合う場合は元のパース結果を返す。

    public Parser<T> Where(Func<T, bool> predicate)
    {
      return new Parser<T>(input =>
      {
        var r = this.Parse(input);
        if (r == null) return null;
        if (!predicate(r.Item1)) return null;
        return r;
      });
    }

標準クエリ演算子としては以上でいいが、それ以外にも作っておいたほうがいいものがある。それは "OR" 。つまり、1個目のパーサーがパースに失敗する場合は2個目のパーサーにパースさせるというもの。
Parser<T>クラスのメソッドとして実装してもいいが、使う時にかっこが必要になってしまうのが嫌なので、今回は演算子|をオーバーロードする。

    public static Parser<T> operator |(Parser<T> x, Parser<T> y)
    {
      return new Parser<T>(input =>
      {
        var r = x.Parse(input);
        return (r == null) ? y.Parse(input) : r;
      });
    }

*1:モナドのことを知っている人は、セレクタを1つ受け取るSelectManyさえあれば良いと思うかもしれない。ところが、これだとクエリ構文が使えない。クエリ構文を使うためには、セレクタを2つ受け取るSelectManyと、Selectが必要になる。Whereは必須ではないが、あると便利。