wiprog

C# とか,数学とか,社会とか.

LINQ で指定したキーだけ使って Distinct, Except とかする

たとえばこんなてきとうなクラスがあったとして

public class MyClass
{
    public int Id { get; set; }
    public double Value { get; set; }
}

Id だけを見て distinct とかしたい (けど結果は Value もほしいし、Id が重複した場合に Value は順番に依存 (最初に見つかったもの) で構わない) とかいう場合のはなしです。 最近ちょっと似たようなの書くことがあったのでメモ IEqualityComparer 書けばできますが、もうちょっとぱぱっと書きたくて。。。

Distinct

public static IEnumerable<TItem> Distinct<TItem, TKey>(this IEnumerable<TItem> source, Func<TItem, TKey> keySelector)
{
    IEnumerable<TItem> Enumerate()
    {
        var set = new HashSet<TKey>();
        foreach (var item in source)
            if (set.Add(keySelector(item))) yield return item;
    }
    
    if (source == null)
        throw new ArgumentNullException(nameof(source));
        
    if (keySelector == null)
        throw new ArgumentNullException(nameof(keySelector));
    
    return Enumerate();
}
var data = new [] 
{
    new MyClass { Id = 1, Value = 1.0 },
    new MyClass { Id = 2, Value = 2.0 },
    new MyClass { Id = 1, Value = 0.5 },
};

// {Id = 1, Value = 1.0}, {Id = 2, Value = 2.0}
var result = data.Distinct(x => x.Id);

Except

public static IEnumerable<TItem> Except<TItem, TKey>(this IEnumerable<TItem> first, IEnumerable<TItem> second, Func<TItem, TKey> keySelector)
{
    IEnumerable<TItem> Enumerate()
    {
        var set = new HashSet<TKey>(second.Select(keySelector));
        foreach (var item in first)
            if (set.Add(keySelector(item))) yield return item;
    }

    if (first == null)
        throw new ArgumentNullException(nameof(first));
        
    if (second == null)
        throw new ArgumentNullException(nameof(second));

    if (keySelector == null)
        throw new ArgumentNullException(nameof(keySelector));

    return Enumerate();
}
var first = new [] 
{
    new MyClass { Id = 1, Value = 1.0 },
    new MyClass { Id = 2, Value = 2.0 },
    new MyClass { Id = 3, Value = 3.0 },
};

var second = new []
{
    new MyClass { Id = 1, Value = 100.0 }   
};

// {Id = 2, Value = 2.0}, {Id = 3, Value = 3.0}
var result = first.Except(second, x => x.Id);

Union

public static IEnumerable<TItem> Union<TItem, TKey>(this IEnumerable<TItem> first, IEnumerable<TItem> second, Func<TItem, TKey> keySelector)
{
    IEnumerable<TItem> Enumerate()
    {
        var set = new HashSet<TKey>();
        foreach (var item in first)
            if (set.Add(keySelector(item))) yield return item;
            
        foreach (var item in second)
            if (set.Add(keySelector(item))) yield return item;
    }

    if (first == null)
        throw new ArgumentNullException(nameof(first));

    if (second == null)
        throw new ArgumentNullException(nameof(second));

    if (keySelector == null)
        throw new ArgumentNullException(nameof(keySelector));

    return Enumerate();
}
var first = new [] 
{
    new MyClass { Id = 1, Value = 1.0 },
    new MyClass { Id = 2, Value = 2.0 },
    new MyClass { Id = 3, Value = 3.0 },
};

var second = new []
{
    new MyClass { Id = 1, Value = 100.0 },
    new MyClass { Id = 4, Value = 400.0 },
};

// {Id = 1, Value = 1.0}, {Id = 2, Value = 2.0}, {Id = 3, Value = 3.0}, {Id = 4, Value = 400.0}
var result = first.Union(second, x => x.Id);

Intersect

public static IEnumerable<TItem> Intersect<TItem, TKey>(this IEnumerable<TItem> first, IEnumerable<TItem> second, Func<TItem, TKey> keySelector)
{
    IEnumerable<TItem> Enumerate()
    {
        var set = new HashSet<TKey>(second.Select(keySelector));
        
        foreach (var item in first)
            if (!set.Add(keySelector(item))) yield return item;
    }

    if (first == null)
        throw new ArgumentNullException(nameof(first));

    if (second == null)
        throw new ArgumentNullException(nameof(second));

    if (keySelector == null)
        throw new ArgumentNullException(nameof(keySelector));

    return Enumerate();
}
var first = new [] 
{
    new MyClass { Id = 1, Value = 1.0 },
    new MyClass { Id = 2, Value = 2.0 },
    new MyClass { Id = 3, Value = 3.0 },
};

