内部イテレータを外部イテレータに変形する（その1：配列の場合）

C#

「内部イテレータを外部イテレータに手動で変換してみる実験 - terazzoの日記」の「内部イテレータを外部イテレータに変形する 1.配列の場合」。かなり長くなってしまった。
ForEachの引数に渡すIntProcedureはPredicateで置き換えようと思ったけど、後々IntProcedureを拡張するようなので、最初からIntProcedureのままでいくことにする。

「継続渡しに変更」の直前まで

using System;
namespace OutIteratorFromInIterator
{
  interface IIntProcedure
  {
    bool Process(int n);
  }

  class IntProcedure : IIntProcedure
  {
    public bool Process(int n)
    {
      Console.Write(n + " ");
      return true;
    }
  }

  interface IntIterableIn
  {
    bool ForEach(IIntProcedure proc);
  }

  class IntArray : IntIterableIn
  {
    int[] _ar;

    public IntArray(int[] ar)
    {
      _ar = ar;
    }

    public int this[int index]
    {
      get { return _ar[index]; }
      set { _ar[index] = value; }
    }

    public int Count
    {
      get { return _ar.Length; }
    }

    public bool ForEach(IIntProcedure proc)
    {
      return ForEachRec(0, this, proc);
    }

    static bool ForEachRec(int i, IntArray intArray, IIntProcedure proc)
    {
      // 引数の分のスタックの消費を節約したいなぁ、とか。
      // 実際どうなんだろ。有効な手段なのかな。
      Func<bool> innerRec = () =>
        {
          if (i >= intArray.Count)
          {
            return true;
          }
          else if (!proc.Process(intArray[i++]))
          {
            return false;
          }
          else
          {
            return innerRec();
          }
        };

      return innerRec();
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      int[] sample = new int[] { 1,3,4,7,8 };
      IntArray intArray = new IntArray(sample);
      RunIteratorIn(intArray);
    }

    static void RunIteratorIn(IntArray intArray)
    {
      IIntProcedure proc = new IntProcedure();
      intArray.ForEach(proc);
      Console.WriteLine("");
    }
  }
}

スタックの消費を節約するために、引数を取らないローカルな再帰メソッド（メソッドって言って良いのかな？）作れるのかなー、と思ってやってみた。できてるみたいなので、とりあえず良しとする。本当に節約になってるのかどうかは知らんけど。
ループ、再帰メソッド、ローカルな再帰メソッドの3通りで配列を走査してみた：http://ideone.com/g2LXo

継続渡しに変更

namespace OutIteratorFromInIterator
{

  ////////////////////////////////////////////////////////////
  // * IContinuationHolder と ContinuationHolder を追加
  // * IContinuationHolderTop と ContinuationHolderTop を追加
  ////////////////////////////////////////////////////////////

  interface IContinuationHolder
  {
    void Call(bool b);
  }

  class ContinuationHolder : IContinuationHolder
  {
    ContinuationHolder _contHolder;

    public ContinuationHolder(ContinuationHolder contHolder)
    {
      _contHolder = contHolder;
    }

    public void Call(bool b)
    {
      _contHolder.Call(b);
    }
  }

  interface IContinuationHolderTop : IContinuationHolder
  {
    bool GetResult();
  }

  class ContinuationHolderTop : IContinuationHolderTop
  {
    bool _result;

    public void Call(bool b)
    {
      _result = b;
    }

    public bool GetResult()
    {
      return _result;
    }
  }

  ////////////////////////////////////
  // * ForEachを変更
  // * ForEachRecをForEachRecCpsへ変更
  // * IntIterableInは変更無し
  ////////////////////////////////////
  class IntArray : IntIterableIn
  {
    public bool ForEach(IIntProcedure proc)
    {
      IContinuationHolderTop contHolder = new ContinuationHolderTop();
      ForEachRecCps(0, this, proc, contHolder);
      return contHolder.GetResult();
    }

    static void ForEachRecCps(int i, IntArray intArray,
                              IIntProcedure proc,
                              IContinuationHolder contHolder)
    {
      Action innerRec = () =>
        {
          if (i >= intArray.Count)
          {
            contHolder.Call(true);
          }
          else if (!proc.Process(intArray[i++]))
          {
            contHolder.Call(false);
          }
          else
          {
            innerRec();
          }
        };

      innerRec();
    }
  }

