さんぽみち

なにか思いついたときとかに気まぐれに更新されます。

C# 続・メソッドチェーンしたくて仕方なかった

C# アルゴリズム

はじめに

　前回の続きです。
　　前回 C# メソッドチェーンしたくて仕方なかった - さんぽみち
　これを拡張したり根本的に変えたりしたら面白いものができたので記事にしてみます。

前回のあらすじ

　メソッドチェーン楽しい
　　↓
　途切れさせるやつ大っ嫌い
　　↓
　チェーンにデリゲート渡して向こう側で処理すればずっとチェーンしてられるんじゃね？
　　↓
　できた！

今回の特徴

　前回の状態では、まだ使い勝手の悪い？場所があります。
　一つ目は、例外を扱うクラスを綺麗に扱うことが難しいです。
　例外を吐いた時のために、チェーンの外側でトラップしてやらなければなりません。
　この例外について、復旧したり握りつぶしたりするのもチェーンの中でやっちゃいます。
　二つ目は、条件分岐を記述する場合、ラムダ式が泥臭くなることです。
　メソッドチェーンで埋め込む式は、できれば1文、多くても2文くらいにしたいです。
　中で分岐などをし始めると汚くなります。
　これを満たそうとすると、2分岐を三項演算子で表現するのが精いっぱいです。
　そこで、分岐に関する処理をもっと戦略的かつ視覚的にもわかりやすくしようと思います。
　なお、このように書きましたがすべてをチェーンで書くということ自体が変な考えであり、
チェーンを一度止めて判断したり例外は外でわかりやすくトラップするのが美しいコードだとは認識しております。
　ですのでこの方向性自体には突っ込まないでください。

実装

　少し長いですが一気に貼っちゃいます。

using System;
using System.Linq;
using System.Collections.Generic;

namespace MaybeChain
{
  public delegate T ConstFunc<T>();
  public delegate void VoidFunc();
  
  
  ///<summary>Maybe型を扱いやすくする為のメソッド群</summary>
  public static class Maybe
  {
    ///<summary>チェーンを始める為にMaybeで包む</summary>
    ///<param name="a">チェーンの先頭となる値</param>
    ///<returns>Maybeで包まれた値</returns>
    ///<remark>Wrap :: T -> Maybe T</remark>
    public static Maybe<T> Wrap<T>(this T a){ return Maybe.Return(a); }
    
    ///<summary>値をMaybeの世界に入れる</summary>
    ///<param name="a">対象となる値</param>
    ///<returns>Maybeとして扱うことのできる値</returns>
    ///<remark>Return :: T -> Maybe T</remark>
    public static Maybe<T> Return<T>(T a){ return Maybe<T>.Return(a); }
    
    ///<summary>一時的な値をスコープ限定で使いまわす</summary>
    ///<param name="a">使いまわしたい値</param>
    ///<param name="f">値を使いまわす関数</param>
    ///<returns>関数の適用結果</returns>
    ///<remark>
    ///2回だけ同じ値を使いたい場合などに使います。
    /// ex)
    ///   var temp = Calc(a);
    ///   var max = temp > thresholds ? temp : thresholds;
    ///      ↓
    ///   var max = Calc(a).With(x => x > thresholds ? x : thresholds);
    ///また、括弧が長くなるときにも有用です。
    ///今回は仕方ないのでここに定義しますが、意味としてはここへの定義は不適切です。
    ///</remark>
    public static U With<T, U>(this T a, Func<T, U> f){ return f(a); }
  }
  
  ///<summary>処理が失敗した時にその後の処理へ失敗した情報を伝播するクラス</summary>
  public abstract class Maybe<T>
  {
#region  ********** Maybeに関する定義 **********
    protected abstract T Value{ get; set; }
    public abstract bool IsNothing{ get; }
    
    ///<summary>値をMaybeの世界に入れる</summary>
    ///<param name="a">対象となる値</param>
    ///<returns>Maybeとして扱うことのできる値</returns>
    ///<remark>Return :: T -> Maybe T</remark>
    public static Maybe<T> Return(T a){ return new Just<T>(a); }
    
    ///<summary>値が有効なときのみ関数へ通してその戻り値を得る</summary>
    ///<param name="f">値へ適用したい関数</param>
    ///<returns>値が有効であれば関数を適用したMaybeインスタンス、有効でなければNothingインスタンス</returns>
    ///<remark>Bind :: Maybe T -> (T -> U) -> Maybe U</remark>
    public Maybe<U> FMap<U>(Func<T, U> f){ return this.Bind( a => new Just<U>(f(a)) ); }
    
    ///<summary>値が有効なときのみ関数へ通してその戻り値を得る</summary>
    ///<param name="f">値へ適用したい関数</param>
    ///<returns>値が有効であれば関数を適用したMaybeインスタンス、有効でなければNothingインスタンス</returns>
    ///<remark> Bind :: Maybe T -> (T -> Maybe U) -> Maybe U</remark>
    public Maybe<U> Bind<U>(Func<T, Maybe<U>> f)
    {
      if(this.IsNothing)
      {
        // すでに処理が失敗している場合、型だけ変換して返す
        return new Nothing<U>(((Nothing<T>)this).Exception);
      }
      else
      {
        try
        {
          // 成功したら値が返る
          return f(this.Value);
        }
        catch(Exception ex)
        {
          // 失敗したらNothingが返る
          return new Nothing<U>(ex);
        }
      }
    }
#endregion
#region   ********** アクション実行の定義 *********
    ///<summary>戻り値のない関数を実行させる</summary>
    ///<param name="f">させたい処理</param>
    public void Execute<U>(Func<T, U> f){ if(!this.IsNothing) { f(this.Value); } }
    
    ///<summary>戻り値のない関数を実行させる</summary>
    ///<param name="f">させたい処理</param>
    public void Execute(Action<T> f){ if(!this.IsNothing) { f(this.Value); } }
    
    ///<summary>戻り値及び引数のない関数を実行させる</summary>
    ///<param name="f">させたい処理</param>
    public void Execute(VoidFunc f){ f(); }
#endregion
#region   ********** チェーンに関するメソッド群 *********
    ///<summary>チェーンを終了してMaybeから値を取り出す</summary>
    ///<exception cref="System.Exception">チェーン中に発生した最初の例外</exception>
    ///<returns>Maybeから取り出した値</returns>
    ///<remark>Tear :: Maybe T -> T</remark>
    public T Tear(){ return this.Value; }
    
    ///<summary>チェーンを終了してMaybeから値を取り出し、無効であった場合はデフォルトの値を返す</summary>
    ///<param name="defaultValue">値が無効であった時に返す値</param>
    ///<returns>Maybeから取り出した値</returns>
    ///<remark>Tear :: Maybe T -> T -> T</remark>
    public T Tear(T defaultValue){ return this.IsNothing ? defaultValue : this.Value; }
    
    ///<summary>Just型とNothing型についてパターンマッチングを行って処理を分岐させる</summary>
    ///<param name="whenJustCallback">Justであった場合に呼び出すコールバック</param>
    ///<param name="whenNothingCallback">Nothingであった場合に呼び出すコールバック</param>
    ///<returns>チェーンを途切れさせない為の、自身への参照</returns>
    public Maybe<T> Match(Action<T> whenJustCallback, Action<Exception> whenNothingCallback)
    {
      if(this.IsNothing){ whenNothingCallback(((Nothing<T>)this).Exception); }
      else              { whenJustCallback(this.Value); }
      return this;
    }
    
    ///<summary>チェーン中に発生した例外を捕まえる</summary>
    ///<param name="whenExceptCallback">例外発生時に行う処理</param>
    ///<returns>チェーンを途切れさせない為の、自身への参照</returns>
    public Maybe<T> Catch(Action<Exception> whenExceptCallback)
    {
      if(this.IsNothing){ whenExceptCallback(((Nothing<T>)this).Exception); }
      return this;
    }
    
    ///<summary>チェーン中に発生した例外を握りつぶす</summary>
    ///<param name="defaultValue">例外発生時に差し替える値</param>
    ///<returns>チェーンを途切れさせない為の、自身への参照</returns>
    public Maybe<T> Rescue(T defaultValue)
    {
      if(this.IsNothing){ return Maybe.Return(defaultValue); }
      return this;
    }
    
