在用 C# 实现基本的 Scheme 解释器时,我惊恐地发现了以下问题:

IEnumerator 没有克隆方法!(或更准确地说,IEnumerable 无法为我提供“可克隆”枚举器)。

我想要什么:

interface IEnumerator<T>
{
    bool MoveNext();
    T Current { get; }
    void Reset();
    // NEW!
    IEnumerator<T> Clone();
}

我无法想出一个 IEnumerable 的实现,它无法提供有效的可克隆 IEnumerator(向量、链表等)。所有这些都能够提供 IEnumerator 的 Clone() 的简单实现,如上所述......无论如何,这比提供 Reset() 方法更容易!)。

缺少 Clone 方法意味着枚举序列的任何函数/递归习惯用法都不起作用。

这也意味着我不能“无缝”地使 IEnumerable 的行为像 Lisp“列表”(您使用 car/cdr 来递归枚举)。IE。“(cdr 一些 IEnumerable)”的效率会低得可怜。

任何人都可以建议一个现实的、有用的 IEnumerable 对象示例,该示例无法提供有效的“Clone()”方法吗?“产量”结构是否存在问题?

谁能建议一个解决方法?

有帮助吗?

解决方案

逻辑是不可阻挡的! IEnumerable 不支持 Clone ,你需要 Clone ,因此你不应该使用 IEnumerable

或者更准确地说,您不应该将它作为Scheme解释器工作的基础。为什么不改为创建一个简单的不可变链表呢?

public class Link<TValue>
{
    private readonly TValue value;
    private readonly Link<TValue> next;

    public Link(TValue value, Link<TValue> next)
    {
        this.value = value;
        this.next = next;
    } 

    public TValue Value 
    { 
        get { return value; }
    }

    public Link<TValue> Next 
    {
        get { return next; }
    }

    public IEnumerable<TValue> ToEnumerable()
    {
        for (Link<TValue> v = this; v != null; v = v.next)
            yield return v.value;
    }
}

请注意, ToEnumerable 方法可以方便地以标准C#方式使用。

回答你的问题:

  

任何人都可以建议一个现实的,   有用的,IEnumerable的例子   对象无法做到的   提供有效的“克隆()”。方法?   它是否存在问题?   “收益率”构造

IEnumerable可以在世界上任何地方获取数据。这是一个从控制台读取行的示例:

IEnumerable<string> GetConsoleLines()
{
    for (; ;)
        yield return Console.ReadLine();
}

这有两个问题:首先, Clone 函数编写起来并不是特别简单(而 Reset 将毫无意义)。其次,序列是无限的 - 这是完全允许的。序列是懒惰的。

另一个例子:

IEnumerable<int> GetIntegers()
{
    for (int n = 0; ; n++)
        yield return n;
}

对于这两个例子,“解决方法”是指“解决方法”。你已经接受了没什么用处,因为它会耗尽可用的内存或永远挂断。但这些都是序列的完全有效的例子。

要了解C#和F#序列,您需要查看Haskell中的列表,而不是Scheme中的列表。

如果您认为无限的东西是红鲱鱼,那么从套接字读取字节怎么样:

IEnumerable<byte> GetSocketBytes(Socket s)
{
    byte[] buffer = new bytes[100];
    for (;;)
    {
        int r = s.Receive(buffer);
        if (r == 0)
            yield break;

        for (int n = 0; n < r; n++)
            yield return buffer[n];       
    }
}

如果在套接字下发送了一些字节数,则不会是无限序列。然而,为它编写克隆将是非常困难的。编译器如何生成IEnumerable实现以自动执行它?

一旦创建了克隆,两个实例现在都必须从他们共享的缓冲系统中工作。这是可能的,但实际上并不需要 - 这不是设计使用这些序列的方式。你纯粹在“功能上”对待它们,就像值一样,递归地对它们应用过滤器,而不是“强制性地”对它们进行处理。记住序列中的位置。它比低级 car / cdr 操作更清晰。

进一步的问题:

  

我想知道,最低级别是什么   &QUOT;原语(一个或多个)&QUOT;我需要这样的   我可能想做的任何事情   IEnumerable在我的Scheme解释器中   可以在计划中实施   而不是内置。