  ///////////////////////
  // Program はそのまま
  ///////////////////////
}

中断可能に変更

元ネタのforEachRecCpsIterableの再帰する部分の、BooleanResultHandlerIterableの無名クラスのインスタンスを作っている所で、

  • BooleanResultHandlerIterableのメンバであるgetResultが定義されていない
  • BooleanResultHandleriterableのメンバでないputResultが定義されている

ので、少なくとも前者でコンパイルできないんじゃねーかなぁ（Java書いた事無いから知らん）とか思いながら、前回を参考に適当にやってみた。ってか、ほとんど同じになった。

using System;
namespace OutIteratorFromInIterator
{
  //////////////////////////////////////////////
  // * IContinuationHolder に SetNext を追加
  // * IContinuationHolderTop に GetNext を追加
  //////////////////////////////////////////////

  interface IContinuationHolder
  {
    void Call(bool b);
    void SetNext(Action next);
  }

  class ContinuationHolder : IContinuationHolder
  {
    IContinuationHolder _contHolder;

    public ContinuationHolder(IContinuationHolder contHolder)
    {
      _contHolder = contHolder;
    }

    public void Call(bool b)
    {
      _contHolder.Call(b);
    }

    public void SetNext(Action next)
    {
      _contHolder.SetNext(next);
    }
  }

  interface IContinuationHolderTop : IContinuationHolder
  {
    bool GetResult();
    Action GetNext();
  }

  class ContinuationHolderTop : IContinuationHolderTop
  {
    bool _result;

    Action _next;

    public void Call(bool b)
    {
      _result = b;
    }

    public bool GetResult()
    {
      return _result;
    }

    public void SetNext(Action next)
    {
      _next = next;
    }

    public Action GetNext()
    {
      return _next;
    }
  }

  //////////////////////////////////////////////////
  // * ForEach を変更
  // * ForEachRecCps を ForEachRecCpsIterable へ変更
  // * IntIterableInは変更無し
  //////////////////////////////////////////////////
  class IntArray : IntIterableIn
  {
    public bool ForEach(IIntProcedure proc)
    {
      IContinuationHolderTop contHolder = new ContinuationHolderTop();
      ForEachRecCpsIterable(0, this, proc, contHolder);
      Action thunk = null;
      while (null != (thunk = contHolder.GetNext()))
      {
        thunk();
      }
      return contHolder.GetResult();
    }

    static void ForEachRecCpsIterable(int i, IntArray intArray,
                                      IIntProcedure proc,
                                      IContinuationHolder contHolder)
    {
      Action innerRec = () =>
        {
          if (i >= intArray.Count)
          {
            contHolder.SetNext(null);
            contHolder.Call(true);
          }
          else if (!proc.Process(intArray[i++]))
          {
            contHolder.SetNext(null);
            contHolder.Call(false);
          }
          else
          {
            contHolder = new ContinuationHolder(contHolder);
            Action thunk = () => innerRec();
            contHolder.SetNext(thunk);
          }
        };
      innerRec();
    }
  }

  ///////////////////////
  // Program はそのまま
  ///////////////////////
}

ここまでは、FactとFiboでの練習を踏まえれば簡単。

最後に、このForEachRecCpsIterableを使ってIntArrayを外部イテレータ化する

using System;
using System.Collections.Generic;
namespace OutIteratorFromInIterator
{
  //////////////////////////////////////////////////
  // * IIntProcedureTop と IntProcedureTop を追加
  //////////////////////////////////////////////////
  interface IIntProcedureTop : IIntProcedure
  {
    int LastProcessedValue();
  }

  class IntProcedureTop : IIntProcedureTop
  {
    int _lastProcessedValue;

    public bool Process(int n)
    {
      // nを使って何をやるかは外側で書かれるので、
      // ここでは Console.Write しない。

      _lastProcessedValue = n;
      return true;
    }

    public int LastProcessedValue()
    {
      return _lastProcessedValue;
    }
  }

  ///////////////////////////////////////////////////////////////////
  // * GetEnumerator を追加
  // * IntIterableInは変更無し
  // * IntArray が IEnumerable<int> も実装するように変更
  ///////////////////////////////////////////////////////////////////
  class IntArray : IntIterableIn, IEnumerable<int>
  {
    public bool ForEach(IIntProcedure proc)
    {
      IContinuationHolderTop contHolder = new ContinuationHolderTop();
      ForEachRecCpsIterable(0, this, proc, contHolder);
      Action thunk = null;
      while (null != (thunk = contHolder.GetNext()))
      {
        thunk();
      }
      return contHolder.GetResult();
    }