    ///<summary>アンマネージドなインスタンスを扱った処理を行う</summary>
    ///<param name="disposable">IDisposableを実装したインスタンスを返す関数</param>
    ///<param name="f">適用したい関数</param>
    ///<typeparam name="D">アンマネージドクラス</typeparam>
    ///<returns>関数を適用した後の値</returns>
    ///<remark>Using :: T -> D -> (T -> D -> U) -> U</remark>
    public Maybe<U> Using<D, U>(ConstFunc<D> disposable, Func<T, D, U> f) where D : IDisposable
    {
      try
      {
        using(D d = disposable())
        {
          return this.FMap( b => f(b, d) );
        }
      }
      catch(Exception ex)
      {
        return new Nothing<U>(ex);
      }
    }
    
    ///<summary>チェーンで計算させる</summary>
    ///<param name="f">適用したい関数</param>
    ///<returns>計算後の値</returns>
    ///<remark>Calc :: Maybe T -> (T -> U) -> Maybe U</remark>
//    public Maybe<U> Calc<U>(Func<T, U> f){ return this.FMap(f); } // fmapそのものである為不要
    
    ///<summary>チェーンを途切れさせずに副作用のみ持つ関数を実行する</summary>
    ///<param name="f">行いたい処理</param>
    ///<returns>チェーンを途切れさせない為の、自身への参照</returns>
    ///<remark>Action :: T -> (T -> U) -> T</remakr>
    public Maybe<T> Action<U>(Func<T, U> f){ this.FMap(f); return this; }
    
    ///<summary>チェーンを途切れさせずに副作用のみ持つ関数を実行する</summary>
    ///<param name="f">行いたい処理</param>
    ///<returns>チェーンを途切れさせない為の、自身への参照</returns>
    ///<remark>Action :: T -> (T -> Void) -> T</remakr>
    public Maybe<T> Action(Action<T> f){ this.Execute(f); return this; }
    
    ///<summary>チェーンを途切れさせずに副作用のみ持つ関数を実行する</summary>
    ///<param name="f">行いたい処理</param>
    ///<returns>チェーンを途切れさせない為の、自身への参照</returns>
    ///<remark>Action :: T -> (Void -> Void) -> T</remakr>
    public Maybe<T> Action(VoidFunc f){ f(); return this; }
    
    ///<summary>同じ計算を複数回行わせる</summary>
    ///<param name="n">繰り返す回数</param>
    ///<param name=f>適用したい関数</param>
    ///<returns>複数回適用後の値</returns>
    ///<remark>Repeat :: Maybe T -> (T -> T) -> Maybe T</remark>
    public Maybe<T> Repeat(int n, Func<T, T> f)
    { return n > 0 && !this.IsNothing ? this.FMap(f).Repeat(n - 1, f) : this; }
    
    ///<summary>計算に使った全ての情報を返す</summary>
    ///<param name="f">適用した関数</param>
    ///<returns>元の値、適用した関数、適用結果をまとめたタプル</returns>
    public Maybe<Tuple<Maybe<T>, Func<T, U>, Maybe<U>>> All<U>(Func<T, U> f)
    { return Maybe.Return(Tuple.Create(this, f, this.FMap(f))); }
    
    public Maybe<T> When(Func<T, bool> doExecCallback, Func<T, T> f)
    { return this.FMap(doExecCallback).With( a => !a.IsNothing && a.Value ) ? this.FMap(f) : this; }
    public Maybe<U> When<U>(BranchStrategy<T, U> strategy)
    { return this.FMap(strategy.Run); }
#endregion
  }
  ///<summary>値が有効であることを示すクラス</summary>
  public class Just<T> : Maybe<T>
  {
    public Just(T a){ this.Value = a; }
    protected override T Value{ get; set; }
    public override bool IsNothing{ get{ return false; } }
  }
  ///<summary>値が無効であることを示すクラス</summary>
  public class Nothing<T> : Maybe<T>
  {
    public Nothing(Exception ex){ this.Exception = ex; }
    protected override T Value{ get{ throw this.Exception; } set{} }
    public override bool IsNothing{ get{ return true; } }
    public Exception Exception{ get; set; }
  }
  
  ///<summary>分岐戦略を扱うクラス</summary>
  public class BranchStrategy<T, U>
  {
    
    private List<Tuple<Func<T, bool>, Func<T, U>>> strategyMap;
    private Tuple<Func<T, bool>, Func<T, U>> otherwise;
    
    ///<summary>デフォルト処理と戦略表からクラスを初期化する</summary>
    ///<param name="otherwise">いずれの条件にも当てはまらなかった場合に実行される処理</param>
    ///<param name="strategyMap">条件とその場合の処理をレコードとしたリスト</param>
    ///<remark>
    ///このコンストラクタを使うと、ラムダ式と型推論の相性や可変引数とタプルの相性が悪い為、非常に冗長な書き方となります。
    /// ex)
    ///   private static BranchStrategy<int, string> pointStrategy = 
    ///     new BranchStrategy<int, string>(point => "red point"
    ///       ,Tuple.Create<Func<int, bool>, Func<int, string>>(point => point == 100, point => "very good")
    ///       ,Tuple.Create<Func<int, bool>, Func<int, string>>(point => point >=  80, point => "good")
    ///       ,Tuple.Create<Func<int, bool>, Func<int, string>>(point => point >=  60, point => "normal")
    ///       ,Tuple.Create<Func<int, bool>, Func<int, string>>(point => point >=  30, point => "bad")
    ///     );
    ///その為、もう一方のコンストラクタからインスタンス化し、そこからチェーンでAddメソッドを呼ぶほうが楽です。
    /// ex)
    ///   private static BranchStrategy<int, string> pointStrategy = 
    ///     new BranchStrategy<int, string>(point => "red point")
    ///       .Add(point => point == 100, point => "very good")
    ///       .Add(point => point >=  80, point => "good")
    ///       .Add(point => point >=  60, point => "normal")
    ///       .Add(point => point >=  30, point => "bad")
    ///     ;
    ///</remark>
    public BranchStrategy(Func<T, U> otherwise, params Tuple<Func<T, bool>, Func<T, U>>[] strategyMap)
    {
      this.strategyMap = strategyMap.ToList();
      this.otherwise = Tuple.Create((Func<T, bool>)( value => true ), otherwise);
    }
    ///<summary>デフォルト処理のみを指定してクラスを初期化する</summary>
    ///<param name="otherwise">いずれの条件にも当てはまらなかった場合に実行される処理</param>
    public BranchStrategy(Func<T, U> otherwise)
    {
      this.strategyMap = new List<Tuple<Func<T, bool>, Func<T, U>>>();
      this.otherwise = Tuple.Create((Func<T, bool>)(value => true), otherwise);
    }
    ///<summary>条件と処理を追加する</summary>
    ///<param name="condition">値を入れると条件に合うかを判定する関数</param>
    ///<param name="calc">行う処理</param>
    ///<returns>チェーンでつなぐ為の自分への参照</returns>
    public BranchStrategy<T, U> Add(Func<T, bool> condition, Func<T, U> calc)
    {
      this.strategyMap.Add(Tuple.Create(condition, calc));
      return this;
    }
    ///<summary>値を受け取り、これに応じた関数を適用して返すメソッド</summary>
    ///<param name="value">判断基準となる値</param>
    ///<returns>値に応じた関数を適用した値</returns>
    public U Run(T value)
    {
      return this.strategyMap.FirstOrDefault( strategy => strategy.Item1(value) )
                   .With( strategy => strategy ?? this.otherwise )
                   .Item2(value);
    }
  }
}

　Maybeモナドベースに実装しました。
　例外を中でトラップするというので想像がついた方もいらっしゃるかもしれません。
　軽くだけ使い方を紹介します。

using System;
using MaybeChain;

public static class MainApp
{
  [STAThread]
  public static void Main()
  {
    var strategy = new BranchStrategy<int, string>(point => "red point")
      .Add(point => point == 100, point => "very good")
      .Add(point => point >=  80, point => "good")
      .Add(point => point >=  60, point => "normal")
      .Add(point => point >=  30, point => "bad")
    ;
    Console.WriteLine("点数を入力してください");
    Console.ReadLine()
      .Wrap()
      .FMap( str => Convert.ToInt32(str) )
      .When( strategy )
      .Catch( ex => Console.WriteLine(ex.ToString()) )
      .Rescue( "不正な値です" )
      .Action( msg => Console.WriteLine(msg) );
  }
}

