迭代器,枚举和序列之间的区别

Question

我想了解ocaml中迭代器,枚举和序列之间的区别

enumeration:
type 'a t = {
  mutable count : unit -> int; (** Return the number of remaining elements       in the enumeration. *)
  mutable next  : unit -> 'a;  (** Return the next element of the   enumeration or raise [No_more_elements].*)
  mutable clone : unit -> 'a t;(** Return a copy of the enumeration. *)
  mutable fast  : bool;        (** [true] if [count] can be done without reading all elements, [false] otherwise.*)
}
sequence:

type 'a node =
| Nil
| Cons of 'a * 'a t
and 'a t = unit -> 'a node

我对迭代器一无所知

Answer 1

枚举/发电机

BatEnum(你所谓的"枚举",但让我们使用模块名称)或多或少与生成器同构,这通常被称为基于拉取:

generator : unit -> 'a option

这意味着"每次调用时generator (),我都会从集合中为您提供一个新元素,直到没有更多元素并返回None".请注意,这意味着以前的元素无法访问.此行为称为"破坏性".
这与gen库类似.这些迭代器从根本上讲是非常必要的(它们通过维持当前状态来工作).

序列

基于拉的方法不一定是破坏性的,这是Seq类型适合的地方.它是一个类似列表的结构,除了每个节点都隐藏在一个闭包后面.它类似于懒惰列表,但没有保证持久性.您可以通过模式匹配来操纵这些序列,就像列表一样.

type 'a node =
| Nil
| Cons of 'a * 'a seq
and 'a seq = unit -> 'a node

迭代器

序列之类的迭代器也称为"基于推送",其类型与iter您在许多数据结构中找到的函数类似:

iterator : ('a -> unit) -> unit

这意味着" iterator f将f函数应用于集合中的所有元素".

有什么不同？

基于拉动和基于推动的方法之间的一个关键区别是它们的表现力.考虑到你有两个生成器,gen1并且gen2很容易添加它们:

let add gen1 gen2 =
  let gen () = 
    match gen1(), gen2() with
    | Some v1, Some v2 -> Some (v1+v2)
    | _ -> None
  in
  gen

但是,您无法使用大多数基于推送的方法来编写这样的函数,例如sequence,因为您没有完全控制迭代.

另一方面,基于推送的迭代器通常更容易定义并且更快.

建议

从OCaml 4.07开始,Seq可在标准库中找到.有一个seqcompatibiliy包,您可以马上使用,并在相关的组合子的大型文库oseq库.
Seq快速,富有表现力且相当容易使用,因此我建议使用它.