スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

マルチパラダイム時代におけるデータ構造 第13回 ー 不変なコンセンスセルを考えよう

 この記事は、マルチパラダイム時代におけるデータ構造 第12回 ー 不変なのか可変なのかはっきりしようの続きです。前回は、不変と可変をはっきりさせることが、データ構造の設計上大切である事を解説しました。今回は不変コンセンスセルを実装することにより、不変とは何かについて解説します。
 前回述べたように、不変なデータ構造を改めて実装しましょう。前回は不変タプルを実装したので、今回は不変コンセンスセルを実装しましょう。そうすれば、プログラムが短すぎて実感できなかった不変の特性を感じることができると思います。

using System;

namespace DataStructure
{
    //1つの要素とそれ以外の要素への参照を持つ不変なデータ構造。
    class ImmutabConsCell<T> : IImmutablDataFreeManager<T>
    {
        #region Field

        //要素
        private ImmutabTuple<T, ImmutabConsCell<T>> _cons;

        #endregion

        #region Property

        // 最初の要素。
        //※プロパティ名はカーと読む。
        public T Car
        {
            get { return this._cons.First; }
        }

        //他の要素。
        //※プロパティ名はクダーと読む。
        public ImmutabConsCell<T> Cdr
        {
            get
            {
                if ( this._cons == null )
                    return null;
                return this._cons.Second;
            }
        }

        #endregion

        #region Constructor

        //格納する要素を指定し、インスタンスを生成する。
        public ImmutabConsCell( T element )
            : this( element, null )
        {
        }

        //格納する要素と次のセルを指定し、インスタンスを生成する。
        public ImmutabConsCell( T element, ImmutabConsCell<T> next )
        {
            this._cons =
                new ImmutabTuple<T, ImmutabConsCell<T>>(
                    element, next );
        }

        #endregion

        #region Method

        //適切なcdrを取得する。
        private static ImmutabConsCell<T> GetCdr(
            int count,
            int max )
        {
            return count == max
                ? null
                : new ImmutabConsCell<T>(
                    default( T ),
                    GetCdr( ++count, max ) );
        }

        //インスタンスの文字列表現を取得する。
        public override string ToString( )
        {
            System.Text.StringBuilder result =
                new System.Text.StringBuilder();
            ImmutabConsCell<T> cons = this;
            result.Append( "{ " );
            do {
                result.Append( cons.Car + " " );
                cons = cons.Cdr;
            } while ( cons != null );
            result.Append( "}" );
            return result.ToString();
        }

        #endregion

        #region IDataFreeManager<T>

        //cdrの数を数える。
        private int GetCdrCount( ImmutabConsCell<T> target, int index )
        {
            if ( target.Cdr == null ) return index;
            else return GetCdrCount( target.Cdr, ++index );
        }

        //要素の数を返す。
        public int Count
        {
            get
            {
                return this.GetCdrCount( this, 1 );
            }
        }

        //最初のデータを選択する。
        public T Select( )
        {
            return this.Car;
        }

        //指定位置のデータを選択する。
        private ImmutabConsCell<T> Select(
            ImmutabConsCell<T> target, int index, int count )
        {
            if ( index >= this.Count )
                throw new IndexOutOfRangeException(
                    "指定された位置" + index +
                    "にデータは存在しません。" );
            return index == count
                ? target
                : this.Select(
                    target.Cdr,
                    index,
                    ++count );
        }

        //指定位置のデータを選択する。
        public T Select( int index )
        {
            return this.Select( this, index, 0 ).Car;
        }

        //cdrを初期化する
        private ImmutabConsCell<T> InitCdr( ImmutabConsCell<T> old )
        {
            return old == null
                ? null
                : new ImmutabConsCell<T>(
                    old.Car,
                    this.InitCdr( old.Cdr ) );
        }

        //指定位置で任意の関数を実行する。
        private ImmutabConsCell<T> Common(
            ImmutabConsCell<T> old,
            T value,
            int index,
            Func<ImmutabConsCell<T>, T, ImmutabConsCell<T>> hitIndexFunc,
            int count )
        {
            if ( index == count ) {
                return hitIndexFunc( old, value );
            } else {
                if ( old == null ) return null;
                return new ImmutabConsCell<T>(
                    old.Car,
                    this.Common(
                        old.Cdr,
                        value,
                        index,
                        hitIndexFunc,
                        ++count ) );
            }
        }

        //最後尾へデータを追加する。
        public IImmutablDataManager<T> Insert( T value )
        {
            return this.Insert( value, this.Count );
        }

        //指定位置へデータを発生させる。
        public IImmutablDataFreeManager<T> Insert( T value, int index )
        {
            return ( IImmutablDataFreeManager<T> )
                this.Common(
                    this,
                    value,
                    index,
                    ( ImmutabConsCell<T> obj, T element ) =>
                        new ImmutabConsCell<T>(
                            element,
                            this.InitCdr( obj ) ),
                    0 );
        }

        //指定位置のデータを更新する。
        public IImmutablDataFreeManager<T> Update( T newValue, int index )
        {
            return this.Common(
                this,
                newValue,
                index,
                ( ImmutabConsCell<T> obj, T element ) =>
                    new ImmutabConsCell<T>(
                    element,
                    this.InitCdr( obj.Cdr ) ),
                0 );
        }

        //最後尾のデータを消滅する。
        public IImmutablDataManager<T> Delete( )
        {
            return this.Delete( this.Count - 1 );
        }

