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

C#でもタプル使いたいよね。で、GetHashCodeのオーバーライドはどう実装すればよいの?

プログラミング C#3.0

遅ればせながら、C#でもタプルが欲しくなった今日この頃。
C#4.0では標準でタプルを用意してくれるっぽいけど、今すぐ欲しいよ。


HaskellPythonなどにあるタプル。C#でも使いたいよね!

タプルとは、いくつかの値(数値型、文字列型など)をひとつにまとめて、
あたかもひとつの値のように扱える機能です。リストや配列が同じ型をまとめるのに対して、
タプルは用途や型が異なる型について、ひとつにまとめる目的で使われます。
その特徴から、汎用的で匿名な構造体と考えて差し支えないでしょう。


さっそくジェネリックを用いて、2要素と3要素のタプルを作ってみます。

using System;
using System.Diagnostics;
using System.Runtime.InteropServices;

namespace ClassLibrary1
{
    /// <summary>
    /// タプル 2要素
    /// </summary>
    /// <typeparam name="T1"></typeparam>
    /// <typeparam name="T2"></typeparam>
    [Serializable]
    [StructLayout(LayoutKind.Auto)]
    [DebuggerDisplay("({Item1}, {Item2})")]
    public struct Tuple<T1, T2> : IEquatable<Tuple<T1, T2>>
    {
        public readonly T1 Item1;
        public readonly T2 Item2;

        public Tuple(T1 item1, T2 item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }

        #region 演算子オーバーロード
        public static bool operator !=(Tuple<T1, T2> tuple1, Tuple<T1, T2> tuple2)
        {
            return !tuple1.Equals(tuple2);
        }

        public static bool operator ==(Tuple<T1, T2> tuple1, Tuple<T1, T2> tuple2)
        {
            return tuple1.Equals(tuple2);
        }
        #endregion

        public override bool Equals(object obj)
        {
            if (!(obj is Tuple<T1, T2>)) return false;
            return Equals((Tuple<T1, T2>)obj);
        }

        public override int GetHashCode()
        {
            //XORしときゃいいでしょう たぶん
            int result = Item1 == null ? 0 : Item1.GetHashCode();
            result = result ^ (Item2 == null ? 0 : Item2.GetHashCode());
            return result;
        }

        public static Tuple<T1, T2> Default
        {
            get { return new Tuple<T1, T2>(default(T1), default(T2)); }
        }

        #region IEquatable<Tuple<T1,T2>> メンバ

        public bool Equals(Tuple<T1, T2> tuple)
        {
            return Equals(Item1, tuple.Item1) && Equals(Item2, tuple.Item2);
        }

        #endregion
    }

    /// <summary>
    /// タプル 3要素
    /// </summary>
    /// <typeparam name="T1"></typeparam>
    /// <typeparam name="T2"></typeparam>
    /// <typeparam name="T3"></typeparam>
    [Serializable]
    [StructLayout(LayoutKind.Auto)]
    [DebuggerDisplay("({Item1}, {Item2}, {Item3})")]
    public struct Tuple<T1, T2, T3> : IEquatable<Tuple<T1, T2, T3>>
    {
        public readonly T1 Item1;
        public readonly T2 Item2;
        public readonly T3 Item3;

        public Tuple(T1 item1, T2 item2, T3 item3)
        {
            this.Item1 = item1;
            this.Item2 = item2;
            this.Item3 = item3;
        }

        #region 演算子オーバーロード
        public static bool operator !=(Tuple<T1, T2, T3> tuple1, Tuple<T1, T2, T3> tuple2)
        {
            return !tuple1.Equals(tuple2);
        }

        public static bool operator ==(Tuple<T1, T2, T3> tuple1, Tuple<T1, T2, T3> tuple2)
        {
            return tuple1.Equals(tuple2);
        }
        #endregion

        public override bool Equals(object obj)
        {
            if (!(obj is Tuple<T1, T2, T3>)) return false;
            return Equals((Tuple<T1, T2, T3>)obj);
        }

        public override int GetHashCode()
        {
            //XORしときゃいいでしょう たぶん
            int result = Item1 == null ? 0 : Item1.GetHashCode();
            result = result ^ (Item2 == null ? 0 : Item2.GetHashCode());
            result = result ^ (Item3 == null ? 0 : Item3.GetHashCode());
            return result;
        }

        public static Tuple<T1, T2, T3> Default
        {
            get { return new Tuple<T1, T2, T3>(default(T1), default(T2), default(T3)); }
        }

