C#で Project Euler P5
問題
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
Problem 5 - PukiWiki
解答
P5.cs
using System; public static class P5 { [STAThread] public static void Main() { Console.WriteLine(Calc()); } private static ulong Calc() { ulong res = 1; for(ulong num = 1; num <= 20; num++) { res = res * num / MyMath.EuclideanAlgorithem(res, num); } return res; } }
MyMath
public static class MyMath { // O(log n) public static ulong ModPow(ulong n, ulong p, ulong m) { ulong res = 1; for(; p > 0; p >>= 1) { res = (p & 1) == 1 ? res * n % m : res; n = (n * n) % m; } return res; } // O(log n) public static ulong EuclideanAlgorithem(ulong a, ulong b) { ulong work; while(b != 0) { work = b; b = a % b; a = work; } return a; } }
計算量 $O(n\log n)$
最大公約数から最小公倍数を求めていって掛け合わせるだけ。
C#で Project Euler P4
問題
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.
Problem 4 - PukiWiki
解答
using System; public static class P4 { public static void Main() { Console.WriteLine(Calc()); } private static long Calc() { int ret = 0; for(int i = 999; i > 100; i--) { for(int j = 999; j > 100; j--) { string s = (i * j).ToString(); Console.WriteLine(i * j); if(IsRenum(i * j)) { Console.WriteLine(i + ", " + j); ret = i * j; goto End; } } } End: return ret; } private static bool IsRenum(int num) { var re = 0; for(var work = num; work > 0; work /= 10) { re = re * 10 + work % 10; } return re == num; } }
計算量 $O(n^2\log n)$
やり方が思い付かなかったので愚直に総当たりしました。
回文数の性質を調べればもっと計算量抑えられそう。
調べてないけど、直観的に11の倍数になりそうな気はする?
C#で Project Euler P3
はじめに
P2はフィボナッチ数列の級数に関する問題だけど、問題に魅力を感じなかったので飛ばしました。
で、僕としては好みなP3をやります。
そういや問題には直接関係ないけど、C#って末尾再帰の最適化してくれないのね。。。
再帰的に書こうと思ってたけど再帰はなるべく減らしてます。
問題
Problem 3 「最大の素因数」
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
Problem 3 - PukiWiki解答
P3.cs
using System; public static class P3 { public static void Main() { Console.WriteLine(Calc()); } private static ulong Calc() { ulong n = 600851475143; ulong index; for(index = 0; n != 1; index++) { while(n % PrimeGenerator.GetPrime(index) == 0) { n /= PrimeGenerator.GetPrime(index); } } return PrimeGenerator.GetPrime(index - 1); } }
PrimeGenerator
using System; using System.Linq; using System.Collections.Generic; public static class PrimeGenerator { private static ulong primeIndex; // 素数の添え字 private static ulong primeCounter; // 素数を探すために回すカウンタ private static readonly Predicate<ulong> TryDivision; // 試し割りを行うデリゲート private static Dictionary<ulong, ulong> primeList = new Dictionary<ulong, ulong>(); // 見つけた素数をバッファする空間 // 初期化 static PrimeGenerator() { primeList.Add(0, 2); // 2の登録 primeIndex = 1; primeCounter = 1; ulong multi = 1; // 素数の積、偶数はとばす為2は登録しない while(primeIndex < 10) { while(MyMath.EuclideanAlgorithem(primeCounter += 2, multi) != 1){ } primeList.Add(primeIndex++, primeCounter); multi *= primeCounter; } // 試し割りの登録、素数の積との最大公約数が1であるかで判定する TryDivision = n => MyMath.EuclideanAlgorithem(multi, n) == 1; } // 指定した添え字の素数を取得する public static ulong GetPrime(ulong idx) { while(primeIndex <= idx) { while(!PrimeTest(primeCounter += 2)){ } primeList.Add(primeIndex++, primeCounter); } return primeList[idx]; } // 素数判定を行う private static bool PrimeTest(ulong n) { // 試し割り、O(log n) if(!TryDivision(n)) { return false; } // フェルマーテスト、O(log n) if(MyMath.ModPow(2, n - 1, n) != 1) { return false; } // ミラーラビンテスト、O(m * (log n)^2) if(!MillerRabinTest(n)) { return false; } // 全てのテストに合格 return true; } private const int BigIntegersTestCount = 15; // 大きな素数判定の時は適当に15回くらいテストする private static readonly ulong[] MRTestPattern4759123141 = new ulong[]{ 2, 7 , 61 }; private static readonly ulong[] MRTestPattern341550071728321 = new ulong[]{ 2, 3, 5, 7, 11, 13, 17 }; // ミラーラビンテスト private static bool MillerRabinTest(ulong n) { // テストパターンの選択 IEnumerable<ulong> testPattern = MRTestPattern4759123141; if(n < 4759123141) { // 初期化で代入した為処理なし } else if(n < 341550071728321) { testPattern = MRTestPattern341550071728321; } else { // これより大きい数字のテストパターンを知らないので // 適当な素数を乱択する testPattern = GetRandomTestPattern().Take(BigIntegersTestCount); } // 全てのパターンでテストする foreach(var testNum in testPattern) { if(testNum >= n) { break; } if(!MillerRabinTestSub(n, testNum)) { return false; } } return true; } private static Random rnd = new Random(); static List<ulong> usedPrimes = new List<ulong>(); // 素数を乱択して返すシーケンス private static IEnumerable<ulong> GetRandomTestPattern() { usedPrimes.Clear(); ulong index; while(true) { index = (ulong)rnd.Next(primeList.Count); if(usedPrimes.Contains(index)) { continue; } usedPrimes.Add(index); yield return primeList[index]; } } // ミラーラビンテストを実際に行う private static bool MillerRabinTestSub(ulong n, ulong a) { ulong m1 = n - 1; // n - 1 // n - 1 を r * d へ分解、ただし r = 2^s, d ≡ 1 (mod 2) ulong r = m1 & (~m1 + 1); // 2のべき乗要素 ulong d = m1 / r; // 奇数要素 ulong pow2 = 0; ulong mp = MyMath.ModPow(a, d, n); // 2の0乗で 1 または -1 の場合は合格 if(mp == 1 || mp == m1) { return true; } for(pow2 = 1; pow2 <= r; pow2 <<= 1) { mp = MyMath.ModPow(a, pow2 * d, n); // 1 より先に -1 が出た場合は合格 if(mp == m1) { return true; } // 1 が -1 より先に出た場合は不合格 if(mp == 1) { return false; } } // 合格して抜けなければ不合格 return false; } public static IEnumerable<ulong> GetPrimeList() { ulong index = 0; while(true) { yield return GetPrime(index); index++; } } public static IEnumerable<ulong> GetPrimeList(Func<ulong, ulong, bool> predicator) { for(ulong index = 0; predicator(index, GetPrime(index)); index++) { yield return GetPrime(index); } } }
MyMath.cs
public static class MyMath { // O(log n) public static ulong ModPow(ulong n, ulong p, ulong m) { ulong res = 1; for(; p > 0; p >>= 1) { res = (p & 1) == 1 ? res * n % m : res; n = (n * n) % m; } return res; } // O(log n) public static ulong EuclideanAlgorithem(ulong a, ulong b) { ulong work; while(b != 0) { work = b; b = a % b; a = work; } return a; } }
計算量 $O(m\varphi(n)(\log n)^2)$
ただし、m はミラーラビンテストのテストパターン数、φはオイラーのトーシェント関数。
計算量あってるか怪しいけど多分これくらい!
計算量でφ関数とか見たことないけどこうとしか書けなかった。
最大の素因数を求めるということで、素直に素因数分解した。
総当たりの計算量$O(\sqrt{n})$くらいになるのかな?に比べればφ関数で母数をぐっと減らせるから速いと思う。
↑違いました、素因数でない素数の判定も行っているので$O(\sqrt{n}m(\log n)^2)$。
下限を出そうと思ったけどある自然数以下の素数を数える方法がわからずに表現できませんでした。。。
でも、使う素数の範囲があらかじめわかるので、素数判定するよりもエラトステネスの篩で素数表を作った方が速いかも。
C#で Project Euler P1
はじめに
暇だったのでやってみた。
本家 : About - Project Euler
日本語: Project Euler - PukiWiki
テンプレート
using System; public static class P { public static void Main() { Console.WriteLine(Calc()); } private static int Calc() { } }
これに対し、クラス名に問題番号を付けてCalcメソッドを実装する形でやっていこうと思います。
また、問題も載せますが日本語訳された方から引用します。
問題
Problem 1 「3と5の倍数」
10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.
Problem 1 - PukiWiki
解答
using System; public static class P1 { [STAThread] public static void Main() { Console.WriteLine(Calc()); } private static int Calc() { return Sum(3) + Sum(5) - Sum(3 * 5); } private static int Sum(int n) { var m = (1000 - 1) / n; return (n * (1 + m)) * m / 2; } }
計算量 O(1)
3の倍数と5の倍数それぞれの総和から重複してるところを引く。
等差数列なので繰り返しなしで求められる。
C# VSで埋め込んだリソースの場所
わからなくてはまったのでメモ
<プロジェクトの名前空間>.<リソースを追加したときに格納されるフォルダ、デフォルトで"Resources">.<追加したリソースのファイル名>
にあった。
調べ方はこんな感じ。
var asm = System.Reflection.Assembly.GetExecutingAssembly(); var resources = asm.GetManifestResourceNames(); foreach(var resource in resources) { System.Console.WriteLine(resource); }
色々調べまわってはまったけども、素直にMSDN見るのが一番と学べた。
コード : アセンブリでのリソース名の検索 (Visual C#)
あと、ソリューションエクスプローラの階層ってそのまま名前空間になってそう。
ソリューションに依存しないけどdllにするには大げさなモジュールとかどうやって扱ってるんだろうみんな。
C# EventArgsの継承とかイベントのnullチェックがめんどくさい
のでこんな拡張メソッド作ってみた、便利。
using System; ///<summary>汎用のEventArgsを生成するためのクラス</summary> public static class GenericEventArgs { public static GenericEventArgs<TArg> Create<TArg>(TArg arg) { return new GenericEventArgs<TArg>(arg); } } ///<summary>汎用のEventArgs</summary> ///<remarks>EventArgsを継承して指定された型の値を持つだけ</remarks> public class GenericEventArgs<TArg> : EventArgs { public TArg Value{ get; private set; } public GenericEventArgs(TArg arg) { this.Value = arg; } } ///<summary>デリゲートに関する拡張メソッド定義用クラス</summary> public static class DelegateExtensionMethods { ///<summary>素直なイベントハンラ型デリゲートの実行</summary> public static void Run( this EventHandler handler, object sender, EventArgs e ){ if(handler != null) { handler(sender, e); } } ///<summary>汎用イベントハンドラ型デリゲートの実行</summary> public static void Run<TEventArgs>( this EventHandler<TEventArgs> handler, object sender, TEventArgs e ) where TEventArgs : EventArgs { if(handler != null) { handler(sender, e); } } ///<summary>汎用EventArgsを用い、引数を生で渡して実行</summary> ///<remarks>EventArgsを継承するのが面倒で横着したいときに使う</remakrs> public static void Run<TArg>( this EventHandler<GenericEventArgs<TArg>> handler, object sender, TArg e ){ handler.Run(sender, GenericEventArgs.Create(e)); } }
使い方はこんな感じ。
using System; public class MainApp { [STAThread] public static void Main() { var eventRaiser = new EventRaiser(); Console.WriteLine("イベント未登録時にイベント発行"); eventRaiser.OnEvent("hoge"); Console.WriteLine("イベント登録"); eventRaiser.Event += (sender, e) => Console.WriteLine(e.Value); Console.WriteLine("イベント登録後にイベント発行"); eventRaiser.OnEvent("fuga"); } } public class EventRaiser { public event EventHandler<GenericEventArgs<string>> Event; public void OnEvent(GenericEventArgs<string> e) { this.Event.Run(this, e); } public void OnEvent(string e) { this.Event.Run(this, e); } }
結果はこんな感じ。
イベント未登録時にイベント発行 イベント登録 イベント登録後にイベント発行 fuga 続行するには何かキーを押してください . . .
きっちり落ちずに流してくれる!
ちょー便利!!
C# ジェネリックメソッドの定義がえぐい
はじめに
C# 続・メソッドチェーンしたくて仕方なかった - さんぽみち とかで使いたい処理が
いっぱい出てきて、作ってた時に思ったメソッド達を作ってたら見た目がひどいものができました。
なのでそれを乗っけてみます。
成果物
まずはこちら。
HighOrderFunctions.cs
namespace HighOrderFunctions { namespace ExtentionMethods { public static class HighOrderFunctionsExtentionMethods { ///<summary>定数を定数メソッドへ変換する拡張メソッド</summary> ///<param name="a1">定数</param> ///<returns>a1を返す定数メソッド</returns> public static Func<T> ToFunc<T>(this T a){ return () => a; } // デリゲートへの部分適用、とりあえず7引数まで public static Func<T2> Apply<T1, T2>(this Func<T1, T2> f, T1 a1) { return () => f(a1); } public static Func<T2, T3> Apply<T1, T2, T3>(this Func<T1, T2, T3> f, T1 a1) { return a2 => f(a1, a2); } public static Func<T2, T3, T4> Apply<T1, T2, T3, T4>(this Func<T1, T2, T3, T4> f, T1 a1) { return (a2, a3) => f(a1, a2, a3); } public static Func<T2, T3, T4, T5> Apply<T1, T2, T3, T4, T5>(this Func<T1, T2, T3, T4, T5> f, T1 a1) { return (a2, a3, a4) => f(a1, a2, a3, a4); } public static Func<T2, T3, T4, T5, T6> Apply<T1, T2, T3, T4, T5, T6>(this Func<T1, T2, T3, T4, T5, T6> f, T1 a1) { return (a2, a3, a4, a5) => f(a1, a2, a3, a4, a5); } public static Func<T2, T3, T4, T5, T6, T7> Apply<T1, T2, T3, T4, T5, T6, T7>(this Func<T1, T2, T3, T4, T5, T6, T7> f, T1 a1) { return (a2, a3, a4, a5, a6) => f(a1, a2, a3, a4, a5, a6); } // デリゲートのカリー化、とりあえず7引数まで public static Func<T1,Func<T2, T3>> Curry<T1, T2, T3>(this Func<T1, T2, T3> f) { return a1 => f.Apply(a1); } public static Func<T1, Func<T2, Func<T3, T4>>> Curry<T1, T2, T3, T4>(this Func<T1, T2, T3, T4> f) { return a1 => a2 => f.Apply(a1).Apply(a2); } public static Func<T1, Func<T2, Func<T3, Func<T4, T5>>>> Curry<T1, T2, T3, T4, T5>(this Func<T1, T2, T3, T4, T5> f) { return a1 => a2 => a3 => f.Apply(a1).Apply(a2).Apply(a3); } public static Func<T1, Func<T2, Func<T3, Func<T4, Func<T5, T6>>>>> Curry<T1, T2, T3, T4, T5, T6>(this Func<T1, T2, T3, T4, T5, T6> f) { return a1 => a2 => a3 => a4 => f.Apply(a1).Apply(a2).Apply(a3).Apply(a4); } public static Func<T1, Func<T2, Func<T3, Func<T4, Func<T5, Func<T6, T7>>>>>> Curry<T1, T2, T3, T4, T5, T6, T7>(this Func<T1, T2, T3, T4, T5, T6, T7> f) { return a1 => a2 => a3 => a4 => a5 => f.Apply(a1).Apply(a2).Apply(a3).Apply(a4).Apply(a5); } // 関数の実行を遅延させる public static Func<T2> Delay<T1, T2>(this Func<T1, T2> f, T1 a1) { return () => f(a1); } public static Func<T3> Delay<T1, T2, T3>(this Func<T1, T2, T3> f, T1 a1, T2 a2) { return () => f(a1, a2); } public static Func<T4> Delay<T1, T2, T3, T4>(this Func<T1, T2, T3, T4> f, T1 a1, T2 a2, T3 a3) { return () => f(a1, a2, a3); } public static Func<T5> Delay<T1, T2, T3, T4, T5>(this Func<T1, T2, T3, T4, T5> f, T1 a1, T2 a2, T3 a3, T4 a4) { return () => f(a1, a2, a3, a4); } public static Func<T6> Delay<T1, T2, T3, T4, T5, T6>(this Func<T1, T2, T3, T4, T5, T6> f, T1 a1, T2 a2, T3 a3, T4 a4, T5 a5) { return () => f(a1, a2, a3, a4, a5); } public static Func<T7> Delay<T1, T2, T3, T4, T5, T6, T7>(this Func<T1, T2, T3, T4, T5, T6, T7> f, T1 a1, T2 a2, T3 a3, T4 a4, T5 a5, T6 a6) { return () => f(a1, a2, a3, a4, a5, a6); } public static Action Delay<T>(this Action<T> f, T a) { return () => f(a); } public static Action Delay<T1, T2>(this Action<T1, T2> f, T1 a1, T2 a2) { return () => f(a1, a2); } public static Action Delay<T1, T2, T3>(this Action<T1, T2, T3> f, T1 a1, T2 a2, T3 a3) { return () => f(a1, a2, a3); } public static Action Delay<T1, T2, T3, T4>(this Action<T1, T2, T3, T4> f, T1 a1, T2 a2, T3 a3, T4 a4) { return () => f(a1, a2, a3, a4); } public static Action Delay<T1, T2, T3, T4, T5>(this Action<T1, T2, T3, T4, T5> f, T1 a1, T2 a2, T3 a3, T4 a4, T5 a5) { return () => f(a1, a2, a3, a4, a5); } public static Action Delay<T1, T2, T3, T4, T5, T6>(this Action<T1, T2, T3, T4, T5, T6> f, T1 a1, T2 a2, T3 a3, T4 a4, T5 a5, T6 a6) { return () => f(a1, a2, a3, a4, a5, a6); } public static Action Delay<T1, T2, T3, T4, T5, T6, T7>(this Action<T1, T2, T3, T4, T5, T6, T7> f, T1 a1, T2 a2, T3 a3, T4 a4, T5 a5, T6 a6, T7 a7) { return () => f(a1, a2, a3, a4, a5, a6, a7); } } } }
…次にこちら。
TupleExtention.cs
using System; namespace TupleExtention { namespace ExtentionMethods { public static class TupleExtentionMethods { // タプルのパターンマッチング public static Tuple<T1, T2> Match<T1, T2>( this Tuple<T1, T2> t, out T1 a1, out T2 a2 ){ a1 = t.Item1; a2 = t.Item2; return t; } public static Tuple<T1, T2, T3> Match<T1, T2, T3>( this Tuple<T1, T2, T3> t, out T1 a1, out T2 a2, out T3 a3 ){ a1 = t.Item1; a2 = t.Item2; a3 = t.Item3; return t; } public static Tuple<T1, T2, T3, T4> Match<T1, T2, T3, T4>( this Tuple<T1, T2, T3, T4> t, out T1 a1, out T2 a2, out T3 a3, out T4 a4 ){ a1 = t.Item1; a2 = t.Item2; a3 = t.Item3; a4 = t.Item4; return t; } public static Tuple<T1, T2, T3, T4, T5> Match<T1, T2, T3, T4, T5>( this Tuple<T1, T2, T3, T4, T5> t, out T1 a1, out T2 a2, out T3 a3, out T4 a4, out T5 a5 ){ a1 = t.Item1; a2 = t.Item2; a3 = t.Item3; a4 = t.Item4; a5 = t.Item5; return t; } public static Tuple<T1, T2, T3, T4, T5, T6> Match<T1, T2, T3, T4, T5, T6>( this Tuple<T1, T2, T3, T4, T5, T6> t, out T1 a1, out T2 a2, out T3 a3, out T4 a4, out T5 a5, out T6 a6 ){ a1 = t.Item1; a2 = t.Item2; a3 = t.Item3; a4 = t.Item4; a5 = t.Item5; a6 = t.Item6; return t; } public static Tuple<T1, T2, T3, T4, T5, T6, T7> Match<T1, T2, T3, T4, T5, T6, T7>( this Tuple<T1, T2, T3, T4, T5, T6, T7> t, out T1 a1, out T2 a2, out T3 a3, out T4 a4, out T5 a5, out T6 a6, out T7 a7 ){ a1 = t.Item1; a2 = t.Item2; a3 = t.Item3; a4 = t.Item4; a5 = t.Item5; a6 = t.Item6; a7 = t.Item7; return t; } } } }
C#でのジェネリックに関するメソッド定義は饒舌し難いほどにやりづらいです!!!
これのテストとか絶対やりたくないです。
標準ライブラリでこれくらいなら定義しておいてくれてもいいのに…
そして実装が終わった後の追い打ちがこれ。
using System; using HighOrderFunctions.ExtentionMethods; class MainApp { [STAThread] public static void Main() { // var sumCurry = Add.Curry(); // <=一番やりたかった形がコンパイルエラー // var sumCurry = // // HighOrderFunctionsExtentionMethods // <=すなわちこれもコンパイルエラー // .Curry(Add); // // var add = Add; // <=これがダメなのが致命的 var sumCurry = ((Func<int, int, int, int>)Add).Curry(); // <=これならOK sumCurry = // HighOrderFunctionsExtentionMethods // <=つまりこれもOK .Curry((Func<int, int, int, int>)Add); // Func<int, int, int, int> add = Add; // <=ということは sumCurry = add.Curry(); // <=これもOK Console.WriteLine(sumCurry(1)(2)(3)); // => 6 } public static int Add(int a, int b, int c) { return a + b + c; } }
使うときもめんどくさい。。。
オーバーロードの兼ね合いがあってメソッドはメソッドグループとして扱われてるのが
問題っぽいと推測。
メソッドグループのインスタンスを変数に落とすことができて、かつメソッドグループから
どのオーバーロードかを選択することができれば解決しそうなのになぁ。
C#6.0ではメソッドをラムダ式で定義できるらしいので、環境ある人はこれができるか
やってみてほしい(丸投げ
一応解説
このままじゃ愚痴だけになっちゃうので、軽くだけ説明を。
Func<T1, T2, .T3, .. , TResult> を使い慣れていない方は、先頭から順にカンマを
接続詞の "と" に置き換えながら読み、最後のカンマだけ "から" と読み、
後ろに "へ変換するデリゲート" とつけて読んでみてください。
つまり、型引数が四つなら "T1 と T2 と T3 からTResult へ変換するデリゲート" となります。
ピンと来てくれればいいなぁ。
Applyメソッド
デリゲートへ部分適用してくれるメソッドです。
例えば、今回のAddメソッドでは Func<int, int, int, int> の形をしたメソッドですね。
これを、第一引数をあらかじめ与えて固定することで Func<int, int, int> に
変換することを部分適用と言います。
やってることのイメージはこんな感じ。
int Add(int a, int b, int c) // 最初は引数三つ { return a + b + c; } // ここへaに1を渡して固定したい // イメージ int Add(int b, int c) // 引数は二つで { static int a = 1; return a + b + c; } // 前に渡した1を覚えておきたい // C#で正しく書くと Func<int, int, int> AddApply(int a) // 返すのはデリゲート { return (x, y) => Add(a, x, y); } // クロージャがaを覚えていてくれる // 使ってみると Func<int, int, int> addAppied = Add(1); // (x, y) => 1 + x + y となる int result = addApplied(2, 3); // (2, 3) => 1 + 2 + 3 となるイメージ
身につくとかゆいところに手が届いて便利です。
Curryメソッド
カリー(Curry)化してくれるメソッドです。
こちらもAddメソッドを使って説明すると、Func<int, int, int, int> から
Func<int, Func<int, Func<int, int>>> のような
形に変換することをカリー化と呼びます。おいしそうです。
どういうことかというと、上の例であれば、Func<int, int> の形を T と置くと
Func<int, Func<int, T>>
Func<int, T> を U と置くと
Func<int, U>
という形をしており、常に引数が一つのメソッドとなっています。
元の引数をもっと増やしてみて
Func<int, int ,int, int, int, int, int>
をカリー化すると
Func<int, Func<int, Func<int, Func<int, Func<int, int>>>>>
という形になりますが、どの段階のメソッドを見ても引数が一つになっています。
これで嬉しいのが、先ほどの部分適用を考えたときです。
Func<int, int, int, int>> へ値を渡すと Func<int, Func<int, Func<int, int>>> が返ってきて、
さっきの部分適用と同等なものが実現できています。
逆に言い換えると、カリー化されたメソッドは実行時に部分適用を繰り返して
元のメソッドと等価な演算を行っているともいえます。
また、ジェネリック型のメソッドを設計するときにも嬉しいことがあります。
それは、引数が常に2つであると考えられることです。
メソッドをデリゲートとして考えると、メソッドのシグネチャはそのまま型と解釈できます。
そもそも今説明で使っている Func<T, TResult> は、標準ライブラリに定義されている
汎用デリゲートですね。
ジェネリック型のメソッドを考えるとき、型は何でもいいけど引数が可変では困ります。
今回書いたような泥臭くめんどうな定義をたくさんしなくてはなりません。
しかし、メソッドがカリー化されている前提で考えると、メソッドの引数が2つだけの
場合を考えるだけでよくなります。
こちらもAddを使って実際に行ってみます。
int Add(int a, int b, int c) // 最初は引数三つ { return a + b + c; } // bとcを受け取るタイミングをずらしたい // イメージ int Add(int a) // 引数は一つで { return ((a + b?) + c!!); } // bを後から受け取りさらにその後にcを受け取りたい // C#で正しく書くと Func<int, Func<int, Func<int, int>>> AddCurry(int a) // 返すのはデリゲートを返すデリゲートで引数ひとつ { return x => y => Add(a, x, y); } // クロージャが(ry // 使ってみると Func<int, Func<int, int>> appliedOnce = Add(1); // x => y => Add(1, x, y) Func<int, int> appliedTwice = appliedOnce(2); // 2 => y => Add(1, 2, y) int result = appliedTwice(3); // 2 => 3 => Add(1, 2, 3)
どの段階でもちゃんと引数が一つになりました!
ラムダ式をネスト?させる部分が綺麗で実装しやすいです。
こんな感じのがカリー化です。
Delayメソッド
いまふとLazyの方がいいかなぁと思いましたがとりあえずDelayメソッドです!
その名の通り遅らせてくれます。
何が遅れるかは、メソッドへ引数を適用して処理させるのを遅らせてくれます。
やっていることは部分適用がわかれば一瞬でわかって、引数が0になるように
部分適用しているだけです。
Addで見てみましょう。
int Add(int a, int b, int c) // 最初は引数三つ { return a + b + c; } // この計算を、引数が与えられた瞬間でなく好きな時にさせたい // イメージ int Add() // 引数はなしで { return (a + c + d); } // aとbとcは前もって渡したい // C#で正しく書くと Func<int> AddDelay(int a, int b, int c) // 返すのは引数なしのデリゲート { return () => a + b + c; } // クロージャが(ry // 使ってみると Func<int> addDelay = AddDelay(1, 2, 3); // () => 1 + 2 + 3 でまだ実行されない int result = addDelay(); // この時点で初めて変数の中身を評価
ちょっとわかりづらいかもですが、引数を渡した段階では中身をのぞいていません。
引数がオブジェクト型でnullを渡したとき、どこでぬるりとなるか想像するとわかりやすいです。
Match
タプルのパターンマッチングをしてくれるメソッドです。
標準で定義されていないからタプルが普及しないのではと思うレベルのものです。
C#7.0には期待しているのでお願いします。。。
やってることは単に値を参照渡ししてタプルの中身を書きだしてくれるだけですね。
使うとこんな感じ。
int n; string s; List<int> l; // 変数宣言 var tuple = Tuple.Create( // タプルの生成 1, "に", new List<int>(new int[]{3}) // Tuple<int, string, List<int>> ); tuple.Match(out n, out s, out l); // さくっと移す Console.WriteLine(n + s + l[0]); // => 1に3
わざわざItem1とかItem2とかでアクセスしなくてよくて楽ちん。
おわりに
ジェネリック型のメソッドは、とにかく定義が非常に面倒で、何に使っていいかも
わかりづらいものだと思います。
それは、オブジェクト指向しているとメソッドの引数は抽象的になるけども
処理自体は具体的なものになりがちだからかなと。
だから引数の型が不定なのにどんな処理を記述すればいいの?ってなるのだと思います。
ですので、一度具体的な実装から離れて構文の中に自分の世界を作ってやる!くらいの気持ちで
フレームワークみたいなのを作ってみるとジェネリックの良さが見えてくるのではと思いました。
個人的には、ジェネリックはコンテナに使うかデリゲートを渡してなんぼだと思います。
ネタでぐちぐち書くだけのつもりでしたが綺麗にまとまったきがします!
それではまたよろしくお願いします。
参考
yohshiy様(2014) C# でのカリー化の使用 | プログラマーズ雑記帳
先日のエントリでも参考に2回使わせていただいたyohshiyさんのエントリです。
僕の大雑把で直観任せの説明よりも丁寧でわかりやすいのでぜひ読んでみてください。
lironi5様(2013) C# のクロージャと部分適用とカリー化 - チラシの裏でプログラミング
さらっと知っている前提のように書いてきたクロージャについて解説されています。
このクロージャで嬉しいことの説明に部分適用とカリー化が引き合いに出されています。
基本的にクロージャさえ押さえておけば部分適用もカリー化も抑えたような物なので必見です。