我认为简短的回答是查看 Abelson和Sussman ,特别是该部分关于溪流 IEnumerable 是一个流,而不是一个列表。它们描述了如何使用特殊版本的map,filter,accumulate等来处理它们。他们还在第4.2节中提出了统一列表和流的想法。

其他提示

作为一种解决方法,您可以轻松地为进行克隆的IEnumerator制作扩展方法。只需从枚举器创建一个列表,并将这些元素用作成员。

但是你失去了枚举器的流媒体功能 - 因为你是新的“克隆”会导致第一个枚举者完全评估。

如果你可以让原来的枚举器消失,即。如果不再使用它,您可以实现一个“克隆”函数,该函数采用原始枚举器,并将其用作一个或多个枚举器的源。

换句话说,你可以构建这样的东西:

IEnumerable<String> original = GetOriginalEnumerable();
IEnumerator<String>[] newOnes = original.GetEnumerator().AlmostClone(2);
                                                         ^- extension method
                                                         produce 2
                                                         new enumerators

它们可以在内部共享原始枚举器和链接列表,以跟踪枚举值。

这将允许:

  • 无限序列,只要两个枚举器都向前推进(链表将被编写为一旦两个枚举器都通过了特定点,就可以对它们进行 GC)
  • 惰性枚举,两个枚举器中的第一个需要尚未从原始枚举器中检索到的值,它将获取该值并将其存储到链表中,然后再生成它

当然,这里的问题是,如果其中一个枚举器远远领先于另一个枚举器,它仍然需要大量内存。

这是源代码。如果您使用 Subversion,您可以下载包含以下代码的类库的 Visual Studio 2008 解决方案文件以及单独的单元测试项目。

存储库: http://vkarlsen.serveftp.com:81/svnStackOverflow/SO847655
用户名和密码都是“guest”,不带引号。

请注意,这段代码根本不是线程安全的。

public static class EnumeratorExtensions
{
    /// <summary>
    /// "Clones" the specified <see cref="IEnumerator{T}"/> by wrapping it inside N new
    /// <see cref="IEnumerator{T}"/> instances, each can be advanced separately.
    /// See remarks for more information.
    /// </summary>
    /// <typeparam name="T">
    /// The type of elements the <paramref name="enumerator"/> produces.
    /// </typeparam>
    /// <param name="enumerator">
    /// The <see cref="IEnumerator{T}"/> to "clone".
    /// </param>
    /// <param name="clones">
    /// The number of "clones" to produce.
    /// </param>
    /// <returns>
    /// An array of "cloned" <see cref="IEnumerator[T}"/> instances.
    /// </returns>
    /// <remarks>
    /// <para>The cloning process works by producing N new <see cref="IEnumerator{T}"/> instances.</para>
    /// <para>Each <see cref="IEnumerator{T}"/> instance can be advanced separately, over the same
    /// items.</para>
    /// <para>The original <paramref name="enumerator"/> will be lazily evaluated on demand.</para>
    /// <para>If one enumerator advances far beyond the others, the items it has produced will be kept
    /// in memory until all cloned enumerators advanced past them, or they are disposed of.</para>
    /// </remarks>
    /// <exception cref="ArgumentNullException">
    /// <para><paramref name="enumerator"/> is <c>null</c>.</para>
    /// </exception>
    /// <exception cref="ArgumentOutOfRangeException">
    /// <para><paramref name="clones"/> is less than 2.</para>
    /// </exception>
    public static IEnumerator<T>[] Clone<T>(this IEnumerator<T> enumerator, Int32 clones)
    {
        #region Parameter Validation

        if (Object.ReferenceEquals(null, enumerator))
            throw new ArgumentNullException("enumerator");
        if (clones < 2)
            throw new ArgumentOutOfRangeException("clones");

        #endregion

        ClonedEnumerator<T>.EnumeratorWrapper wrapper = new ClonedEnumerator<T>.EnumeratorWrapper
        {
            Enumerator = enumerator,
            Clones = clones
        };
        ClonedEnumerator<T>.Node node = new ClonedEnumerator<T>.Node
        {
            Value = enumerator.Current,
            Next = null
        };

        IEnumerator<T>[] result = new IEnumerator<T>[clones];
        for (Int32 index = 0; index < clones; index++)
            result[index] = new ClonedEnumerator<T>(wrapper, node);
        return result;
    }
}

