読者です 読者をやめる 読者になる 読者になる
ようこそ。睡眠不足なプログラマのチラ裏です。

C#でmap(写像)、foldlとfoldr(畳み込み)、unfold(解きほぐし)とか

プログラミング C#3.0

※追記しました。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を受け取るUnfoldは要らんかもしらんですね^^;



では、さっそく使ってみましょう。

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 = "くぁwせdrftgyふじこlp;@";

            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

くぁwせdrftgyふじこlp;@
ぁwせdrftgyふじこlp;@
wせdrftgyふじこlp;@
せdrftgyふじこlp;@
drftgyふじこlp;@
rftgyふじこlp;@
ftgyふじこlp;@
tgyふじこlp;@
gyふじこlp;@
yふじこlp;@
ふじこlp;@
じこlp;@
こlp;@
lp;@
p;@
;@
@

くぁwせdrftgyふじこlp;@
ぁwせdrftgyふじこlp;@
wせdrftgyふじこlp;@
せdrftgyふじこlp;@
drftgyふじこlp;@
rftgyふじこlp;@
ftgyふじこlp;@
tgyふじこlp;@
gyふじこlp;@
yふじこlp;@
ふじこlp;@
じこlp;@
こlp;@
lp;@
p;@
;@
@

どうやら、できているようですね(・ω・)


fold(畳み込み)って、つまるところforループなんですよね。
もっと言えば、変化する1つの状態を保持してループを表現してくれるという感じでしょうか。
unfoldは、foldの逆バージョンと言われるけど、それだと少しわかり難いですね。
簡単に言うと、変化する複数の状態を都度作りながらループ表現してくれるという感じでしょうか。
ということは、unfoldは無限への入り口。無限リスト生成マッスィーンということですね、わかります。




[追記:2008/12/16]

ふと気付きました。凡ミスしてたっぽいですw
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 メソッドを使うことによって、
「条件が満たされる間、要素を返す」というようにすることができますからね。
勿論それがたとえ無限だとしてもおkなわけで。例えば、下記のように書くことができますね。

            // 解きほぐし
            Func<string, string> source = x => x.Substring(1, x.Length - 1);
            var word = "くぁwせdrftgyふじこlp;@";

            var unfold = source.Unfold(word).TakeWhile( x => x != "");
            foreach (var item in unfold) Console.WriteLine(item);


めでたしめでたし(^ω^)