逆ポーランド記法電卓をF#とC#で実装してみる

「すごいHaskell 楽しく学ぼう!」の10章で取り上げられている逆ポーランド記法電卓を少しアレンジしたものを、F#とC#を使って実装してみました。

• 与えられた逆ポーランド記号で書かれた文字列を数値と演算子に分解して、listをスタックに見立てて、詰める
• スタックを畳み込み込む

現状、入力エラーなどの不測の事態は考慮していません。後に、monadを使ってエラーハンドリングできるものに修正する予定。

以下、実行のイメージ

let input = "10 4 3 + 2 * -"
let ans = solveRPN input
printfn "%A" ans
// => -4

型を定義する

「すごいHaskell 楽しく学ぼう!」では、文字列のまま処理を進めていましたが、関数型プログラミングらしく型を作ってみました。

F#

// 演算子
type Operator = 
    | Addition
    | Subtraction
    | Multiplication
    | Division

// スタックに積むアイテム
type Item = 
    | Number of double
    | Operator of Operator

C#

C#には判別共用体がないので、record型を使って定義する

// 演算子
public abstract record Operator();

public record Addition() : Operator;
public record Subtraction() : Operator;
public record Multiplication() : Operator;
public record Division() : Operator;

// スタックに積むアイテム
public abstract record Item();

public record Number(double value) : Item;
public record Ope(Operator ope) : Item;

関数を実装する

F#

type SolveRPN = string -> double

let solveRPN: SolveRPN = 
    fun expression ->
        // 文字列をItemへ変換してスタックへ詰める
        let createStack = 
            fun (exp: string) ->
                let splited =  Array.toList(exp.Split(' '))
                let parse str = 
                    match str with
                    | "+" -> Addition |> Operator
                    | "-" -> Subtraction |> Operator
                    | "*" -> Multiplication |> Operator
                    | "/" -> Division |> Operator
                    | n -> double n |> Number
                List.map parse splited

        // スタックを畳み込む関数
        let foldingFunction stack item = 
            match stack, item with
            | ((Number x)::(Number y)::ys), Operator o -> 
                match o with
                    | Addition -> (Number (y + x)) :: ys
                    | Subtraction -> (Number (y - x)) :: ys
                    | Multiplication -> (Number (y * x)) :: ys
                    | Division -> (Number (y / x)) :: ys
            | xs, n -> n :: xs
        expression 
        |> createStack 
        |> List.fold foldingFunction [] 
        |> List.head 
        |> function 
            | Number x -> x
            | _ -> 500.0

C#

var solveRPN = (string exp) =>
    {
        // 文字列をItemへ変換してスタックへ詰める
        var createStack = (string exp) =>
        {
            var splited = exp.Split(' ').ToList();
            static Item parse(string str)
            {
                return str switch
                {
                    "+" => new Ope(new Addition()),
                    "-" => new Ope(new Subtraction()),
                    "*" => new Ope(new Multiplication()),
                    "/" => new Ope(new Division()),
                    _ => new Number(double.Parse(str))
                };
            }
            return splited.Select(x => parse(x)).ToList();
        };

        // スタックを畳み込む関数
        var foldingFunction = (ImmutableArray<Item> stack, Item item)
            => (new { A = stack, B = item }) switch
                {
                    { A: [var x, var y, .. var xs], B: Ope o } =>
                        new { X = x, Y = y, O = o.ope } switch
                        {
                            { X: Number n2, Y: Number n1, O: Addition } => xs.Insert(0, new Number(n1.value + n2.value)),
                            { X: Number n2, Y: Number n1, O: Subtraction } => xs.Insert(0, new Number(n1.value - n2.value)),
                            { X: Number n2, Y: Number n1, O: Multiplication } => xs.Insert(0, new Number(n1.value * n2.value)),
                            { X: Number n2, Y: Number n1, O: Division } => xs.Insert(0, new Number(n1.value / n2.value)),
                            { X: _, Y: _, O: _ } => xs.Insert(0, item)
                        },
                    { A: [.. var xs], B: _ } => xs.Insert(0, item)
                };
        var ans = createStack(exp).Aggregate([], foldingFunction).First();
        return ans switch { Number n => n.value, _ => 500 };
    };

まとめ

関数型プログラミングに寄せた書き方をしているので、当たり前といえば当たり前なのですが、全く同じことをするとF#の方が圧倒的にすっきりしたコードになっています。C＃の方は、ヘルパー関数をいくつか用意すれば、もう少しはすっきりさせることはできますが、いずれにせよひと手間かかるということになります。

また、C#の方はパターンマッチの使い方が今一つ分からず、かなりぎこちない実装になってしまいました。※この辺もっとこうした方が良いなどのご意見がありましたら、教えていただけると助かります。