var second = new []
{
    new MyClass { Id = 1, Value = 100.0 },
    new MyClass { Id = 4, Value = 400.0 },
};

// {Id = 1, Value = 1.0}
var result = first.Intersect(second, x => x.Id);

C# の ref まとめ

C#7.2 までの参照渡し関係のまとめです。

C# 7 系で参照渡しの扱いが強化されて種類も増えました。 上手につかうとサイズの大きい値型のコピーを避けられるのでまとめてみました。 動作をきちんと理解するために C# to C# の変換をしたコードや IL をのせています。

予備知識 - defensive copy, readonly struct

defensive copy - 防衛的なコピー

readonly 指定された値型は値が変化しないことを保証するために、コンパイラが値を防衛的にコピーしている場合がある。

defensive copy が発生するのは下記の場合に、後述する readonly struct ではないふつうの struct を使用しているとき

  • readonly フィールドとして構造体を持っている場合
  • readonly な参照渡しで構造体を返すとき

こんな構造体があった場合

public struct Point
{
    public double X;
    public double Y;
    
    // フィールドを書き換えるメソッド
    public void Set(double x, double y)
    {
        X = x;
        Y = y;
    }
}
readonly フィールドでない場合

たとえば、このようなクラスでは防御的コピーは発生しない(readonly でないので、構造体のフィールドを書き換えることに制限はない)

public static class MyClass
{
    // readonly でないフィールド
    private static Point s_origin = default;
    
    public static void Sample()
    {
        // フィールド書き換え
        s_origin.Set(1, 1);
    
        // 実際に書き換わっている
        Console.WriteLine($"X: {s_origin.X}, Y: {s_origin.Y}");
    }
}

IL を見ると、こんな感じ

MyClass.Sample:
IL_0000:  nop 
   
; s_origin の「アドレス」をスタックに push     
IL_0001:  ldsflda     MyClass.s_origin

; set メソッドの呼び出し
IL_0006:  ldc.r8      00 00 00 00 00 00 F0 3F 
IL_000F:  ldc.r8      00 00 00 00 00 00 F0 3F 
IL_0018:  call        Point.Set
IL_001D:  nop         
readonly フィールドの場合
public static class MyClass
{
    // 原点の座標を何度も使うので readonly フィールドにもつ
    private static readonly Point s_origin = default;
    
    public static void Sample()
    {
        // 構造体のフィールドは readonly を受け継ぐので書き換えできない
        // s_origin.X = 1;
        
        // フィールドを書き換えるかもしれないメソッドは呼べるように見える
        s_origin.Set(1, 1);
        
        // 実際には書き換わっていない
        Console.WriteLine($"X: {s_origin.X}, Y: {s_origin.Y}");
    }
}

s_origin.Set() メソッド読んでもフィールドが書き換わっていないが、 これは(フィールドを変更しているかもしれない)メソッド呼び出しを許容しつつ、readonly であることを保証するために、いったん s_origin をコピーしてから、そのコピーに対してメソッドを呼ぶため。

「メソッドの中でなにも書き換えていない」ことは呼び出し側から知るすべがないので、実際にコピーが必要かどうかにかかわらず常にコピーが発生する。 readonly なフィールドや readonly な参照 (in 引数) を使用するときは注意が必要。

IL をみると、ローカル変数に値をコピーしてからメソッドを読んでいる

MyClass.Sample:
IL_0000:  nop      
; 値をローカル変数にコピー   
IL_0001:  ldsfld     MyClass.s_origin
IL_0006:  stloc.0     

; ローカル変数のアドレスをスタックに push
IL_0007:  ldloca.s    00 

; ローカル変数にたいして Set() を呼ぶ
IL_0009:  ldc.r8      00 00 00 00 00 00 F0 3F 
IL_0012:  ldc.r8      00 00 00 00 00 00 F0 3F 
IL_001B:  call        Point.Set
IL_0020:  nop         

readonly struct

防衛的なコピーは、下記のようにすべてのフィールドを readonly にしていても発生する。

struct NoReadOnlyPoint
{
    // X, Y は readonly
    public readonly double X;
    public readonly double Y;

    // フィールドや this の書き換えを行うメソッドは持たないが、
    // 呼び出し側からはフィールドの書き換えを行っていないことを知るすべがないため、
    // readonly な NoReadOnlyPoint のインスタンスに対して Hoge() を呼ぶと、常に defensive copy が発生する
    public void Hoge()
    {
        // ...
    }
}

下記のように readonly struct とすることによって、フィールドの書き換えが起こらないことを保証でき、 defensive copy を避けられる