internal class ClonedEnumerator<T> : IEnumerator<T>, IDisposable
{
    public class EnumeratorWrapper
    {
        public Int32 Clones { get; set; }
        public IEnumerator<T> Enumerator { get; set; }
    }

    public class Node
    {
        public T Value { get; set; }
        public Node Next { get; set; }
    }

    private Node _Node;
    private EnumeratorWrapper _Enumerator;

    public ClonedEnumerator(EnumeratorWrapper enumerator, Node firstNode)
    {
        _Enumerator = enumerator;
        _Node = firstNode;
    }

    public void Dispose()
    {
        _Enumerator.Clones--;
        if (_Enumerator.Clones == 0)
        {
            _Enumerator.Enumerator.Dispose();
            _Enumerator.Enumerator = null;
        }
    }

    public T Current
    {
        get
        {
            return _Node.Value;
        }
    }

    Object System.Collections.IEnumerator.Current
    {
        get
        {
            return Current;
        }
    }

    public Boolean MoveNext()
    {
        if (_Node.Next != null)
        {
            _Node = _Node.Next;
            return true;
        }

        if (_Enumerator.Enumerator.MoveNext())
        {
            _Node.Next = new Node
            {
                Value = _Enumerator.Enumerator.Current,
                Next = null
            };
            _Node = _Node.Next;
            return true;
        }

        return false;
    }

    public void Reset()
    {
        throw new NotImplementedException();
    }
}

这使用反射创建新实例,然后在新实例上设置值。我也从深度的C#中发现这一章非常有用。 迭代器块实现详细信息:自动生成的状态机

static void Main()
{
    var counter = new CountingClass();
    var firstIterator = counter.CountingEnumerator();
    Console.WriteLine("First list");
    firstIterator.MoveNext();
    Console.WriteLine(firstIterator.Current);

    Console.WriteLine("First list cloned");
    var secondIterator = EnumeratorCloner.Clone(firstIterator);

    Console.WriteLine("Second list");
    secondIterator.MoveNext();
    Console.WriteLine(secondIterator.Current);
    secondIterator.MoveNext();
    Console.WriteLine(secondIterator.Current);
    secondIterator.MoveNext();
    Console.WriteLine(secondIterator.Current);

    Console.WriteLine("First list");
    firstIterator.MoveNext();
    Console.WriteLine(firstIterator.Current);
    firstIterator.MoveNext();
    Console.WriteLine(firstIterator.Current);
}

public class CountingClass
{
    public IEnumerator<int> CountingEnumerator()
    {
        int i = 1;
        while (true)
        {
            yield return i;
            i++;
        }
    }
}

public static class EnumeratorCloner
{
    public static T Clone<T>(T source) where T : class, IEnumerator
    {
        var sourceType = source.GetType().UnderlyingSystemType;
        var sourceTypeConstructor = sourceType.GetConstructor(new Type[] { typeof(Int32) });
        var newInstance = sourceTypeConstructor.Invoke(new object[] { -2 }) as T;

        var nonPublicFields = source.GetType().GetFields(BindingFlags.NonPublic | BindingFlags.Instance);
        var publicFields = source.GetType().GetFields(BindingFlags.Public | BindingFlags.Instance);
        foreach (var field in nonPublicFields)
        {
            var value = field.GetValue(source);
            field.SetValue(newInstance, value);
        }
        foreach (var field in publicFields)
        {
            var value = field.GetValue(source);
            field.SetValue(newInstance, value);
        }
        return newInstance;
    }
}

此答案也用于以下问题是否可以克隆IEnumerable实例,保存迭代状态的副本?

为什么不将它作为扩展方法:

public static IEnumerator<T> Clone(this IEnumerator<T> original)
{
    foreach(var v in original)
        yield return v;
}

这基本上会创建并返回一个新的枚举器,而不会完全评估原始的。

编辑:是的,我误读了。 Paul是正确的,这只适用于IEnumerable。

这可能会有所帮助。它需要一些代码来调用IEnumerator上的Dispose():

class Program
{
    static void Main(string[] args)
    {
        //var list = MyClass.DequeueAll().ToList();
        //var list2 = MyClass.DequeueAll().ToList();

        var clonable = MyClass.DequeueAll().ToClonable();


        var list = clonable.Clone().ToList();
        var list2 = clonable.Clone()ToList();
        var list3 = clonable.Clone()ToList();
    }
}

class MyClass
{
    static Queue<string> list = new Queue<string>();