        //指定位置のデータを消滅する。
        public IImmutablDataFreeManager<T> Delete( int index )
        {
            return this.Common(
                this,
                default( T ),
                index,
                ( ImmutabConsCell<T> obj, T element ) =>
                    obj.Cdr == null
                    ? null
                    : new ImmutabConsCell<T>(
                        obj.Cdr.Car,
                        this.InitCdr(
                            obj.Cdr.Cdr ) ),
                0 );
        }

        #endregion

        #region Operator

        //暗黙的に不変コンスセルを不変タプルに変換する。
        public static implicit operator
            ImmutabTuple<T, ImmutabConsCell<T>>(
                ImmutabConsCell<T> obj )
        {
            if ( obj == null ) return null;
            return new ImmutabTuple<T, ImmutabConsCell<T>>(
                obj.Car, obj.Cdr );
        }

        #endregion
    }
}

スムーズな解説のために不変を意識しつつ宣言型プログラミングで実装していたので、以前との違いが分かりにくいかもしれませんが、データライフサイクルで新しいオブジェクトを返すのは、大きく異なります。名前が長い以外の特徴がわからないかもしれませんので、これから解説します。
 不変であるためには、デフォルトコンストラクタは禁止せねばなりません。何故ならば、後でプロパティの値を変えてはならないからです。変えることを許可してしまうと、オブジェクトが可変になってしまいます。加えて、データライフサイクルでは、必ず新しいインスタンスを返さねばなりません。これも不変を保つために必要な事です。不変性について知らない人は、これらの事柄を不便な制約のように見えるでしょう。
 しかし、不変であることは明確なメリットがあります。それは、処理の順番に依存しにくくなる事です。何故ならば、処理結果が与える値で決定されるからです。これは、並列処理で大きな武器となります。処理の順番で結果が変わる場合、並列処理で正しい結果を得るのは大変です。また、テストもやり易くなります。不変であることは大きなメリットがあるのです。
 では、なぜ可変という手段があるのでしょうか?それについては、次回可変オブジェクトとともに解説します。続く...
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

インドリ

Author:インドリ
みなさん、はじめまして、
コンニチハ。

ボクは、無限の夢(infinity dream)を持つネタ好きな虹色の鳥インドリ(in dre)です。
色々な情報処理技術を啄ばむから楽しみにしてね。

http://twitter.com/indori
は別人による嫌がらせ行為です。
私とは関係ないので注意して下さい。
次はなりすましブログなどをするかもしれませんが、ここ以外でブログをするつもりがないので、ここ以外にインドリのブログがあったとしても無視してください。


何度言っても分からない人がいるので、ここにコメント欄へ書き込むときの注意事項を書きます。


一、社会人としてのマナーをわきまえましょう。
一、妄想に基づく書き込みを止めてください。
一、暴言の類は書かないで下さい。
一、某誹謗中傷サイトの書き込みは彼らの妄想に基づく書き込みですから無視して、ここへ書き込まないで下さい。
一、コメント書く前に他のコメントよく読んでから行って下さい。
一、言いがかかり等の行為を禁止します。
一、その他常識的に考えて迷惑なコメントはしないで下さい。


以上のルールを守れない人のコメントは削除します。



利用上の注意
ここに紹介してある文章およびプログラムコードは正確であるように心がけておりますが、内容を保証するものではありません。当サイトの内容によって生じた損害については、一切の責任を負いませんので御了承ください。


執筆したCodeZineの記事


【VB.NETで仮想CPUを作ろう】

  1. VB.NETで仮想CPUを作ろう
  2. レジスタの実装
  3. 仮想CPUのGUI化
  4. テストドライバの改良
  5. CPUの基礎動作の実装
  6. MOV命令の実装
  7. ADD命令実装
  8. SUB命令実装
  9. INC命令&DEC命令の実装と命令長
  10. MLU命令の実装とModR/Mについて
  11. DIV命令の実装とイベント設計について
  12. 機械語駆動式 関数電卓を作ろう!
  13. 機械語駆動式 関数電卓を作ろう! 解答編(前半)
  14. 機械語駆動式 関数電卓を作ろう! 解答編(後半)


【仮想ネットワーク実装でTCP/IPを学ぼう】
  1. TCP/IPの基礎と勘所
  2. ネットワークアクセス層の勘所
  3. インターネット層の勘所
  4. トランスポート層の勘所
  5. アプリケーション層の勘所
  6. セキュリティの基礎と仮想ネットワークの仕様
  7. GDI+と独自プロトコルの定義



【並列化】
インテル Parallel Studioを使って並列化プログラミングを試してみた
並列プログラミングの効率的なデバッグを実現する「Parallel Inspector」


【TBBシリーズ】
  1. インテル スレッディング・ビルディング・ブロックの概要
  2. インテルTBBから学ぶループの並列化
  3. スレッドセーフとインテルTBBのコンテナ
  4. インテルTBBのスレッドクラス


【OpenMPシリーズ】
  1. OpenMPの基礎構文
  2. OpenMPの実行時ライブラリと並列ループ
  3. OpenMPのメモリモデルとfork- joinモデル

最近の記事
最近のコメント
月別アーカイブ
カテゴリ
Ada (9)
COBOL (5)
C (9)
C++ (11)
C# (370)
D (25)
Java (8)
Perl (1)
Ruby (14)
PHP (2)
Boo (2)
Cobra (2)
LISP (6)
F# (33)
HTML (0)
XHTML (0)
CSS (0)
XML (0)
XSLT (0)
Scala (4)
WPF (0)
WF (2)
WCF (0)
LINQ (4)
MONO (5)
Linux (0)
MySQL (0)
ブログ内検索
リンク
最近のトラックバック
RSSフィード
ブロとも申請フォーム

この人とブロともになる

QRコード
FC2カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。