結果

1回目
点数を入力してください
30
bad
続行するには何かキーを押してください . . .

2回目
点数を入力してください
0
red point
続行するには何かキーを押してください . . .

3回目
点数を入力してください
91
good
続行するには何かキーを押してください . . .

4回目
点数を入力してください
xxxx
System.FormatException: 入力文字列の形式が正しくありません。
   場所 System.Number.StringToNumber(String str, NumberStyles options, NumberBuffer& number, NumberFormatInfo info, Boolean parseDecimal)
   場所 System.Number.ParseInt32(String s, NumberStyles style, NumberFormatInfo info)
   場所 System.Convert.ToInt32(String value)
   場所 MainApp.<Main>b__b(String str)
   場所 MaybeChain.Maybe`1.<>c__DisplayClass1`1.<FMap>b__0(T a)
   場所 MaybeChain.Maybe`1.Bind[U](Func`2 f)
不正な値です
続行するには何かキーを押してください . . .

　こんな感じの使用感です。
　戦略的に分岐させ、例外が発生しても処理を続けられます。

　それでは中身を少しずつのぞいてみます。

Maybeモナドの実装

　一番のメインとなるMaybeモナドから。

class Maybe<T>

#region  ********** Maybeに関する定義 **********
    protected abstract T Value{ get; set; }
    public abstract bool IsNothing{ get; }
    
    ///<summary>値をMaybeの世界に入れる</summary>
    ///<param name="a">対象となる値</param>
    ///<returns>Maybeとして扱うことのできる値</returns>
    ///<remark>Return :: T -> Maybe T</remark>
    public static Maybe<T> Return(T a){ return new Just<T>(a); }
    
    ///<summary>値が有効なときのみ関数へ通してその戻り値を得る</summary>
    ///<param name="f">値へ適用したい関数</param>
    ///<returns>値が有効であれば関数を適用したMaybeインスタンス、有効でなければNothingインスタンス</returns>
    ///<remark>Bind :: Maybe T -> (T -> U) -> Maybe U</remark>
    public Maybe<U> FMap<U>(Func<T, U> f){ return this.Bind( a => new Just<U>(f(a)) ); }
    
    ///<summary>値が有効なときのみ関数へ通してその戻り値を得る</summary>
    ///<param name="f">値へ適用したい関数</param>
    ///<returns>値が有効であれば関数を適用したMaybeインスタンス、有効でなければNothingインスタンス</returns>
    ///<remark>
    ///関数の第一引数が自身であると考えて
    /// Bind :: Maybe T -> (T -> Maybe U) -> Maybe U
    ///</remark>
    public Maybe<U> Bind<U>(Func<T, Maybe<U>> f)
    {
      if(this.IsNothing)
      {
        // すでに処理が失敗している場合、型だけ変換して返す
        return new Nothing<U>(((Nothing<T>)this).Exception);
      }
      else
      {
        try
        {
          // 成功したら値が返る
          return f(this.Value);
        }
        catch(Exception ex)
        {
          // 失敗したらNothingが返る
          return new Nothing<U>(ex);
        }
      }
    }
#endregion

　まずはReturnメソッドから。

    ///<summary>値をMaybeの世界に入れる</summary>
    ///<param name="a">対象となる値</param>
    ///<returns>Maybeとして扱うことのできる値</returns>
    ///<remark>Return :: T -> Maybe T</remark>
    public static Maybe<T> Return(T a){ return new Just<T>(a); }

　Returnメソッドでは、新しいJust型のインスタンスを返しています。
　Justの具体的な実装はこうなっています。

  ///<summary>値が有効であることを示すクラス</summary>
  public class Just<T> : Maybe<T>
  {
    public Just(T a){ this.Value = a; }
    protected override T Value{ get; set; }
    public override bool IsNothing{ get{ return false; } }
  }

　単純に、指定された型の値を格納するだけのコンテナです。
　もう一つのMaybeを継承したクラスの実装も並べて書きます。

  ///<summary>値が無効であることを示すクラス</summary>
  public class Nothing<T> : Maybe<T>
  {
    public Nothing(Exception ex){ this.Exception = ex; }
    protected override T Value{ get{ throw this.Exception; } set{} }
    public override bool IsNothing{ get{ return true; } }
    public Exception Exception{ get; set; }
  }

　こちらは値を持たず、アクセスしようとすると問答無用で例外を投げつけます。
　ここからなんとなく、値が有効か無効かをIsNothingメソッドとか使いながら
判断するのかなーと想像してもらえると嬉しいです。

　次はFMapメソッドを見てみます。

    ///<summary>値が有効なときのみ関数へ通してその戻り値を得る</summary>
    ///<param name="f">値へ適用したい関数</param>
    ///<returns>値が有効であれば関数を適用したMaybeインスタンス、有効でなければNothingインスタンス</returns>
    ///<remark>Bind :: Maybe T -> (T -> U) -> Maybe U</remark>
    public Maybe<U> FMap<U>(Func<T, U> f){ return this.Bind( a => new Just<U>(f(a)) ); }

　読み解く前に軽く説明すると、このメソッドはLinqでいうSelectメソッドと同等のものです。
　具体的には、コンテナから要素を取り出して、関数により変換後にまた同じコンテナへ格納し、
そのコンテナを返すという動きをします。

　それでは実際に中身を読んでみます。
　引数に、コンテナが格納する型から別の型（同じでも可）へ変換するデリゲートが渡されています。
　それをFunc<T, U>のデリゲートからFunc<T, Maybe<U>>へ変換しています。
　そしてその変換したデリゲートをBindメソッドへ渡しています。

　次にBindメソッドの中身を見てみます。

    ///<summary>値が有効なときのみ関数へ通してその戻り値を得る</summary>
    ///<param name="f">値へ適用したい関数</param>
    ///<returns>値が有効であれば関数を適用したMaybeインスタンス、有効でなければNothingインスタンス</returns>
    ///<remark>Bind :: Maybe T -> (T -> Maybe U) -> Maybe U</remark>
    public Maybe<U> Bind<U>(Func<T, Maybe<U>> f)
    {
      if(this.IsNothing)
      {
        // すでに処理が失敗している場合、型だけ変換して返す
        return new Nothing<U>(((Nothing<T>)this).Exception);
      }
      else
      {
        try
        {
          // 成功したら値が返る
          return f(this.Value);
        }
        catch(Exception ex)
        {
          // 失敗したらNothingが返る
          return new Nothing<U>(ex);
        }
      }
    }

　やってること自体はシンプルです。
　もし、自身がNothing（無効な値を表す）なら例外内容はそのままにコンテナの型を変えます。
　つまり、中の要素に触らず、渡された関数も使うことなく形だけ変えて処理が終わります。
　次に、もし自身が有効であれば渡されたデリゲートをコンテナの中身へ適用して返そうとします。
　渡されたデリゲートがMaybe型へ変換してくれるのでそのまま返せますね。
　もし、このデリゲートを実行中に例外が発生した場合はその例外内容を覚えさせて
Nothingを返します。
　こうすることで、例外が発生しても中断することなく、無効な値として扱うことができます。
　仮にNothingに対してBindメソッドを呼び出されても、上のガードによって無効な値の中身に
触れられることはありません。そつなく無難にしのいでます。
　また、中の値を得るためのValueプロパティはprotectedであるため、
外部から直接触れられることはありません。
　中の値へ触れるには、このBindメソッドへ渡すデリゲートからのみとなります。

　ちなみにこれらのメソッド名についてですが、一般的な名前を使っている為、
Returnが気持ち悪いとかは勘弁してください。
　Wikipedia先生から引用させていただきます。

形式的には、モナドは型構築子 M とふたつの演算 bind と return から構成される(returnをunitと呼ぶこともある)。
return 演算は素な型の値を受け取って、構築子によりモナド的なコンテナに詰めて返す。これは モナド的な値を作成する。
bind 演算はモナド的な値と、素な型の値からモナド的な値への関数を受け取って、新しいモナド的な値を返す。
　～ 出典:Wikipedia モナド (プログラミング) - Wikipedia ～

　同じページにちょうどMaybeモナドについても記述されているので読んでみてください。

外界との橋渡し、WrapメソッドとTearメソッド