    static MyClass()
    {
        list.Enqueue("one");
        list.Enqueue("two");
        list.Enqueue("three");
        list.Enqueue("four");
        list.Enqueue("five");
    }

    public static IEnumerable<string> DequeueAll()
    {
        while (list.Count > 0)
            yield return list.Dequeue();
    }
}

static class Extensions
{
    public static IClonableEnumerable<T> ToClonable<T>(this IEnumerable<T> e)
    {
        return new ClonableEnumerable<T>(e);
    }
}

class ClonableEnumerable<T> : IClonableEnumerable<T>
{
    List<T> items = new List<T>();
    IEnumerator<T> underlying;

    public ClonableEnumerable(IEnumerable<T> underlying)
    {
        this.underlying = underlying.GetEnumerator();
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new ClonableEnumerator<T>(this);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    private object GetPosition(int position)
    {
        if (HasPosition(position))
            return items[position];

        throw new IndexOutOfRangeException();
    }

    private bool HasPosition(int position)
    {
        lock (this)
        {
            while (items.Count <= position)
            {
                if (underlying.MoveNext())
                {
                    items.Add(underlying.Current);
                }
                else
                {
                    return false;
                }
            }
        }

        return true;
    }

    public IClonableEnumerable<T> Clone()
    {
        return this;
    }


    class ClonableEnumerator<T> : IEnumerator<T>
    {
        ClonableEnumerable<T> enumerable;
        int position = -1;

        public ClonableEnumerator(ClonableEnumerable<T> enumerable)
        {
            this.enumerable = enumerable;
        }

        public T Current
        {
            get
            {
                if (position < 0)
                    throw new Exception();
                return (T)enumerable.GetPosition(position);
            }
        }

        public void Dispose()
        {
        }

        object IEnumerator.Current
        {
            get { return this.Current; }
        }

        public bool MoveNext()
        {
            if(enumerable.HasPosition(position + 1))
            {
                position++;
                return true;
            }
            return false;
        }

        public void Reset()
        {
            position = -1;
        }
    }


}

interface IClonableEnumerable<T> : IEnumerable<T>
{
    IClonableEnumerable<T> Clone();
}

“可克隆”的目的枚举器主要是为了能够保存迭代位置并能够在以后返回它。这意味着,迭代容器必须提供比 IEnumerable 更丰富的接口。它实际上是 IEnumerable IList 之间的东西。使用 IList ,你可以使用整数索引作为枚举器,或者创建一个简单的不可变包装类,保存对列表和当前位置的引用。

如果你的容器不支持随机访问并且只能向前迭代(如单向链表),它必须至少提供获取下一个元素的能力,具有对前一个元素的引用或某些“迭代”状态&QUOT;你可以在迭代器中保存。因此,界面可能如下所示:

interface IIterable<T>
{
    IIterator<T> GetIterator(); // returns an iterator positioned at start
    IIterator<T> GetNext(IIterator<T> prev); // returns an iterator positioned at the next element from the given one
}

interface IIterator<T>
{
    T Current { get; }
    IEnumerable<T> AllRest { get; }
}

请注意,迭代器是不可变的,它不能“向前移动”,我们只能要求我们的可迭代容器给我们一个指向下一个位置的新迭代器。这样做的好处是,只要您需要,您可以将迭代器存储在任何位置,例如,有一堆迭代器,并在需要时返回到先前保存的位置。您可以通过分配变量来保存当前位置以供以后使用,就像使用整数索引一样。

如果需要使用标准语言迭代功能(如 foraech 或LinQ)从给定位置迭代到容器末尾, AllRest 属性非常有用。它不会改变迭代器位置(记住,我们的迭代器是不可变的)。实现可以重复 GetNext yleid return

GetNext 方法实际上可以是迭代器本身的一部分,就像那样:

interface IIterable<T>
{
    IIterator<T> GetIterator(); // returns an iterator positioned at start
}

interface IIterator<T>
{
    T Current { get; }
    IIterator<T> GetNext { get; } // returns an iterator positioned at the next element from the given one
    IEnumerable<T> AllRest { get; }
}

这几乎是一样的。确定下一个状态的逻辑只是从容器实现移到迭代器 实现。请注意,迭代器仍然是不可变。你不能“向前移动”,你只能得到另一个,指向下一个元素。

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top