C# でランク N 多相

C#

追記：これだと解決できていない。

C# に Sprache というパーサーコンビネーターがあるのだが、最近そいつを継続渡しスタイル（continuation passing style; CPS）にしてやろうと、Haskell のパーサーコンビネーター attoparsec を参考にいじっていた。

そこでこういう型があった。

newtype Parser i a = Parser {
      runParser :: forall r.
                   State i -> Pos -> More
                -> Failure i (State i)   r
                -> Success i (State i) a r
                -> IResult i r
    }

この型単品では C# への翻訳で困らないのだが、次のような関数があると困ったことになる。

plus :: Parser i a -> Parser i a -> Parser i a

そこで StackOverflow で質問してなるほどなーと思ったのでまとめてみる。

newtype は実質型の別名なので（明示的な相互変換が要るが）、plus 型は次のように理解できるわけだ。

plus :: (forall r.
            State i -> Pos -> More
         -> Failure i (State i)   r
         -> Success i (State i) a r
         -> IResult i r)
     -> (forall r.
            State i -> Pos -> More
         -> Failure i (State i)   r
         -> Success i (State i) a r
         -> IResult i r)
     -> (forall r.
            State i -> Pos -> More
         -> Failure i (State i)   r
         -> Success i (State i) a r
         -> IResult i r)

ややこしいので今回の話題に本質的でない部分を省くと、次のようになる。（意味のあるものではなくなっているが。）

f :: (forall r. r -> r)
  -> ()

この型は C# でいうところの void F<R>(Func<R, R> f) なのではないかと思うかもしれないが次のような場合に問題がある。

static void Main(string[] args)
{
    F(Id);
}

T Id<T>(T t) { return t; }

void F<T>(Func<T, T> f) { // This is not sound!
    System.Console.WriteLine("{0}", f(1));
    System.Console.WriteLine("{0}", f("one"));
}

F<T>(Func<T, T>) を使うところで推論できないとエラーが出、じゃあと T の型を指定しようとすると int にしても string にしても問題があるわけだ。

f の型は F を適用するところでは一意に決めず多相のままにしておきたいわけだ。こういうのをランク 2 多相という。（上述の F はランク 1 多相。）

で、C# はそんな多相をサポートしてないしなんとか回避策がないものかと考えてパッっと出てこなかったんで StackOverflow に聞いてみたら次のような回答が得られた。

using System;

interface IGenericSameTypeFunction
{
    T Apply<T>(T input);
}

public class SimpleIdentityFunction : IGenericSameTypeFunction
{
    public T Apply<T>(T input) => input;
}

class Test
{    
    static void F(IGenericSameTypeFunction function)
    {
        Console.WriteLine(function.Apply(1));
        Console.WriteLine(function.Apply("one"));
    }

    static void Main()
    {
        F(new SimpleIdentityFunction());
    }
}

なるほどなぁ。部分型多相を使うことでランク N 多相を実現するのだな。