readonly struct ReadOnlyPoint
{
    // readonly なフィールドのみ許容される
    // get-only プロパティも、結局 readonly フィールドを生成するので許容
    public readonly double X;
    public readonly double Y;

    // フィールドや this の書き換えを行うメソッドは持てないので、
    // 呼び出し側で defensive copy の必要がない
    public void Hoge()
    {
        // ...
    }
}

呼び出し例

public static class MyClass
{
    // 原点の座標を何度も使うので readonly フィールドにもつ
    private static readonly NoReadOnlyPoint s_noReadonlyOrigin = default;
    private static readonly ReadOnlyPoint s_readonlyOrigin = default;

    public static void Sample()
    {
        // 防衛的なコピーが発生
        s_noReadonlyOrigin.Hoge();
        
        // 防衛的なコピーが発生しない
        s_readonlyOrigin.Hoge();
    }
}

IL

MyClass.Sample:
IL_0000:  nop         

// readonly struct でない場合はコピーが発生
IL_0001:  ldsfld      MyClass.s_noReadonlyOrigin
IL_0006:  stloc.0     
IL_0007:  ldloca.s    00 
IL_0009:  call        NoReadOnlyPoint.Hoge
IL_000E:  nop         

// readonly struct の場合はコピーが発生しない
IL_000F:  ldsflda     MyClass.s_readonlyOrigin
IL_0014:  call        ReadOnlyPoint.Hoge
IL_0019:  nop         
IL_001A:  ret    

生成される C# コード

readonly struct にした構造体には、コンパイラが [IsReadOnly] 属性をつける

[IsReadOnly]
private struct ReadOnlyPoint
{
    public readonly double X;
    public readonly double Y;
    public void Hoge()
    {
    }
}

この属性によって readonly struct かどうかの判定をおこなうようだ

参照渡しの種類一覧

種類 使う場所 書き換え C#のバージョン
ref parameters 引数 o 1.0?
out parameters 引数 o 1.0?
in parameters 引数 x 7.2
ref returns 戻り値 o 7.0
ref returns (readonly) 戻り値 x 7.2
ref locals ローカル変数 o 7.0
ref locals (readonly) ローカル変数 x 7.2

参照引数

ref parameters

読み書き両方できる参照渡しの引数。 渡す前にかならず初期化が必要

x と y を交換するメソッドの例:

void Main()
{
    // 必ず初期化しておく
    int x = 1;
    int y = 2;

    Swap(ref x, ref y); // x: 2, y: 1
}

public static void Swap<T>(ref T x, ref T y)
{
    T tmp = x;
    x = y;
    y = tmp;
}

out parameters

出力用の参照引数。 渡す前に初期化が不要、 C# 7 では out-var で変数の宣言と同時に受け取れる

void Main()
{
    var list = new List<int>() { 1, 2, 3, 4 };
    
    // 出力引数のうけとり
    // C#7 からは 受けとりと同時に変数の宣言が可能
    if (TryGetAt(list, 1, out var elem))
    {
        Console.WriteLine(elem);
    }
    else
    {
        Console.WriteLine("not found");
    }
}

// IList<T> の指定したインデックスの値を返す
private static bool TryGetAt<T>(IList<T> list, int index, out T elem)
{
    if (list.Count > index)
    {
        // out 引数に結果を入れる
        elem = list[index];
        return true;
    }
    else
    {
        // out 引数は必ず初期化しなければならない
        elem = default;
        return false;
    }
}

in parameters

読み取り専用の参照渡し引数。 値渡しで発生する構造体のコピーを避けつつ、 ref で参照渡ししたときの書き換えのリスクもなくす。 ただし、予備知識に書いたとおり、 readonly struct でない値型を受け取ったときに、プロパティやメソッドの呼び出しを行うと無条件にコピーが発生するので注意。

例:

using System;

public class Program
{
    static void F(in int x)
    {
        // 読み取り可能
        Console.WriteLine(x);

        // 書き換えようとするとコンパイル エラー
        x = 2;
    }

    // 補足: in 引数はオプションにもできる
    static void G(in int x = 1)
    {
    }

    static void Main()
    {
        int x = 1;

        // ref 引数と違って修飾不要
        F(x);

        // 明示的に in と付けてもいい
        F(in x);

        // リテラルに対しても呼べる
        F(10);

        // 右辺値(式の計算結果)に対しても呼べる
        int y = 2;
        F(x + y);

        // in のオプション引数を省略した呼び出し
        G();
    }
}

コンパイル後は結局は ref に変換される