        #region IEquatable<Tuple<T1,T2,T3>> メンバ

        public bool Equals(Tuple<T1, T2, T3> tuple)
        {
            return Equals(Item1, tuple.Item1) && Equals(Item2, tuple.Item2) && Equals(Item3, tuple.Item3);
        }

        #endregion
    }
}

上記コードでタプルの要件を満たしたものが作れたと思うが、ひとつ疑問がある。
それはGetHashCodeのオーバーライドで実装すべき内容についてです。
基本的には、意味のあるすべての要素のハッシュコードについてXOR(排他的論理和)しておけば問題ないとは思うのだが、
GetHashCodeのオーバーライドの実装って、本当にこれでいいかは疑問が残るところ。
ググっても、情報ごとに主張がバラバラだったりで…、何が正しいのか判断できずにいる。
MSDNによると、一意性や一貫性は保証されないが、とりあえず全部XORしとけ的な
内容だったと思うので、今のところそうしています。有識者の方、教えていただけると助かります。


タプルがあるなら、当然zip関数とunzip関数が欲しいよね

zip関数(Haskell)
http://www.zvon.org/other/haskell/Outputprelude/zip_f.html
unzip関数(Haskell)
http://www.zvon.org/other/haskell/Outputprelude/unzip_f.html


せっかくタプルを作ったのであれば、合わせてZip関数とUnzip関数は欲しいところです。
思い立ったら吉日、すぐ作りましょう。ちょっと必要だったので作ったオマケの関数も添えておきます。

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

namespace ClassLibrary1
{
    public static class Utility
    {
        /// <summary>
        /// Zip関数
        /// 
        /// 2つのリスト各要素を組み合わせたタプルのリストを返します。
        /// リストの長さは短いほうに揃えます。 
        /// </summary>
        /// <typeparam name="T1"></typeparam>
        /// <typeparam name="T2"></typeparam>
        /// <param name="source1"></param>
        /// <param name="source2"></param>
        /// <returns></returns>
        public static IEnumerable<Tuple<T1, T2>> Zip<T1, T2>(IEnumerable<T1> source1, IEnumerable<T2> source2)
        {
            var cnt = source1.Count();
            if (source1.Count() > source2.Count())
                cnt = source2.Count();

            var enm1 = source1.GetEnumerator();
            var enm2 = source2.GetEnumerator();
            for (var i = 0; i < cnt; i++)
            {
                enm1.MoveNext();
                enm2.MoveNext();
                yield return new Tuple<T1, T2>(enm1.Current, enm2.Current);
            }
        }

        /// <summary>
        /// Unzip関数
        /// 
        /// 2要素タプルのリストを2つのリストに分けて、2つのリストを要素として持つタプルを返します。
        /// </summary>
        /// <typeparam name="T1"></typeparam>
        /// <typeparam name="T2"></typeparam>
        /// <param name="source"></param>
        /// <returns></returns>
        public static Tuple<IEnumerable<T1>, IEnumerable<T2>> Unzip<T1, T2>(IEnumerable<Tuple<T1, T2>> source)
        {
            List<T1> list1 = new List<T1>();
            List<T2> list2 = new List<T2>();
            foreach (var tuple in source)
            {
                list1.Add(tuple.Item1);
                list2.Add(tuple.Item2);
            }
            return new Tuple<IEnumerable<T1>, IEnumerable<T2>>(list1, list2);
        }

        /// <summary>
        /// TupleCaterpillar
        /// 
        /// 前方から2つずつの要素をとるタプルを、1要素ずつ移動しながらつくり、そのリストを返します。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <example>
        /// var array = new string[] { "A", "B", "C", "D", "E" };
        /// foreach (var tuple in array.TupleCaterpillar())
        /// {
        ///     Console.WriteLine("{0}:{1}",tuple.Item1,tuple.Item2);
        /// }
        /// 
        /// **********************************************
        /// 結果
        /// **********************************************
        /// A:B
        /// B:C
        /// C:D
        /// D:E
        /// </example>
        /// <returns></returns>
        public static IEnumerable<Tuple<T, T>> TupleCaterpillar<T>(this IEnumerable<T> source)
        {
            int i = 0;
            var map = source.Select(x =>
            {
                if (x.Equals(source.Last())) return default(Tuple<T, T>);
                return new Tuple<T, T>(x, (T)source.Skip(++i).ElementAt(0));
            });
            foreach (var item in map)
            {
                if (item == default(Tuple<T, T>)) yield break;
                yield return item;
            }
        }

