C#でmap(写像)、foldlとfoldr(畳み込み)、unfold(解きほぐし)とか
※追記しました。2008/12/16
オブ脳寄りの人間なので、どうしても関数型脳に染まりきれないところはあるんですが、
今年Haskellを学んでみて、foldとかunfoldってのは、すっげー便利だなと思いました。
そんなわけで、C#でちょっくらfoldとかunfoldしてみようの巻。
public static class Extentions { /// <summary> /// map(写像) /// </summary> /// <typeparam name="T"></typeparam> /// <typeparam name="TResult"></typeparam> /// <param name="source"></param> /// <param name="func"></param> /// <returns></returns> public static IEnumerable<TResult> Map<T, TResult>(this IEnumerable<T> source, Func<T, TResult> func) { if (source == null) throw new ArgumentNullException("items"); if (func == null) throw new ArgumentNullException("func"); foreach (var item in source) yield return func(item); } /// <summary> /// fold-left(畳み込み左) /// </summary> /// <typeparam name="T"></typeparam> /// <typeparam name="U"></typeparam> /// <param name="source"></param> /// <param name="func"></param> /// <param name="acc"></param> /// <returns></returns> public static T FoldLeft<T, U>(this IEnumerable<U> source, Func<T, U, T> func, T acc) { if (source == null) throw new ArgumentNullException("items"); if (func == null) throw new ArgumentNullException("func"); if (acc == null) throw new ArgumentNullException("acc"); for (int index = 0; index < source.Count<U>(); index++) acc = func(acc, source.ElementAt(index)); return acc; } /// <summary> /// fold-right(畳み込み右) /// </summary> /// <typeparam name="T"></typeparam> /// <typeparam name="U"></typeparam> /// <param name="source"></param> /// <param name="func"></param> /// <param name="acc"></param> /// <returns></returns> public static T FoldRight<T, U>(this IEnumerable<U> source, Func<T, U, T> func, T acc) { if (source == null) throw new ArgumentNullException("items"); if (func == null) throw new ArgumentNullException("func"); if (acc == null) throw new ArgumentNullException("acc"); for (int index = source.Count<U>() - 1; index >= 0; index--) acc = func(acc, source.ElementAt(index)); return acc; } /// <summary> /// filter /// </summary> /// <typeparam name="T"></typeparam> /// <param name="source"></param> /// <param name="func"></param> /// <returns></returns> public static IEnumerable<T> Filter<T>(this IEnumerable<T> source, Predicate<T> func) { if (source == null) throw new ArgumentNullException("items"); if (func == null) throw new ArgumentNullException("func"); foreach (var item in source) if (func(item)) yield return item; } /// <summary> /// IterateIndex /// </summary> /// <typeparam name="T"></typeparam> /// <param name="items"></param> /// <param name="action"></param> public static void IterateIndex<T>(this IEnumerable<T> source, Action<int, T> action) { if (source == null) throw new ArgumentNullException("items"); if (action == null) throw new ArgumentNullException("action"); for (int index = 0; index < source.Count(); index++) action(index, source.ElementAt(index)); } /// <summary> /// unfold(解きほぐし) /// </summary> /// <typeparam name="T"></typeparam> /// <param name="func"></param> /// <param name="init"></param> /// <returns></returns> public static IEnumerable<T> Unfold<T>(this Func<T, T> func, T init) { if (func == null) throw new ArgumentException("func"); if (init == null) yield break; var seed = init; yield return seed; while (true) { seed = func(seed); if (seed == null) yield break; yield return seed; } } /// <summary> /// unfold(解きほぐし) /// </summary> /// <typeparam name="T"></typeparam> /// <param name="func"></param> /// <param name="p"></param> /// <param name="init"></param> /// <returns></returns> public static IEnumerable<T> Unfold<T>(this Func<T, T> func, Predicate<T> p, T init) { if (func == null) throw new ArgumentException("func"); if (p == null) throw new ArgumentException("p"); for (T seed = init; !p(seed); seed = func(seed)) yield return seed; }
たぶん、こんな感じでよいでしょう。
SelectはHaskellで言うところのmap、AggregateはHaskellで言うところのfoldlですね。
あと、一応作ってはみましたが、Predicate
では、さっそく使ってみましょう。
using System; using System.Linq; namespace ConsoleApplication1 { class Program { static void Main() { var list = Enumerable.Range(1, 6); Func<int,int,int> f = (acc, x) => x - acc; // 写像 var map = list.Map( x => x * 2); foreach (var item in map) Console.WriteLine(item); Console.WriteLine(); // Selectは写像 var map2 = list.Select(x => x * 2); foreach (var item in map2) Console.WriteLine(item); Console.WriteLine(); // 畳み込み左 var fl1 = list.FoldLeft(f, 0); Console.WriteLine("fl1:{0}",fl1); Console.WriteLine(); // Aggregateは畳み込み左 var fl2 = list.Aggregate(0, f); Console.WriteLine("fl2:{0}", fl2); Console.WriteLine(); // 畳み込み右 var fr = list.FoldRight(f, 0); Console.WriteLine("fr:{0}", fr); Console.WriteLine(); // フィルタ var filter = Enumerable.Range(1, 100).Filter(x => x % 2 == 0); Console.WriteLine("filter:{0}", filter.Count()); Console.WriteLine(); list.IterateIndex((i, j) => Console.WriteLine("{0}-{1}", i, j)); Console.WriteLine(); // 解きほぐし Predicate<string> p = x => x == ""; Func<string, string> source = x => { if (String.IsNullOrEmpty(x)) return ""; return x.Substring(1, x.Length - 1); }; var word = "くぁｗせｄｒｆｔｇｙふじこｌｐ；＠"; var unfold = source.Unfold(p,word); foreach (var item in unfold) Console.WriteLine(item); Console.WriteLine(); // 解きほぐし Func<string, string> source2 = x => { if (String.IsNullOrEmpty(x)) return null; return x.Substring(1, x.Length - 1); }; var unfold2 = source2.Unfold(word); foreach (var item in unfold2) Console.WriteLine(item); Console.ReadLine(); } } }
実行結果
2 4 6 8 10 12 2 4 6 8 10 12 fl1:3 fl2:3 fr:-3 filter:50 0-1 1-2 2-3 3-4 4-5 5-6 くぁｗせｄｒｆｔｇｙふじこｌｐ；＠ ぁｗせｄｒｆｔｇｙふじこｌｐ；＠ ｗせｄｒｆｔｇｙふじこｌｐ；＠ せｄｒｆｔｇｙふじこｌｐ；＠ ｄｒｆｔｇｙふじこｌｐ；＠ ｒｆｔｇｙふじこｌｐ；＠ ｆｔｇｙふじこｌｐ；＠ ｔｇｙふじこｌｐ；＠ ｇｙふじこｌｐ；＠ ｙふじこｌｐ；＠ ふじこｌｐ；＠ じこｌｐ；＠ こｌｐ；＠ ｌｐ；＠ ｐ；＠ ；＠ ＠ くぁｗせｄｒｆｔｇｙふじこｌｐ；＠ ぁｗせｄｒｆｔｇｙふじこｌｐ；＠ ｗせｄｒｆｔｇｙふじこｌｐ；＠ せｄｒｆｔｇｙふじこｌｐ；＠ ｄｒｆｔｇｙふじこｌｐ；＠ ｒｆｔｇｙふじこｌｐ；＠ ｆｔｇｙふじこｌｐ；＠ ｔｇｙふじこｌｐ；＠ ｇｙふじこｌｐ；＠ ｙふじこｌｐ；＠ ふじこｌｐ；＠ じこｌｐ；＠ こｌｐ；＠ ｌｐ；＠ ｐ；＠ ；＠ ＠
どうやら、できているようですね(・ω・)
fold(畳み込み)って、つまるところforループなんですよね。
もっと言えば、変化する１つの状態を保持してループを表現してくれるという感じでしょうか。
unfoldは、foldの逆バージョンと言われるけど、それだと少しわかり難いですね。
簡単に言うと、変化する複数の状態を都度作りながらループ表現してくれるという感じでしょうか。
ということは、unfoldは無限への入り口。無限リスト生成マッスィーンということですね、わかります。
[追記：2008/12/16]
ふと気付きました。凡ミスしてたっぽいですｗ
Enumerable.TakeWhile メソッドの存在を考えると、
常識的に考えて・・ 、Unfoldは下記のように無限の要素を返すようにすべきでした。
/// <summary>
/// unfold(解きほぐし)
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="func"></param>
/// <param name="init"></param>
/// <returns></returns>
public static IEnumerable<T> Unfold<T>(this Func<T, T> func, T init)
{
if (func == null) throw new ArgumentException("func");
var seed = init;
yield return seed;
while (true)
{
seed = func(seed);
yield return seed;
}
}
Enumerable.TakeWhile メソッドを使うことによって、
「条件が満たされる間、要素を返す」というようにすることができますからね。
勿論それがたとえ無限だとしてもおｋなわけで。例えば、下記のように書くことができますね。
// 解きほぐし
Func<string, string> source = x => x.Substring(1, x.Length - 1);
var word = "くぁｗせｄｒｆｔｇｙふじこｌｐ；＠";
var unfold = source.Unfold(word).TakeWhile( x => x != "");
foreach (var item in unfold) Console.WriteLine(item);
めでたしめでたし(^ω^)