using System;
using System.Runtime.CompilerServices;
public class Program
{
    // [IsReadOnly] がついた ref になる
    private static void F([IsReadOnly] ref int x)
    {
        // 読み取り可能
        Console.WriteLine(x);
    }

    private static void G([IsReadOnly] ref int x = 1)
    {
    }

    private static void Main()
    {
        // in で修飾してもしなくても結局ただの ref になる
        int num = 1;
        Program.F(ref num);
        Program.F(ref num);

        // リテラルに対しての呼び出しは ローカル変数が作られて、その参照が渡される
        int num2 = 10;
        Program.F(ref num2);

        // 式の計算結果に対して呼ぶ場合は先に式の計算結果をローカル変数に入れておいて、その参照が渡される
        int num3 = 2;
        num2 = num + num3;
        Program.F(ref num2);

        // オプション引数を省略した場合は、デフォルト値の参照が渡される
        num2 = 1;
        Program.G(ref num2);
    }
}

(サンプルコードはこちらから引用させていただきました)

参照戻り値、参照ローカル変数

C# 7 から、戻り値とローカル変数にも参照渡しが使えるようになった。 C# 7.2 からは readonly な参照を返すこともできる

readonly でない ref returns では、readonly なフィールドを返すことはできない(書き換えられるため) readonly な ref returns では、 readonly なフィールドを返せる。

using System;
public class Program
{
    public void Sample()
    {
        var user = new User("hanako");
        
        // 書き換えできる参照
        ref var mutableId = ref user.MutableId;
        mutableId = Guid.NewGuid();
        
        // 書き換えできない参照
        ref readonly var immutableId = ref user.ImmutableId;
        // immutableId = Guid.NewGuid(); // 代入できない
        
        // これは値渡し
        var idValue = user.Id;
        var idValue2 = user.MutableId;
        var idValue3 = user.ImmutableId;
    }
}

public class User
{
    private Guid _id;
    public string Name { get; }
    
    // これは値渡し
    public Guid Id => _id;
    
    // 書き換えできる参照を返す
    public ref Guid MutableId => ref _id;
    
    // readonly な参照を返す
    public ref readonly Guid ImmutableId => ref _id;
    
    public User(string name)
    {
        _id = Guid.NewGuid();
        Name = name;
    }
}

コンパイルすると、 readonly でも readonly でなくてもどちらも同じコードになる (IsReadOnlyAttribute がつく)。 ポインタをつかった unsafe コードが生成される。

using System;
using System.Diagnostics;
using System.Reflection;
using System.Runtime.CompilerServices;
using System.Security;
using System.Security.Permissions;

[assembly: AssemblyVersion("0.0.0.0")]
[assembly: Debuggable(DebuggableAttribute.DebuggingModes.Default | DebuggableAttribute.DebuggingModes.DisableOptimizations | DebuggableAttribute.DebuggingModes.IgnoreSymbolStoreSequencePoints | DebuggableAttribute.DebuggingModes.EnableEditAndContinue)]
[assembly: CompilationRelaxations(8)]
[assembly: RuntimeCompatibility(WrapNonExceptionThrows = true)]
[assembly: SecurityPermission(SecurityAction.RequestMinimum, SkipVerification = true)]
[module: UnverifiableCode]
public class Program
{
    public unsafe void Sample()
    {
        User user = new User("hanako");
        Guid* mutableId = user.MutableId;
        *mutableId = Guid.NewGuid();
        Guid* immutableId = user.ImmutableId;
        Guid id = user.Id;
        Guid guid = *user.MutableId;
        Guid guid2 = *user.ImmutableId;
    }
}
public class User
{
    private Guid _id;

    [DebuggerBrowsable(DebuggerBrowsableState.Never), CompilerGenerated]
    private readonly string <Name>k__BackingField;

    public string Name
    {
        [CompilerGenerated]
        get
        {
            return this.<Name>k__BackingField;
        }
    }

    public Guid Id
    {
        get
        {
            return this._id;
        }
    }

    public unsafe Guid* MutableId
    {
        get
        {
            return ref this._id;
        }
    }

    [IsReadOnly]
    public unsafe Guid* ImmutableId
    {
        [return: IsReadOnly]
        get
        {
            return ref this._id;
        }
    }

    public User(string name)
    {
        this._id = Guid.NewGuid();
        this.<Name>k__BackingField = name;
    }
}

参考

関連: Span<T>

C# でオレオレパーサコンビネータをつくってみる

この記事について

この記事は C# Advent Calendar 2017 の 10 日目の記事です。 アホなので 9 日の夜に書きはじめています。ちゃんと間に合ったらいいねください・・・!!!!

コードは github にあります wipiano/csharp-parser-combinators