    static void ForEachRecCpsIterable(int i, IntArray intArray,
                                      IIntProcedure proc,
                                      IContinuationHolder contHolder)
    {
      Action innerRec = () =>
        {
          if (i >= intArray.Count)
          {
            contHolder.SetNext(null);
            contHolder.Call(true);
          }
          else if (!proc.Process(intArray[i++]))
          {
            contHolder.SetNext(null);
            contHolder.Call(false);
          }
          else if (i >= intArray.Count)
          {
            contHolder.SetNext(null);
            contHolder.Call(true);
          }
          else
          {
            contHolder = new ContinuationHolder(contHolder);
            Action thunk = () => innerRec();
            contHolder.SetNext(thunk);
          }
        };
      innerRec();
    }

    public IEnumerator<int> GetEnumerator()
    {
      IIntProcedureTop proc = new IntProcedureTop();
      IContinuationHolderTop contHolder = new ContinuationHolderTop();
      if (Count > 0)
      {
        Action next =
          () => ForEachRecCpsIterable(0, this, proc, contHolder);
        contHolder.SetNext(next);
      }

      Action thunk = null;
      while (null != (thunk = contHolder.GetNext()))
      {
        thunk();
        yield return proc.LastProcessedValue();
      }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
      return GetEnumerator();
    }
  }


  ///////////////////////////////////
  // * RunIteratorOut を追加
  // * Main を変更
  ///////////////////////////////////
  class Program
  {
    static void Main(string[] args)
    {
      int[] sample = new int[] { 1,3,4,7,8 };
      IntArray intArray = new IntArray(sample);
      RunIteratorIn(intArray);
      RunIteratorOut(intArray);
    }

    static void RunIteratorIn(IntArray intArray)
    {
      IIntProcedure proc = new IntProcedure();
      intArray.ForEach(proc);
      Console.WriteLine("");
    }

    static void RunIteratorOut(IntArray intArray)
    {
      foreach (int n in intArray)
      {
        Console.Write(n + " ");
      }
      Console.WriteLine("");
    }
  }
}

GetEnumeratorでyield returnを使ってしまってるけど、これはIEnumeratorを継承したクラスを定義するのが面倒だったからってだけ。だから問題ないはず。そもそもyield return使えるのなら、（配列の場合は）わざわざこんな面倒くさいことしなくても、外部イテレータを直接簡単に書ける。
元ネタの最後で

これで完成！と思いきや、実は5回呼んでもhasNext()がtrueを戻すため、ループが一回増えてしまう。これはforEachRecCpsIterable()で無条件で匿名内部クラスをnewしてsetNext()しているため。
外部イテレータを実装する場合、実際に処理を行う前にhasNext()で次の処理が可能かを返してやらないと行けない。事前に処理可能かどうかを判定できるかは処理によって違う。この部分は処理の内容を見て手を入れてやらないと行けないかも。

とあるが、これはIntProcedureが

  1. 配列の各要素について、何らかの判定を行い
  2. 処理を続行する場合にはtrueを、中断する場合にはfalseを返す

という仕様になっているから。何も考えずただ全要素を走査するだけなら常に「次の処理」を作成してやれば良い。そうなると、IIntProcedure.Processが値を返す必要はなくなる。実際C#のList.ForEachはActionを引数に取るし、Schemeのfor-eachも初めの引数で渡される手続きの戻り値は無視される。そういうこともあってか、ForEachに渡す処理が、ループを続行するか否かの判定を行うのは、自分はちょっと違和感がある。ループを継続するか中断するの判断が必要な場合は、別の方法を考えた方がいいんじゃないかなぁ。根拠は無くて、あくまで直感だけど。
ということで、実際に動かしてみた：http://ideone.com/3YARz

僕が一番興味があるのは次の木構造のイテレータ。2分木の外部イテレータは（僕にスキルが無いだけで、本当はyield returnで簡単に書けるのかもしれないけど）yield returnを使っても書けなかった（「yield return - チキン煮込みチーズミックス4辛」参照）。

ということで、つづく。