　それでは次に、このMaybeの世界とC#の世界をつなぐ、WrapとTearメソッドについて見てみます。
　まずはMaybeクラス（ジェネリックでない）のWrapメソッドとReturnから。

class Maybe

    ///<summary>チェーンを始める為にMaybeで包む</summary>
    ///<param name="a">チェーンの先頭となる値</param>
    ///<returns>Maybeで包まれた値</returns>
    ///<remark>Wrap :: T -> Maybe T</remark>
    public static Maybe<T> Wrap<T>(this T a){ return Maybe.Return(a); }
    
    ///<summary>値をMaybeの世界に入れる</summary>
    ///<param name="a">対象となる値</param>
    ///<returns>Maybeとして扱うことのできる値</returns>
    ///<remark>Return :: T -> Maybe T</remark>
    public static Maybe<T> Return<T>(T a){ return Maybe<T>.Return(a); }

　Wrapメソッドは拡張メソッドとなっており、Maybe.Returnを呼び出しています。
　この型引数はどんな型でもいいので、気軽にMaybeの世界へ入れるよう拡張メソッドとしています。
　また、こちらでもわざわざReturnメソッドを実装しているのは型推論させるためです。
　有名どころでは、Tuple.Createなどと同じ考え方です。
　このメソッドがなければ、Maybe<T>.Returnを呼び出す際、型引数まで指定しなければ
Returnを呼び出せません。
　例えばこんな感じ。

// 型推論をさせない場合
var maybe1 = Maybe<Dectionary<string, int>>.Return(new Dictionary<string, int>());
// 型推論させた場合
var maybe2 = Maybe.Return(new Dictionary<string, int>());
// おまけでvar型を使わなかった場合
Maybe<Dictionary<string, int>> maybe3 = Maybe<Dictionary<string, int>>.Return(new Dictionary<string, int>());

　Dictionaryくらいならまだ楽な方ですが、これでもずいぶん手間です。
　また、DictionaryのKeyがStringからintに変わったなどがあった場合、2箇所直さなければなりません。
　varすら使わなかったらと思うと型推論を生かすって大切ですね。

　次はTearメソッドを見てみます。

class Maybe<T>

    ///<summary>チェーンを終了してMaybeから値を取り出す</summary>
    ///<exception cref="System.Exception">チェーン中に発生した最初の例外</exception>
    ///<returns>Maybeから取り出した値</returns>
    ///<remark>Tear :: Maybe T -> T</remark>
    public T Tear(){ return this.Value; }
    
    ///<summary>チェーンを終了してMaybeから値を取り出し、無効であった場合はデフォルトの値を返す</summary>
    ///<param name="defaultValue">値が無効であった時に返す値</param>
    ///<returns>Maybeから取り出した値</returns>
    ///<remark>Tear :: Maybe T -> T -> T</remark>
    public T Tear(T defaultValue){ return this.IsNothing ? defaultValue : this.Value; }

　こちらはMaybeのコンテナを破いて中身を取り出すメソッドで、オーバーロードが2つあります。
　一つ目の引数無しのものは、中身が何であろうが無理やり取り出そうとします。
　Maybeな世界の中では無効な値であろうが無難に流せていましたが、厳密なC#本来の
世界に帰ってきたときは無効なままではいられません。現実はつらいものです。
　ですのでさっきのNothing<T>の実装を除いたときにわかるように、中身が無効な値で
あった場合は例外が投げつけられます。
　これに対し、二つ目のオーバーロードではデフォルト値を引数として渡します。
　これにより、中身が無効な値であった場合はデフォルト値を返して例外を握りつぶします。
　例えば、コンフィグファイルの読み込みに失敗した場合にデフォルト値を返す、などの使い方では
こちらが使いやすいと思います。

　長くなりそうなので今日はここまでで！

おわりに

　この実装は、C#の中に新しい文法を作っている気分になれてなかなか楽しいです。
　Maybeによるチェーンにとってメタ的な値（例えばRepeatメソッドの繰り返す回数など）にも、
Maybeの中身から 引っ張ってこれるような方法を考えたいと思います。
　完成させていち早く快適なチェーンライフを送りたいです。

参考

yohshiy様(2013) 静的型付けでの型推論と動的型付けでの型チェック | プログラマーズ雑記帳

　型推論に関する内容が書かれています。
　C#のvar型はVBのVariant型やjavascriptのvar型とは意味が違います。
　この記事では、それがどう違うのかという大切なところがわかりやすく説明されています。

yohshiy様(2014) C# やるなら LINQ を使おう | プログラマーズ雑記帳

　同じくyohshiy様より。
　自分的にはLinqと言えばここ！！ってほどLinqについて学ばせて頂きました。
　Linqへの理解があるとこの記事がわかりやすくなる為、苦手な方にはこちらをおすすめします。

Gab_km様(2011) #95 もしC#プログラマーがMaybeモナドを実装したら « C# « a wandering wolf

　初めてモナドというものを知った時に読ませていただきました。
　自分の良く知っている言語で書かれていると安心感があります。

C# メソッドチェーンしたくて仕方なかった

C#

はじめに

メソッドチェーン楽しいですよね！
Linqとか使ってると止まらなくなっちゃいますが、これに慣れるとどんなものからでもチェーンで書きたくなります。
そこで、ストレスを感じず楽しくコーディングするために、汎用的に使えるものを考えてみました。

実装

いきなり実装に入ります。

using System;

public static class ChainMethoads
{
    public static IChain<T> Wrap<T>(this T a){ return new Chain<T>(a); }
    
    public interface IChain<T>
    {
        IChain<U> Calc<U>(Func<T, U> f);
        IChain<T> Action(Action<T> f);
        IChain<T> Action<U>(Func<T, U> f);
        IChain<T> Repeat(int n, Func<T, T> f);
        T Tear();
    }
    private class Chain<T> : IChain<T>
    {
        private T a;
        public Chain(T a){ this.a = a; }
        
        public IChain<U> Calc<U>(Func<T, U> f){ return f(this.a).Wrap(); }
        public IChain<T> Action(Action<T> f){ f(this.a); return this; }
        public IChain<T> Action<U>(Func<T, U> f){ f(this.a); return this; }
        public IChain<T> Repeat(int n, Func<T, T> f)
        { return n > 0 ? this.Calc(f).Repeat(n - 1, f) : this; }
        
        public T Tear(){ return this.a; }
    }
}

　変数名ひどいとか気にしない、手続的なことはほとんどしてないのでこっちの方がわかりやすいはず。
　特に複雑なことはしてなくて、Chainクラスの実体を隠蔽したいから内部クラスにしてIChain越しに
操作させてるだけです。
　軽くだけ各メソッドの説明をすると、
　　・Wrapメソッド : チェーン中の値に直接触れられないよう隠蔽するためにIChainで包む。
　　・Calcメソッド : 関数を渡して適用した結果を返す。LinqのSelectみたいなイメージ。
　　・Actionメソッド : 副作用のみある処理（主に状態が変わる形のものを想定）を渡し、
　　　元の値を返すことでチェーンをつなぐ。
　　・Repeatメソッド : 指定回数、渡した関数を適用する。
　　・Tearメソッド : 計算結果の値を得る。IChainの膜を破いて中身を取り出すイメージ。
　です。
　思いついた処理内容がこれくらいだったので実装したメソッドは少ないですが、欲しくなったときに実装すればいいやくらいの感じで気楽に作りました。
　遅延評価させるかは考えましたが、副作用のある処理をチェーンしたかったのがことの発端なのでやめときました。
　使い方はこんな感じ。

using System;

public static class ChainTest{
    [STAThread]
    public static void Main()
    {
        Console.WriteLine(
            1.Wrap().Calc( x => x * 2)
                    .Action( x => Console.WriteLine(x) )
                    .Repeat( 10, x => x * 2 )
                    .Tear()
        );
    }
}

　この実装の前に、実は先に拡張メソッドを使って実装してたのでこちらものせときます。
　Haskell風に型シグネチャも書いときます。
　ただし、ジェネリック型はC#の記述に沿って大文字とさせてもらいます。
　また、C#で副作用を期待した使い方をする箇所があるため、値がないことをVoidと書きます。
　カリー化は特に必要を感じなかったためとりあえずしてません、いるときになればやります。