Haskell や Scala で便利便利と言われているパーサコンビネータを自分でつくって遊んでみようという記事です。 実用的なパーサコンビネータの完成までは至らなくても、雰囲気だけつかめればと。

関数をどんどん組み合わせていくので delegate と拡張メソッドを使って遊ぶ感じになります。 この記事を読むにあたって、パーサコンビネータや Haskell や Scala や関数型プログラミングの知識は必要ありませんが、高階関数が出てくるので馴染みのない方は wikipedia でもさらっと読んでおくとわかりやすいかと思います。

Java 版のこの記事を参考に、 C# だったらどう書くかなあ、自分だったらどう書くかなあというところを考えて書きました。 なので Haskell とも Scala とも下記の先行記事とも同じ実装にはなっていません。

.NET の パーサコンビネータの実装はすでにあるようですが、これを再現しようという話ではありません

私自身関数型にはあまり強くないので詳しい方にコメントいただけると、読んでくれる方も助かるのではないかと思います!

続編は json のパースあたりをいつか書くかもって感じです。

完成イメージ

例えば xxx-xxxx の形式の郵便番号を受け付けるパーサはこんなふうに書けます。 この記事の最後にもうすこしだけ難しい例がのっていますが、 json のパーサなんかもかけるとおもいます。

// xxx-yyyy の xxx 部分
Parser<int> leftPart = Digit.Repeat(3).Map(chars => int.Parse(new string(chars.ToArray())));

// xxx-yyyy の yyyy 部分
Parser<int> rightPart = Digit.Repeat(4).Map(chars => int.Parse(new string(chars.ToArray())));

// xxx-yyyy の形式の郵便番号のパーサ
Parser<PostalCode> postalCodeParser = leftPart
    .Left(Literal('-'))
    .Sequence(rightPart, (left, right) => new PostalCode(left, right));

ParseResult<PostalCode> result = postalCodeParser(Source.Create("123-4567"));
PostalCode postalCode = result.Result;
public class PostalCode
{
    public int LeftPart { get; }
    
    public int RightPart { get; }

    public PostalCode(int left, int right)
    {
        this.LeftPart = left;
        this.RightPart = right;
    }

    public override string ToString() => $"{LeftPart}-{RightPart}";
}

パーサを定義する

パーサコンビネータは小さいパーサを組み合わせて大きいパーサをつくるための関数です。 まずはパーサ周りの用意をしていきます

  • Parser への入力を表す Source
  • Parser の実行結果を表す ParseResult
  • Source を受け取って ParseResult を返す Parser

Source

パーサは文字列を受け取って結果を返せばいいのですが、パーサを組み合わせていくときに生の string を直接渡すと、読んでいる位置の管理などをパーサが行う必要があるので、あとから不便になります。 そこで、うすくラップした Source 構造体を作ります。

元記事では Parser 自体が Source に対して位置を読み進めるという副作用をもっていましたが、 C# では構造体を書けるのでイミュータブルにします。

Read() メソッドを使って先頭の一文字と、位置が進められたあたらしい Source を取得できます。 文字列の長さをこえて読もうとした場合は EndOfSourceException が発生します。

ちょっとだけ長いですが、、

/// <summary>
/// Parser への入力
/// </summary>
public struct Source
{
    // 最初に与えられた文字列をもっておく
    private readonly string _source;
    
    // 現在位置
    private readonly int _pos;

    private Source(string source, int pos)
    {
        _source = source;
        _pos = pos;
    }

    /// <summary>文字列の先頭をさす Source を作成します</summary>
    public static Source Create(string source)
        => new Source(source, 0);

    /// <summary>一文字読み出します</summary>
    public (char c, Source source) Read()
    {
        if (_source.Length <= _pos)
        {
            // source の終わりを超えて読もうとした場合は Exception
            throw new EndOfSourceException(this);
        }

        return (_source[_pos], new Source(_source, _pos + 1));
    }

    /// <summary>指定した文字数ぶん char を読み出します</summary>
    public (IEnumerable<char> chars, Source source) ReadChars(int count)
    {
        if (_source.Length < _pos + count)
        {
            // 読み出そうとしている長さが source をこえていたら Exception
            throw new EndOfSourceException(this);
        }

        return (_source.Skip(_pos).Take(count), new Source(_source, _pos + count));
    }

    /// <summary>指定した長さの文字列を読み出します</summary>
    public (string s, Source source) ReadString(int length)
    {
        if (_source.Length < _pos + length)
        {
            // 読み出そうとしている長さが source をこえていたら Exception
            throw new EndOfSourceException(this);
        }

        return (_source.Substring(_pos, length), new Source(_source, _pos + length));
    }