        /// <summary>
        /// TupleCaterpillarReverse
        /// 
        /// 後方から2つずつの要素をとるタプルを、1要素ずつ移動しながらつくり、そのリストを返します。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <example>
        /// var array = new string[] { "A", "B", "C", "D", "E" };
        /// foreach (var tuple in array.TupleCaterpillarReverse())
        /// {
        ///     Console.WriteLine("{0}:{1}",tuple.Item1,tuple.Item2);
        /// }
        /// 
        /// **********************************************
        /// 結果
        /// **********************************************
        /// D:E
        /// C:D
        /// B:C
        /// A:B
        /// </example>
        /// <returns></returns>
        public static IEnumerable<Tuple<T, T>> TupleCaterpillarReverse<T>(this IEnumerable<T> source)
        {
            int i = 0;
            source = Reverse(source.ToArray());
            var map = source.Select(x =>
            {
                if (x.Equals(source.Last())) return default(Tuple<T, T>);
                return new Tuple<T, T>((T)source.Skip(++i).ElementAt(0), x);
            });
            foreach (var item in map)
            {
                if (item == default(Tuple<T, T>)) yield break;
                yield return item;
            }
        }

        /// <summary>
        /// Reverse
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="sauce"></param>
        /// <returns></returns>
        public static IList<T> Reverse<T>(IList<T> sauce)
        {
            var array = sauce.ToArray();
            int len = array.Length - 1;
            for (int i = 0; i <= len; i++)
                array[i] = sauce.ElementAt(len - i);
            return array;
        }
    }
}

タプルと各関数を使ってみます。

using System;
using ClassLibrary1;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var listA = new string[] { "a", "b", "c", "d", "e", "f", "g" };
            var listB = new int[] { 6, 5, 4, 3, 2, 1 };
            var listC = new int[] { 1, 2, 3, 4, 5, 6 };

            Console.WriteLine("Zip関数");
            var zip = Utility.Zip(listA, listB);
            foreach (var tuple in zip)
                Console.WriteLine("{0},{1}", tuple.Item1, tuple.Item2);

            Console.WriteLine();
            foreach (var tuple in Utility.Zip(listB, listC))
                Console.Write("{0}", tuple.Item1 + tuple.Item2);

            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine("Unzip関数");
            var unzip = Utility.Unzip(zip);
            foreach (var item in unzip.Item1) 
                Console.Write("{0},",item);
            Console.WriteLine();
            foreach (var item in unzip.Item2)
                Console.Write("{0},",item);
            Console.WriteLine();

            Console.WriteLine();
            Console.WriteLine("TupleCaterpillar");
            foreach (var tuple in listA.TupleCaterpillar())
                Console.WriteLine("{0}:{1}", tuple.Item1, tuple.Item2);

            Console.WriteLine();

            Console.WriteLine();
            Console.WriteLine("TupleCaterpillarReverse");
            foreach (var tuple in listA.TupleCaterpillarReverse())
                Console.WriteLine("{0}:{1}", tuple.Item1, tuple.Item2);

            Console.ReadKey();
        }
    }
}


実行結果

Zip関数
a,6
b,5
c,4
d,3
e,2
f,1

777777

Unzip関数
a,b,c,d,e,f,
6,5,4,3,2,1,

TupleCaterpillar
a:b
b:c
c:d
d:e
e:f
f:g


TupleCaterpillarReverse
f:g
e:f
d:e
c:d
b:c
a:b

お、いい感じにタプルってますね。期待どおりのものが出来たと思う。
必要に応じて4要素タプルや5要素タプルを作ったり、
各タプルに応じた様々な関数を作ると、便利さ100万倍かもしれません。
さあ、unzip3, zip3, zipWith, zipWith3とかいろいろ作ってみよう。




追記:2008/02/09
zeclが書いたZip関数のことは忘れてください。
コメントにてNyaRuRuさんに書き下ろしていただいたZip関数を使いましょう。

public static IEnumerable<Tuple<T1, T2>> Zip<T1, T2>(IEnumerable<T1> source1, IEnumerable<T2> source2)
{
  using (var enumerator1 = source1.GetEnumerator())
  using (var enumerator2 = source2.GetEnumerator())
  {
    while (enumerator1.MoveNext() && enumerator2.MoveNext())
    {
      yield return new Tuple<T1, T2>(enumerator1.Current, enumerator2.Current);
    }
  }
}