namespace AllChain
{
    public static class ChainExtendMethoads
    {
        // Calc :: T -> (T -> U) -> U
        public static U Calc<T, U>(this T a,  Func<T, U> f){ return f(a); }
        // Action :: T -> (T -> Void) -> T
        public static T Action<T>(this T a, Action<T> f){ f(a); return a; }
        // Action :: T -> (T -> U) -> T
        public static T Action<T, U>(this T a, Func<T, U> f){ f(a); return a; }
        // Repeat :: T -> int -> (T -> T) -> T
        public static T Repeat<T>(this T a, int n, Func<T, T> f)
        { return n > 0 ? f(a).Repeat(n - 1, f) : a; }
        
        // Left :: T -> (T -> U) -> T
        public static T Left<T, U>(this T a, Func<T, U> f){ f(a); return a; }
        // Right :: T -> (T -> U) -> T -> U
        public static Func<T, U> Right<T, U>(this T a, Func<T, U> f){ f(a); return f; }
        // All :: T -> (T -> U) -> (T, T -> U, U)
        public static Tuple<T, Func<T, U>, U> All<T, U>(this T a, Func<T, U> f)
        { return Tuple.Create(a, f, f(a)); }
    }
}

　こっちのが実装自体は綺麗。
　LeftとRightとAllはなんかあったら面白そうだから別で実装してみたけどどこかで使えるのだろうか。
　さすがに見える範囲が広いと混乱招きそうなのでnamespace区切っときました。
　使い方はこんな感じ。

using System;
using AllChain;

public static class TestAll
{
    [STAThread]
    public static void Main()
    {
        Console.WriteLine(
            1.Calc( x => x * 2)
             .Action( x => Console.WriteLine(x))
             .Repeat( 4, x => x * x)
             .Action( x => Console.WriteLine(x));
        );
    }
}

　すべての型に直接このメソッドが使える為、隠蔽したクラスを用いた方法とは違ってWrapメソッドやTearメソッドが不要です。
　すっきりシンプルにチェーンできて気持ちいいですね！

　最初は、

using System.Collections.Generic;
//using System.Linq;

public static class LinqExtendMethoads
{
    public static IEnumerable<T> Wrap<T>(this T a){ yield return a; }
    public static T Tear<T>(this IEnumerable<T> a){ a.ToArray[0]; }
}

　とかしておいてやればLinq使い放題でいいかもとか思ったけど、使ってみるとSelectくらいしか使わない上に遅延評価が悪い方向に働くことが多かったのでやめときました。

おわりに

　実は一番最初、C#で汎用的なモナド(IMonadを実装すればバインドできるような物)を実装しようとしたけど納得いく形に再現できずこんな感じの実装にしました。
　必要な関数をデリゲートとして渡してもらって動的に作ればあるいはとかも考えたけど、結局クラスメソッドの実装が保障されてないと無理なところが出てきて無理でした。
　そう聞くと妥協のようなものに見えますが、こっちはこっちで使用感自体は悪くないです！
　みなさんも楽しいメソッドチェーンライフを送ってください！
　今回は参考にするページも特にないので参考はなしです。

Haskellの勉強 その3 : genD, gcdex

Haskell 学習の足跡 アルゴリズム 暗号 C#

はじめに

　色々あって更新に時間がかかりました…
　勉強自体は進んでいるので書きたいことも増えているので頑張りたいです。

　それでは今日も、Haskell で RSA暗号 を実装していきます。
　処理がいい感じに複雑なので楽しいと思います！

実装内容

　本エントリでは。鍵生成の
　　・ 秘密鍵 d の生成 : genD , gcdex
　を実装します。

実装

genD

Haskell

  -------------------------------------------
  --  e * d ≡ 1  (mod φ(n))
  --  e * d + m * φ(n) = 1
  --  e * d + φ(n) * m = 1 ...1
  --   式 1 から拡張ユークリッド互除法より d を求める
  -------------------------------------------
  genD :: Integer -> Integer -> Integer
  genD phn e = d `mod` phn
    where
      (_, d, _) = Multiplication.gcdex e phn

C#

  public static long GenD(long phn, long e)
  {
    return (Multiplication.GcdEx(e, phn)[1] + phn) % phn;
  }

　どちらもほとんど同じ感じなソースですね！
　Haskell で変な束縛がありますが、これはタプルに値を受け取るときに使わない要素がある場合は '_' と書いておくことで明示的にいらないと言ってます。

　内容を比較してみます。
　さっきほとんど一緒と言いましたが、微妙に違う場所がありますね。
　Haskell では、戻ってきた値から直接剰余をとっていますが、 C# では剰余する値を足してからとっています。
　これは、負数に対する剰余演算が違う挙動をするためです。
　Haskell では、n, m を自然数とすると
\begin{eqnarray*} -n \ {\rm mod} \ m = (m - n) \ {\rm mod} \ m \end{eqnarray*} 　という考え方*1になります。
　一方 C# では
\begin{eqnarray*} -n \ {\rm mod} \ m = - (n \ {\rm mod} \ m) \end{eqnarray*} 　という考え方*2となり、解が異なってしまいます。
　どちらも考え方としてはあり*3なのですが、今考えたい世界では Haskell が正しい計算をしてくれています。
　なので、C# では被除数が負数になることのないよう調整しています。

gcdex

　ソースを載せる前に、拡張されたユークリッドの互除法について軽く説明を。
　効率的に最大公約数を得るユークリッドの互除法というものがあるのですが、これに手を加えることで、a, b を既知の自然数として
\begin{eqnarray} ax + by = gcd \end{eqnarray} 　となる x と y をついでに求めることができるよう拡張したものを拡張されたユークリッドの互除法とか呼んだりされています。

　d の条件は、
\begin{eqnarray*} ed&\equiv& 1\pmod {φ(n)} \newline ed + mφ(n)&=& 1 \newline \end{eqnarray*} 　と表すことができます。
　e 及び φ(n) が既知なので、式 (1) と同じ形となるため拡張されたユークリッドの互除法を適用でき、これから d を求めることができます。

　具体的な手順は、
\begin{eqnarray*} &r_0=ax_0+by_0 \\ &r_1=ax_1+by_1 \\ &\vdots \\ &r_n=ax_n+by_n \\ &\vdots \\ &r_{res}=ax_{res}+by_{res} \\ &r_{res+1}=ax_{res+1}+by_{res+1}=0 \\ \mbox{ただし}\\ &q_n=\lbrack r_{n-1} \div r_{n-2} \rbrack \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \\ &x_n= \begin{cases} 1 & (n=0)\\ 0 & (n=1)\\ x_{n-2}-p_n(x_{n-1})&(n\geqq2) \end{cases}\\ \\ &y_n= \begin{cases} 0 & (n=0)\\ 1 & (n=1)\\ y_{n-2}-p_n(y_{n-1})&(n\geqq2) \end{cases}\\ \end{eqnarray*} です。
　すると、${\rm r_{res}}={\rm gcd}(a,b)$ となっており、式(1)を満たす整数のペアが求まります。

　意味を分かりやすくするため、同じ操作をする式を関数に抜き出しておきます。
\begin{eqnarray*} \mbox{ここで}\\ &{\rm current}(n,m,q)=n-mq\\ \mbox{とおいて}\\ &x_n= \begin{cases} 1 & (n=0)\\ 0 & (n=1)\\ {\rm current}(x_{n-2},x_{n-1},q_n)&(n\geqq2) \end{cases}\\ \\ &y_n= \begin{cases} 0 & (n=0)\\ 1 & (n=1)\\ {\rm current}(y_{n-2},y_{n-1},q_n)&(n\geqq2) \end{cases}\\ \end{eqnarray*} 　またこの時 $r_n = r_{n-2} \ {\rm mod} \ r_{n-1}$ となる性質もあり、実装にはこの式も使います。

　これから書くソースを追いかけるために、手順だけ説明しました。
　なぜこれで求まるかなどはここでは重要でないため、気になる方は参考のリンクを読んでみてください！