    /// <summary>Source の終わりに達したときの Exception</summary>
    public class EndOfSourceException : Exception
    {
        private static readonly string EndOfSource = "EndOfSource";
        
        /// <summary>例外発生時の Source</summary>
        public Source Source { get; }

        internal EndOfSourceException(Source source)
            : base(EndOfSource)
        {
            this.Source = source;
        }
    }
}

ParseResult

ParseResult<T> はパーサの実行結果です。 パーサはすべてこれを返します。 結果は任意の型で持っておくことができます。 構造体が親をもてないのでこんな形にしてしまいましたが、 class にして型スイッチでも良かったかもしれないですね。。

public struct ParseResult<T>
{
    /// <summary>実行後の Source</summary>
    public Source Source { get; }
    
    /// <summary>成功したかどうか</summary>
    public bool IsSuccess { get; }

    /// <summary>パース結果</summary>
    public T Result =>
        this.IsSuccess ? _result : throw new Exception($"Parse error: {Reason}");

    private readonly T _result;
    
    // 失敗した理由
    public string Reason { get; }
    
    internal ParseResult(Source source, bool isSuccess, T result, string reason)
    {
        this.Source = source;
        this.IsSuccess = isSuccess;
        _result = result;
        this.Reason = reason;
    }
}

あとで using static で使いやすいように別クラスにヘルパー関数を定義しておきます

public static class ParseResultHelper
{
    public static ParseResult<T> Success<T>(Source source, T result)
        => new ParseResult<T>(source, true, result, default);
    
    public static ParseResult<T> Failed<T>(Source source, string reason)
        => new ParseResult<T>(source, false, default, reason);
}

Parser

パーサ本体の定義はとてもかんたんです。 Source を受け取って ParseResult を返します。 前に実行されたパーサの結果を気にするのはパーサコンビネータの役割なので、パーサ自体は Source だけに集中します。

public delegate ParseResult<T> Parser<T>(Source source);

一文字だけ読むパーサを実装する

まず簡単な一文字だけ読むパーサをいくつか実装してみます。

  • どんな文字でも受理するパーサ Any
  • 数値 (0 〜 9) だけ受理するパーサ Digit
  • 指定された文字だけ受理するパーサ (を返す高階関数) Literal(char c)
  • 指定された関数が true を返す文字を受理するパーサ (を返す高階関数) Is(Func<char, bool>)

ここで、パーサが Success や Failed の ParseResult<T> を作りやすくする関数を import しておきます

using static ParseResultHelper;

public static class CharParsers
{
   // TODO
}

Any - どんな文字でも受け付ける

どんな文字がきてもいいからとりあえず読み進めたい、というときのためのパーサです。 常に Success を返せば良いです。

public static Parser<char> Any { get; } = (Source s) =>
{
    var (c, next) = s.Read();
    return Success(next, c);
};

例:

var result = Any(Source.Create("a"));    // { IsSuccess: true, Result: 'a' }

Digit - 数字を読む

数値であれば Success を返します。

public static Parser<char> Digit { get; } = (Source s) =>
{
    var (c, next) = s.Read();
    return char.IsDigit(c) ? Success(next, c) : Failed<char>(next, "Is not a digit.");
};

例:

var success = Digit(Source.Create("12a"));    // { IsSuccess: true, Result: '1' }
var failed            // xxx-yyyy の xxx 部分
            Parser<int> leftPart = Digit.Repeat(3).Map(chars => int.Parse(new string(chars.ToArray())));

            // xxx-yyyy の yyyy 部分
            Parser<int> rightPart = Digit.Repeat(4).Map(chars => int.Parse(new string(chars.ToArray())));
            
            // xxx-yyyy の形式の郵便番号のパーサ
            Parser<PostalCode> postalCodeParser = leftPart
                .Left(Literal('-'))
                .Sequence(rightPart, (left, right) => new PostalCode(left, right));

            ParseResult<PostalCode> result = postalCodeParser(Source.Create("123-4567"));
            PostalCode postalCode = result.Result;
 = Digit(Source.Create("a12"));     // { IsSuccess: false, Result: Exception }

Literal - ある文字に一致していたら OK

これは文字を指定してその都度パーサを作る必要があるので、 Parser<char> を返す高階関数を書きます。 与えられた文字と、 Source から取得した文字が一致していれば成功です。

public static Parser<char> Literal(char literal) => (Source s) =>
{
    var (c, next) = s.Read();
    return c == literal ? Success(next, c) : Failed<char>(next, $"{c} is not equals {literal}");
};

例:

var parser = Literal('a'); // 'a' を受け付けるパーサ
var success = parser(Source.Create("abc"));    // { IsSuccess: true, Result: 'a' }
var failed = parser(Source.Create("ccc"));     // { IsSuccess: false, Result: Exception }

Is - 判定関数を指定する

これも Literal と同じように高階関数を書きます。 与えられた関数が true を返すかどうかで成功か失敗かがきまります。

public static Parser<char> Is(Func<char, bool> predicate) => (Source s) =>
{
    var (c, next) = s.Read();
    return predicate(c) ? Success(next, c) : Failed<char>(next, $"predicate({c}) returns false.");
};

例:

var lowerParser = Is(char.IsLower);    // 小文字だけ受け付けるパーサ
var success = lowerParser(Source.Create("abc"));    // { IsSuccess: true, Result: 'a' }
var failed = lowerParser(Source.Create("ABC"));     // { IsSuccess: false, Result: Exception }

これまでにつくったパーサはすべて Is() で置き換えられます。

とりあえず、パーサコンビネータをかんたんに使ってみるにはこのぐらいでよさそうなので先に進みましょう。

パーサコンビネータ

いよいよパーサコンビネータをつくっていきます。 パーサを組み合わせるための道具がパーサコンビネータですが、 実装寄りの言い方をすると、パーサコンビネータは パーサを引数にとって新しいパーサを返す関数 です。

今回は 5 種類の基本的なパーサコンビネータをつくってみます。

  • Many: 0 回以上の繰り返し
  • Repeat: 指定回数の繰り返し
  • Sequence: 2 つのパーサを順番に結合する
  • Or: 2 つのパーサのどちらか成功した方の結果をとる
  • Left, Right: 成功する条件は Sequence と同じだが、結果は左辺または右辺のものだけをとりだす

ふつうに書くと () がたくさんになって Lisp((((())))) みたいになる上にちょっと書きごこちよくないので Parser<T> の拡張メソッドとしてつくります。(Lisp は好きですよ)

ImmutableList<T>

今回、コンビネータの戻り値として Parser<ImmutableList<T>> を使います。 List<T> と違ってイミュータブルなリストであり、 Add メソッドなどのメソッドはすべて副作用のない関数になっていて、そのコレクション自体を変更するのではなく、変更された新しいコレクションを返します。 このために、データの構造も配列ではなく連結リストのような構造になっています。

この性質から、コンビネータが返すパーサを副作用のないパーサにすることができ、見通しがよくなっています。

標準では使えないので、 System.Collections.Immutable パッケージを nuget でインストールしてください。

Many - 0 回以上の繰り返し

まずは引数を 1 個しかとらないコンビネータが簡単なので Many からやっていきましょう。 失敗するまで読み続けて、最後に成功した結果のリストを返します。 「0回以上」なので 1 度も成功しなくても OK です。

public static Parser<ImmutableList<T>> Many<T>(this Parser<T> parser)
{
    ParseResult<ImmutableList<T>> Impl(Source s, ImmutableList<T> results)
    {
        var result = parser(s);

        return result.IsSuccess
            ? Impl(result.Source, results.Add(result.Result))
            : Success(s, results);
    }

    return (Source s) => Impl(s, ImmutableList<T>.Empty);
}

実際に parser を実行しているのは Impl 内です。 Impl は失敗するまで再帰的に呼ばれ続けます。

数字の 0 回以上の繰り返しはこのように書けます:

Parser<ImmutableList<char>> manyDigits = Digit.Many();

Repeat - 指定回数の繰り返し

Many の回数指定版です。今度は指定された回数分きっちり成功しつづけなければなりません。

public static Parser<ImmutableList<T>> Repeat<T>(this Parser<T> parser, int count)
{
    ParseResult<ImmutableList<T>> Impl(Source s, int c, ImmutableList<T> results)
    {
        if (c == 0)
        {
            // 0 回を指定されたら終わり
            return Success(s, results);
        }

        var result = parser(s);

        return result.IsSuccess
            ? Impl(result.Source, c - 1, results.Add(result.Result))
            : Failed<ImmutableList<T>>(result.Source, result.Reason);
    }

    return (Source s) => Impl(s, count, ImmutableList<T>.Empty);
}

3 桁の数字はこのように書けます:

Parser<ImmutableList<char>> parser = Digit.Repeat(3);

Sequence - 連結

ここから 2 つのパーサを引数にとるコンビネータの実装に入ります。

ParseResult を string に限定せずジェネリック型にしてしまったことでここから一気に実装がめんどくさくなってしまいました・・・。