　それでは実装に移ります。
　 Haskell

  ----------------------------
  --  拡張ユークリッド互除法
  ----------------------------
  gcdex :: Integer -> Integer -> 
           (Integer, Integer, Integer)
  gcdex n m = gcdex' n m 1 0 0 1
    where
      gcdex' ::  Integer -> Integer -> Integer ->
                 Integer -> Integer -> Integer ->
                 (Integer, Integer, Integer)
      gcdex' r0 r1 x0 x1 y0 y1
        | r1 == 0   = (r0, x0, y0)
        | otherwise = gcdex' r1 r2 x1 x2 y1 y2
        where
          (q, r2) = quotRem  r0 r1
          next n0 n1 =  n0 - n1 * q
          x2 = next x0 x1
          y2 = next y0 y1

C#

  public static long[] GcdEx(long a, long b)
  {
    long r0 = a, x0 = 1, y0 = 0,
         r1 = b, x1 = 0, y1 = 1,
         rw,     xw,     yw;
    long q;
    while(r1 > 0)
    {
      q = r0 / r1;
      rw = r0;
      xw = x0;
      yw = y0;
      
      r0 = r1;
      x0 = x1;
      y0 = y1;
      
      x1 = xw - x1 * q;
      y1 = yw - y1 * q;
      r1 = rw % r1;
    }

　RSA暗号実装に当たり、書き方という点で最も差が出る関数だと感じています。
　Haskell のソースを追いかけていきます。

  gcdex n m = gcdex' n m 1 0 0 1

　gcdex 関数そのものの定義はこれです。
　怪しげな数字を入れて gcdex' 関数を呼び出していますね！
　これは、実際の処理を隠すために where の下へ定義し、初期値を入れて呼び出しています。
　ではその gcdex' の定義を見ていきましょう。
　where 句の下に宣言されています。

    where
      gcdex' r0 r1 x0 x1 y0 y1
        | r1 == 0   = (r0, x0, y0)
        | otherwise = gcdex' r1 r2 x1 x2 y1 y2

　なんか変なパイプができてきました。
　これはガードと呼ばれ、条件を上から順番に評価していき True となった行の式を実行するものです。
　崩してmax関数とか書いて数式と対比するとわかりやすいかも。

  max a b | a > b     = a
          | otherwise = b

　これは、
\begin{eqnarray*} {\rm max}(a,b)= \begin{cases} a & ( a > b ) \\ b & ( otherwise ) \end{cases} \end{eqnarray*} と同じ意味です。
　見た目もほとんど一緒な感じ。
　otherwise は論理値型の True と同じで、ここまで流れ込めば必ず実行されます。
　switch 文の default と同じと思ってもいいかも！

　これを頭に入れて読んでいきます。

      gcdex' r0 r1 x0 x1 y0 y1

　引数が多いですね…
　でも、これが意味するところは数式からわかると思います。
\begin{align*} &r_0=ax_0+by_0 \\ &r_1=ax_1+by_1 \end{align*} 　でしたね！
　この場合の $r_2,\ x_2,\ y_2$ は二つ手前までの式を持っていると求まるため、このような引数となっています。

　次は、分かりやすさのため下の行から読みます。

        | otherwise = gcdex' r1 r2 x1 x2 y1 y2

　個人的に、最高に気持ちいい表現のできた行です！！
　内容は、gcdex' を呼び出すだけの内容です。
　つまり再帰してますね。
　Haskell ではループ構文が基本的になく、再帰で繰り返しの処理を表現します。
　再帰であるため、当然引数を変えて呼び出しています。
　どのような再帰となっているかは一目瞭然ですね！
　一つ添え字を進めて呼び出しています。

　それでは飛ばした前の行に戻ってみます。

        | r1 == 0   = (r0, x0, y0)

　これは、再帰の終了条件となっています。
　数式での $r_{res+1} = 0$ に当たります。
　この一つ前の式に欲しい値が詰まっているので、添え字が 0 の値をまとめて返して終了となっています。
　終了条件がはっきりと見えるため再帰でも読みやすくて安全！
　何を返すのかも明確になってますね！

　次は、添え字を進めるための定義を読みます。

        where
          (q, r2) = quotRem  r0 r1
          next n0 n1 =  n0 - n1 * q
          x2 = next x0 x1
          y2 = next y0 y1

　ここで出てくる quotRem 関数は、整数の除算と剰余を同時に得る関数です。
　割ったついでに余りも取っとこうって関数です。
　(割った結果, 余り) というタプルに入って返ってきます。
　next関数は数式でのcurrent関数と一緒ですね。*4
　これによって x と y を進め、$r_n = r_{n-2} \ {\rm mod} \ r_{n-1}$ だったので r はただ剰余をとるだけで進みます。

　これに対する C# も少し見てみます。
　めんどいのでソースは引っ張ってきませんが、ループの中でひたすらワーク変数に移しておいて加工して同じ変数にずらして代入して…といったよくある実装になっています。

考察

　gcdex 関数が実装中も読んでいても面白い関数でした。

　Haskell ではそもそも一つの関数につき一つの式が原則であるため、ループが基本的には表現できません。
　それでもこの原則を貫くことで、見通しの良いソースとなるため、手続型の言語では読みづらいとされることの多い再帰処理の表現力が高まっているように感じました。
　というか書かれてるのは数式そのものだから表現力は高いはず。

　これに対して C# では、一応めいいっぱい読みやすく書いたつもりだけどやっぱりループでは同じ変数を違う意味に書き換えながらの処理となり、変数の数と比例して読みづらくなるように感じました。
　また、式を与えられてない状況でこれだけを読んでも、どのような漸化式をたどっているか想像しづらいか、そもそも式を意識できないと思います。

　メモリやスタックの制約が厳しい状態であれば C# のような実装にならざるを得ませんが、そうでなければループ（特に while のループ）を再帰にしてみると手続型でも場合によってはすっきりとしたスリムなソースになるかもしれません！

おわりに

　RSA暗号自体はすでに実装済みですが、gcdex 関数が書いてる途中も読み直しても一番楽しいお気に入りの関数です。
　再帰という表現方法は、以前から表現力が高い場面*5があると思っていましたが、こんな小さな関数でもここまでの差が出るのが面白いです。
　手続型の言語において、なんでもかんでも再帰に書き直せばいいというものではないと思うけど、実装方法の一つに再帰もあると頭の片隅にでも置いておくと、動的な計算に芯が通りそうです。

参考

新潟大学 竹内照雄教授(2009) 拡張ユークリッド互除法

　拡張されたユークリッド互除法について詳しく解説されております。
　初めて実装したときに参考にさせていただきました。

rooooomania様(2015) Haskell で条件分岐 - Qiita

　Haskell における分岐が、段階的かつシンプルにまとめられています。
　ガード以外にも実行する式を変える方法の参考になります。

*1:最小非負剰余と呼ばれる。

*2:絶対値最小剰余と呼ばれる。

*3:言語によって様々で、C言語に至ってはコンパイラ依存。

*4:数式では注目している添え字を返すから current、ソースでは次の添え字を返すから next とした。

*5:特にオブジェクト指向言語でinterfaceや抽象クラスと組み合わせたとき。

式がうまく表示されない…

疑問 解決

下のこれがうまく表示できないんだけどなんで…
\begin{eqnarray*} a_{1,1}=b_{1,1} \end{eqnarray*}

↓中身
a{1,1}=b{1,1}

これだとうまく表示される

\begin{align} a_{2,2}=b_2 \end{align}

↓中身
a_{2,2} = b_2

うまくいく例
\begin{eqnarray*} a_1=b_1\newline a_{a,a}=b_a\newline a_a=b_a\newline \end{eqnarray*}

分数はうまくいくから波括弧が悪さしてるわけでは無さげ
\begin{eqnarray*} \frac{1}{1} \end{eqnarray*}

分数で下付き文字
\begin{eqnarray*} \frac{a_{1,1}}{1} \end{eqnarray*}

分母も下付き文字
\begin{eqnarray*} \frac{a{1,1}}{b{1,1}} \end{eqnarray*}

やっぱりだめみたい
下付き文字で波括弧が二つ出てきた場合だけ表示されないけどなんでだろう。。。
手元で使ってるMarkdownのエディタでは正しく表示されてるから環境の問題っぽい？
他の人から見たらちゃんと変換されてるのだろうか

追記

　解決しました！！
　Markdownのアンダースコアと解釈されて、斜体になってたようです。
　記法が間違ってると言われて見直すとアンダースコア消えて斜体になってますね…
　'\_' と書いてやることでエスケープするとうまく表示されるようになりました！
　こんな感じ

\begin{align*} a_{1,1}=b_{1,1} \end{align*} 　中身↓
a\_{1,1}=b\_{1,1}

Haskellの勉強 その2 : genN, genPhiN

Haskell 学習の足跡 暗号 C#

はじめに

　先日までとブログの編集方法を変えて Markdown という書き方に変えました。
　Markdown では直接 HTML を埋め込むことができるので楽です！
　しかしその弊害として、文字に色を付けるのが少し面倒になりました。。。
　前の記事が過剰に色づけしてる感はあったので、これからはほんとに強調したい箇所のみに色を付けることにします。

　それでは今日こそ Haskell で RSA暗号を実装していきます。
　処理の簡単な関数を扱って、Haskell の基本的な文法を押さえていきます。

書き方

　実装していくに当たり、Haskell と僕の大好きな C# を比較しながら書いていきます。
　しかし、違う言語間である（しかも設計思想も全然違う！）ため、記法やものの呼び方が違います。 　そこで、比較をしやすくするためにこれをどう呼んでどう書くかを示しておきます。

関数

　C# は純オブジェクト指向言語であり、関数という概念がありません。
　そこで Haskell と合わせるために以下の条件を満たす C# の静的メソッドを関数と呼ぶことにします。
　　・メソッド呼び出し時の引数が同じであれば必ず同じ戻り値を返す。
　また、この条件のことを "参照透過性"*1 といいます。

変数

　Haskell では変数へ一度値を代入すると、再代入することができません。
　C# の readonly なイメージですね。
　このため、変数*2へ値を代入することを "束縛する" といいます。
　これは Haskell と C# で使い分けることとします。

命名規則

　Haskell での関数及び束縛数の命名は、シンボルの先頭が小文字でなければならないため、Camel 記法*3 または Snake 記法*4しか許されません。
　C# では関数名は Pascal 記法*5、変数名は Camel 記法が推奨されます。
　他にもそれぞれの言語で命名規則が違うことや、そもそも片方の言語にしか存在しない概念への命名などがあります。
　これらについては、それぞれの言語で推奨・強制させられる記法で命名していきます。
　見出しで関数名などを使う場合は、Haskell の記法に合わせることにします。

実装内容

　本エントリでは、鍵生成の
　　・ 法となる整数 n の計算 : genN
　　・ φ(n) の計算 : genPhiN
を実装します。
　また、処理内容が簡単なので Haskell の基本的な構文をメインに書きたいと思います。

実装

genN

Haskell

  ---------------
  --  n = p * q
  ---------------
  genN :: (Integer, Integer) -> Integer
  genN primes = p * q
    where
      (p, q) = primes

C#

  ///<summary>法を生成する</summary>
  ///<param name="primes">二つの素数</param>
  ///<returns>法</returns>
  public static long GenN(long[] primes)
  {
    long p = primes[0];
    long q = primes[1];
    return p * q;
  }

　Haskell を見ると、

  genN :: (Integer, Integer) -> Integer

という謎の記述があります。
　これは C言語でいうプロトタイプ宣言のようなもので、引数と戻り値の型を明示しています。*6
　読み方は、

genN 関数は (Integer, Integer) から Integer を作る

あたりでいいと思います。
　(Integer, Integer) は Tuple（タプル）といい、複数の値をセットにして扱いたい場合に使う型です。
　要素数は任意で型も好きな型をセットにできますが、必ず固定長でなければなりません。
　これを頭に入れて読んでみると、
\begin{align*} f:{T}→{S} \end{align*} などの記法と似ていて直観的ですね！

　次に具体的な実装を。

  genN primes = p * q

　Hakell の関数は、変数へ式を束縛するといった考え方であるため、左辺に関数名（変数名）と引数を半角スペースで区切って、右辺に計算の定義を書きます。
　この時、他言語でよくある引数を囲む丸括弧はありません。
　つまりこの式は、

genN 関数は、primes を受け取って p と q を乗じた結果を返す。

と読めます。
　この p と q とは何者でしょうか？

　この続きを見てみると、

      where  
        (p, q) = primes

と、p, q に関する定義っぽいがあります。
　この where 句は、関数内でのみ使える変数や関数を定義できます。
　関数内のみから見えるブロックであるというイメージで多分大体あっています。

　その下では、タプルをばらして束縛することで中身を取り出してます。
　こうすることで、p と q を別々の変数として扱うことができるようになります。

　つなげて読んでみると、

関数 genN は、primes を受け取って p と q を乗じた結果を返す。
ただし、p は primes の先頭要素、 q は primes の第二要素である。

あたりが語順及び意味的にしっくりくると思います。

　一応 C# との比較もしてみます。

　C# では、"{}" を使って関数用のブロックを準備していますね。
　言葉にすると、

p へ primes[0] を代入する。次に q へ primes[1] を代入する。  
返すのは、 p と q を乗じた結果である。

となり、手続的な定義方法であることがわかります。

genPhiN

Haskell

  -------------------------------------------
  --    φ(n) = lcm(p - 1, q - 1)
  -------------------------------------------
  genPhiN :: (Integer, Integer) -> Integer
  genPhiN (p, q) = lcm (p - 1) (q - 1)

C#

  ///<summary>φ(n)を生成する</summary>
  ///<param name="p">素数</param>
  ///<param name="q">pと異なる素数</param>
  ///<returns>φ(n)</returns>
  public static long GenPhiN(long p, long q)
  {
    long gcd = Multiplication.GcdEx(p - 1, q - 1)[0];
    return (p - 1) * (q - 1) / gcd;
  }

　さっきは説明のために回りくどい書き方をしましたが、今度は素直な実装です。
　まずは Haskell から見ます。
　これ以降は、注目するべきことがない場合は関数宣言について触れません。

  genPhiN (p, q) = lcm (p - 1) (q - 1)

　lcm 関数を呼び出していますが、この関数は整数型を二つ渡すとその最小公倍数を求めて返してくれます。
　標準で準備されていたのでこれをそのまま使い、結果を返すだけですね。

　さっきと違うのはタプルの受け取り方。
　タプルはわざわざ where 句の中で展開する必要はなく、展開した状態で扱いたいのであればこのような書き方が楽です。

　次に C# を見てみます。

    long gcd = Multiplication.GcdEx(p - 1, q - 1)[0];
    return (p - 1) * (q - 1) / gcd;

　こちらは、標準では最小公倍数を求める関数が準備されていないため、自分で実装しています。
　ここで呼び出されている GcdEx 関数は後で作る関数で、今は最大公約数を得る関数だと思ってください。
　ここで最小公倍数 lcm(n, m) は、最大公約数 gcd(n, m) を用いて

\begin{align*} lcm(n, m)=\frac{nm}{gcd(n, m)} \end{align*}

と表すことができましたね！
　これと同じことを行っているだけです。
　ただ、これはライブラリに準備されていなかった*7だけの話であり、想定している言語の使用用途が違うだけであり、考え方の違いとは言えないですね。。。

考察

　genPhiN 関数からは面白い差は見当たりませんでしたが、genN 関数では言語間での思想の違いを見つけることができたと思います。

　Haskell では、
　　どんな値が返ってくるのか
に着目して定義する対し、C# では、
　　どうやって値が返ってくるのか
に着目していると考えられます。

　ここで、後からソースを読み返す時を考えてみてください。
　Haskell の場合は、どんな値が返ってくるかを先に教えてもらい*8、付随する情報を必要に応じて階層的に読んでいくといった手順で関数を読むことができます。
　C# の場合は、先頭から最後まで読まなければその戻り値が何を意味するかが分かりません。
　だから、Haskell は C# に対して、関数単位では可読性が高い言語であるといえるかなぁと思います。

　ただし、C# の手続的な定義方法を否定しているわけではなくて、そもそも Haskell には参照透過性という重たい制約があります。
　これのおかげで、関数内は値を加工する以外の処理はないという前提のもとにソースを読むことができるだけです。
　これに対し C# では、インスタンスのフィールドやメソッドにアクセスする可能性があります*9。
　そのため、着目しなければならない対象が戻り値だけでないので手続を全て把握しなければなりません。
　そういった前提で作られているため、C# では処理を順番に定義していく方法が合っているんだと感じました。

おわりに

　今回のエントリを書いていて、文法は言語の思想を顕著に表すものなのだと改めて実感できました。
　また、新しい言語に触れるという行為は、自分が使うすべての言語に対して理解が深まるとこちらも再確認できました。
　みなさんも、怖がらず積極的に新しい言語に触れてみてください。
　プログラミング言語は怖くないです、友達です！！

参考

7shi様(2015) Haskell 超入門 - Qiita

　学習の際にちょこちょこお世話になってます。
　基本的なことが丁寧にまとめられており、例も多くてわかりやすいです。

rikunora様(2012) ＲＳＡのひ・み・つ - 小人さんの妄想

　RSA暗号について記述されていますが、特にオイラーの定理についてで参考とさせて頂きました。
　φ(n)が最小公倍数でいい理由が納得できました。

あくあのーと様(2014) はてなブログで高速に記事を書けるMarkdown記法チートシート - No Hack No Life

　Markdown について参考にさせて頂きました。
　HTML との対応も書かれており、CSSを適用したいときにどのタグを使うと行けそうか判断しやすかったです。
　ちなみに前まではこれの 見たままモード を使っていました。

xxxx7様(2015) Easy Copy MathJax

　LaTeX での記述方法について参考にさせていただきました。
　綺麗にまとめられており見やすいです。

*1:言い換えると、関数は状態を持たないとも言える。

*2:変わらないから変数っていうのはおかしいと感じるかもしれない。
　だが、評価されるまで値が定まらない数であるため変数と呼ばせてもらう。

*3:先頭の単語を小文字にしてそれ以降の単語は大文字とする記法。 (ex) fooBar

*4:全ての単語は小文字で、単語間を '_' (アンダースコア)で区切る記法。 (ex) foo_bar

*5:先頭の単語から大文字で、それ以降も大文字とする記法。 (ex) FooBar

*6:Haskell では引数と戻り値の型が自明である場合は型推論されるため、基本的にこの宣言は不要である。
　だが、学習中は型を意識したいためなるべく明示する。

*7:.Net 4.0から多倍長整数型である System.Numeric.BigInteger 構造体が実装された。
　この中には、GreatestCommonDivisor メソッドが定義されている。

*8:関数定義の手前で定義する let 句も存在する。
　しかし、こちらを用いても定義と関数が行う計算を区別していることに変わりはない。

*9:というか、アクセスしないならクラスメソッドにして欲しい。

Haskellの勉強 その1

Haskell 暗号 学習の足跡

はじめに

　Haskell の勉強記録を書いていこうとして、熱中して気づけば5時間ほど書いていたのですが、なんというか、すごく長くなってしまいました！！

　これではいかんと思い、もともと分割するつもりでは書いていましたがさらに細かく分割することにしました。

　でも、分割しすぎると何のための関数を書いているのかわからなくなるため、このエントリで全体を俯瞰的に示したいと思います。

RSA暗号を扱うために必要な機能

  • 鍵生成
  • 暗号化
  • 復号

 　ただし、鍵生成は元となる二つの素数 p, q 及び公開鍵である e を渡されるものとする。

各機能で行う処理

鍵生成

　法となる n の計算

　φ(n) の計算

　秘密鍵 d の生成

　対となる鍵のペアを生成

暗号化・復号

　暗号化

　復号

　冪乗の計算

処理に対応する関数名とその内容

鍵生成

　法となる整数 n の計算 : genN

　　RSA暗号は、数字を割った余りの世界（剰余類）での話となります。

　　この時の割る数を "法" と呼びます。

　　法 n の世界で考えたいときは、式の右端に (mod n) と書きます。

　　また、この世界では左辺と右辺の値が等しくても、本当に等しいかわかりません。

　　なので等号記号 "=" の変わりに合同記号 "≡" を使います。

　　　(左辺) ≡ (右辺)          (mod n)

　　のように書きます。

　　単に a を b で割った余り r を求めたいだけの場合は、

　　　r = a mod b

　　と書きます。

　φ(n) の計算 : genPhiN

　　φ(n) はオイラーのトーシェント関数といい、その定義は

　　　1 ～ n - 1 の範囲で n と互いに素であるものの個数を数える

　　というものです。

　　RSA暗号の基盤となっている "オイラーの定理" で重要な数字となります。

　　大雑把なイメージとしては、

　　　条件付き*1だけど冪乗に周期性があって一周*2したら元の数字に戻るんだなぁ

　　くらいに思ってもらえると十分です！

　秘密鍵 d の生成 : genD, gcdex

　　φ(n) と公開鍵 e  から秘密鍵 d を生成します。

　　平文を e 乗した状態が暗号文、暗号文を d 乗したら一周して平文に戻ります。

　　e と d と φ(n) の関係は

　　　e × d ≡ 1          (mod φ(n))

　　　　割った余りの世界へ、割ってなくなった数を足すと元に戻るので、

　　　　以下のような整数 m が存在するはず

　　　e × d + φ(n) × m = 1

　　となります。

　　ここで、 gcdex は拡張ユークリッドの互除法を実装した関数です。

　　これは整数 a, b の最大公約数 gcd 及び

　　　a × x + b × y = gcd

　　を満たす最小の x, y を求めることができる方法です。

　　　a = e, x = d, b = φ(n), m = y, gcd = 1

　　としてやると変形した式がこの形となるため、これより d を求めるわけです。

　対となる鍵のペアを生成 : genKeyPair

　　これは元から与えられている公開鍵と上で生成した秘密鍵、法となる n を

　　セットにして返すだけの関数です。

　　プログラムとしてはこの関数だけを公開して鍵生成処理への入口とします。

 暗号化・復号

　暗号化 : ecrypt

　　公開鍵 e と法 n を使って暗号化します。

　　やることは平文を法 n の世界で e 乗するだけです。

　復号 : decrypt

　　秘密鍵 d と法 n を使って復号します。

　　やることは暗号文を法 n の世界で n 乗するだけです。

　冪状の計算 : power

　　法 n の世界での冪乗を行います。

おわりに

　これ書くだけでも結構な量になった！

　前のエントリでRSA暗号の説明はしないって書いたけど、結局何やってるかわかんなかったらソースが読めないと思って概要と計算手順だけでも書いたらこうなりました。

　気を取り直して明日からこそプログラム書いていきます。

　Haskell の文法とかも書いた方がいいかなぁって思ったけど、実際のコードと比べながらの方がわかりやすいと思ったので、少なくともここには書かずに別エントリとします。

参考

　参考を書こうか考えたけど、各関数実装時に張った方がよさそうなのでここでは無とします。

*1:底と法が互いに素であることが条件

*2:一周でなくても整数周であればよい

Haskellの勉強 その0

Haskell 暗号 学習の足跡

はじめに

　関数型プログラミング言語であるHaskellを最近勉強してます。

　動機としては、圏論と関数型プログラミング言語の関係を聞いて、そういえば関数型の言語ってやったことなかったなーって思ったから。

　手続型の言語しか触ったことがなかったので考え方がまるで違ってギャップが楽しい毎日です。

学習目的

　・関数型プログラミングの思想を雰囲気だけでもつかみ、思考の幅を広げる

　・圏論の基礎を身に着ける

学習方法

　とりあえずの学習方法としては、RSA暗号をさくっとべたべたな方法で実装した後に、Haskellらしい概念を取り入れていく方法でやります。

　RSA暗号を題材に選んだ理由はいくつかあって、一つ目がCTFやってたおかげでRubyやらC#で実装したことがあるため、手続型との対比を行いやすいため。

　二つ目が、ぱっと思いついた処理の中で、処理が短い割に数式を処理に落とし込むことが多いため。

　三つ目が、RSA暗号は平文空間と暗号文空間が乗法について準同型であるため、圏論が根っこにあるHaskellでは何か面白いことができるかもと思ったため。

 

 おわりに

　大体こんな感じ！

　RSA暗号について深く書くつもりはないので、気になる方はwikipedia先生とか参考のURLをのぞいてみてください。

参考

まいとう情報通信研究会(2003) はじめに | サルにも分かるRSA暗号

　初めてRSA暗号と出会った直後にお世話になったサイトです。

　前提知識がほとんど必要なく、頑張れば中学生でも雰囲気をつかむことができます。

神戸大学 高橋真研究室(2015) RSA暗号

　RSA暗号を実装するとき、計算結果が正しいかの答え合わせをここで行ってます。

　説明も簡潔で分かりやすく、試しながら学べて参考になると思います。