渡されるパーサの型がちがう場合を考慮して、3 つのオーバーロードを用意する必要があります。

  • Parser<ImmutableList<T>> Sequence<T>(Parser<T> first, Parser<T> second): 型がおなじパーサを連結する
  • Parser<ImmutableList<T>> Sequence<T>(Parser<ImmutableList<T>> first, Parser<T> second): 型が同じパーサを 2 回以上つづけて連結したい場合のサポート
  • Parser<TResult> Sequence<TFirst, TSecond, TResult>(Parser<TFirst> first, Parser<TSecond> second, Func<TFirst, TSecond, TResult> resultSelector): 型が一致しないパーサを連結する
public static Parser<ImmutableList<T>> Sequence<T>(this Parser<T> first, Parser<T> second) =>
    first.Sequence(second, (f, s) => ImmutableList<T>.Empty.Add(f).Add(s));

public static Parser<ImmutableList<T>> Sequence<T>(this Parser<ImmutableList<T>> first, Parser<T> second) =>
    first.Sequence(second, (f, s) => f.Add(s));

public static Parser<TResult> Sequence<TFirst, TSecond, TResult>(this Parser<TFirst> first, Parser<TSecond> second, Func<TFirst, TSecond, TResult> resultSelector) =>
    (Source s) =>
    {
        var firstResult = first(s);
        if (firstResult.IsSuccess)
        {
            var secondResult = second(firstResult.Source);

            return secondResult.IsSuccess
                ? Success(secondResult.Source, resultSelector(firstResult.Result, secondResult.Result))
                : Failed<TResult>(secondResult.Source, secondResult.Reason);
        }
        else
        {
            return Failed<TResult>(firstResult.Source, firstResult.Reason);
        }
    };

Qiita という文字列を受け付けるパーサはこんな感じになります:

var qiitaParser = Literal('Q')
    .Sequence(Literal('i').Repeat(2))
    .Sequence(Literal('t'))
    .Sequence(Literal('a'));

string qiita = string.Join("", qiitaParser(Source.Create("Qiita")).Result);

Or - 選択

Or も Sequence と同じように実装できます。 ただし Or はふたつのパーサが同じ型である必要があります。 ここで、 first が成功した場合は second は評価せずに first の結果を返すことにします。

public static Parser<T> Or<T>(this Parser<T> left, Parser<T> right) => (Source s) =>
{
    var leftResult = left(s);

    return leftResult.IsSuccess
        ? leftResult
        : right(s);
};

Left, Right

Left, Right の実装は Sequence に渡す ResultSelector が違うだけです。

Left は与えられたパーサ両方が成功したとき、右側の結果を捨てて左側の結果だけを返します。 Right はその逆で、左側の結果を捨てて右側の結果だけを返します。

public static Parser<TLeft> Left<TLeft, TRight>(this Parser<TLeft> left, Parser<TRight> right) =>
    left.Sequence(right, (l, r) => l);

public static Parser<TRight> Right<TLeft, TRight>(this Parser<TLeft> left, Parser<TRight> right) =>
    left.Sequence(right, (l, r) => r);

Map - 型変換

これはパーサどうしを組み合わせるものではないですが、便利な関数として Parser の型を変換するための関数をつくっておきます。

public static Parser<TResult> Map<TParser, TResult>(this Parser<TParser> parser, Func<TParser, TResult> mapper) =>
    (Source s) =>
    {
        var result = parser(s);
        return result.IsSuccess
            ? Success(result.Source, mapper(result.Result))
            : Failed<TResult>(result.Source, result.Reason);
    };

最後にしょぼい郵便番号のパーサをつくってみる

なんとか完成しました・・・!!!

最後に郵便番号のパーサをつくってみます。 そのままだと Sequence だけで終わってしまうので、すこしゆるいパーサをつくります。

下記のような入力はすべて受け付けることができます

  • 123-4567
  • 1234567
  • 〒1234567
  • 〒123-4567
// xxx-yyyy の xxx 部分
Parser<int> leftPart = Digit.Repeat(3).Map(chars => int.Parse(new string(chars.ToArray())));

// xxx-yyyy の yyyy 部分
Parser<int> rightPart = Digit.Repeat(4).Map(chars => int.Parse(new string(chars.ToArray())));

// 普通の xxx-yyyy
Parser<PostalCode> normal = leftPart.Left(Literal('-')).Sequence(rightPart, (l, r) => new PostalCode(l, r));

// xxxyyyy
Parser<PostalCode> withoutSeparator = leftPart.Sequence(rightPart, (l, r) => new PostalCode(l, r));

Parser<PostalCode> postalCode = normal.Or(withoutSeparator);

// 〒 が付加されてもよい
Parser<PostalCode> postalCodeParser = Literal('〒').Right(postalCode).Or(postalCode);