我通读了维基百科上关于存在类型的文章。我认为它们之所以被称为存在类型是因为存在操作符(∃)。但我不知道这有什么意义。有什么区别

T = ∃X { X a; int f(X); }

and

T = ∀x { X a; int f(X); }

?


当前回答

类型参数的所有值都存在一个通用类型。存在类型仅适用于满足存在类型约束的类型参数值。

例如,在Scala中,表示存在类型的一种方法是抽象类型,它被限制在某个上界或下界。

trait Existential {
  type Parameter <: Interface
}

同样,受约束的通用类型是存在类型,如下例所示。

trait Existential[Parameter <: Interface]

任何使用站点都可以使用接口,因为存在的任何可实例化子类型必须定义必须实现接口的类型Parameter。

在Scala中,存在类型的退化情况是一种抽象类型,它永远不会被引用,因此不需要由任何子类型定义。这在Scala中有效地简化了List[_]和List<?Java中的>。

我的回答受到Martin Odersky关于统一抽象类型和存在类型的建议的启发。随附的幻灯片有助于理解。

其他回答

当有人定义一个通用类型∀X时,他们是在说:你可以插入任何你想要的类型,我不需要知道任何类型来完成我的工作,我只会不透明地将它称为X。

当有人定义存在类型∃X时,他们在说:我将在这里使用我想要的任何类型;你不会知道任何关于类型的信息,所以你只能模糊地把它称为X。

通用类型让你可以这样写:

void copy<T>(List<T> source, List<T> dest) {
   ...
}

复制函数不知道T是多少,但它不需要知道。

存在类型可以让你这样写:

interface VirtualMachine<B> {
   B compile(String source);
   void run(B bytecode);
}

// Now, if you had a list of VMs you wanted to run on the same input:
void runAllCompilers(List<∃B:VirtualMachine<B>> vms, String source) {
   for (∃B:VirtualMachine<B> vm : vms) {
      B bytecode = vm.compile(source);
      vm.run(bytecode);
   }
}

列表中的每个虚拟机实现都可以有不同的字节码类型。runAllCompilers函数不知道字节码类型是什么,但它不需要知道;它所做的就是将字节码从VirtualMachine.compile传递到VirtualMachine.run。

Java类型通配符(例如:List<?>)是存在类型的一种非常有限的形式。

更新:忘了说你可以用通用类型来模拟存在类型。首先,包装通用类型以隐藏类型参数。第二,反向控制(这有效地交换了上面定义中的“你”和“我”部分,这是存在和共相之间的主要区别)。

// A wrapper that hides the type parameter 'B'
interface VMWrapper {
   void unwrap(VMHandler handler);
}

// A callback (control inversion)
interface VMHandler {
   <B> void handle(VirtualMachine<B> vm);
}

现在,我们可以让VMWrapper调用我们自己的VMHandler,它有一个通用类型的句柄函数。最终效果是一样的,我们的代码必须将B视为不透明的。

void runWithAll(List<VMWrapper> vms, final String input)
{
   for (VMWrapper vm : vms) {
      vm.unwrap(new VMHandler() {
         public <B> void handle(VirtualMachine<B> vm) {
            B bytecode = vm.compile(input);
            vm.run(bytecode);
         }
      });
   }
}

虚拟机实现示例:

class MyVM implements VirtualMachine<byte[]>, VMWrapper {
   public byte[] compile(String input) {
      return null; // TODO: somehow compile the input
   }
   public void run(byte[] bytecode) {
      // TODO: Somehow evaluate 'bytecode'
   }
   public void unwrap(VMHandler handler) {
      handler.handle(this);
   }
}

我画了这个图。我不知道它是否严谨。但如果有帮助的话,我很高兴。

类型参数的所有值都存在一个通用类型。存在类型仅适用于满足存在类型约束的类型参数值。

例如,在Scala中,表示存在类型的一种方法是抽象类型,它被限制在某个上界或下界。

trait Existential {
  type Parameter <: Interface
}

同样,受约束的通用类型是存在类型,如下例所示。

trait Existential[Parameter <: Interface]

任何使用站点都可以使用接口,因为存在的任何可实例化子类型必须定义必须实现接口的类型Parameter。

在Scala中,存在类型的退化情况是一种抽象类型,它永远不会被引用,因此不需要由任何子类型定义。这在Scala中有效地简化了List[_]和List<?Java中的>。

我的回答受到Martin Odersky关于统一抽象类型和存在类型的建议的启发。随附的幻灯片有助于理解。

似乎我来晚了一点,但无论如何,这篇文档增加了关于存在类型是什么的另一种观点,尽管不是特别的语言不可知,这样应该更容易理解存在类型:http://www.cs.uu.nl/groups/ST/Projects/ehc/ehc-book.pdf(第8章)

The difference between a universally and existentially quantified type can be characterized by the following observation: The use of a value with a ∀ quantified type determines the type to choose for the instantiation of the quantified type variable. For example, the caller of the identity function “id :: ∀a.a → a” determines the type to choose for the type variable a for this particular application of id. For the function application “id 3” this type equals Int. The creation of a value with a ∃ quantified type determines, and hides, the type of the quantified type variable. For example, a creator of a “∃a.(a, a → Int)” may have constructed a value of that type from “(3, λx → x)”; another creator has constructed a value with the same type from “(’x’, λx → ord x)”. From a users point of view both values have the same type and are thus interchangeable. The value has a specific type chosen for type variable a, but we do not know which type, so this information can no longer be exploited. This value specific type information has been ‘forgotten’; we only know it exists.

直接回答你的问题:

对于通用类型,T的使用必须包括类型参数x。例如T<String>或T<Integer>。对于存在类型使用T不包括该类型参数,因为它是未知的或不相关的-只需使用T(或在Java中T<?>)。

进一步的信息:

通用/抽象类型和存在类型是对象/函数的消费者/客户和它的生产者/实现之间的二元视角。一方看到的是普遍类型,另一方看到的是存在类型。

在Java中,你可以定义一个泛型类:

public class MyClass<T> {
   // T is existential in here
   T whatever; 
   public MyClass(T w) { this.whatever = w; }

   public static MyClass<?> secretMessage() { return new MyClass("bazzlebleeb"); }
}

// T is universal from out here
MyClass<String> mc1 = new MyClass("foo");
MyClass<Integer> mc2 = new MyClass(123);
MyClass<?> mc3 = MyClass.secretMessage();

From the perspective of a client of MyClass, T is universal because you can substitute any type for T when you use that class and you must know the actual type of T whenever you use an instance of MyClass From the perspective of instance methods in MyClass itself, T is existential because it doesn't know the real type of T In Java, ? represents the existential type - thus when you are inside the class, T is basically ?. If you want to handle an instance of MyClass with T existential, you can declare MyClass<?> as in the secretMessage() example above.

存在类型有时用于隐藏某些东西的实现细节,如在其他地方讨论的那样。Java版本如下所示:

public class ToDraw<T> {
    T obj;
    Function<Pair<T,Graphics>, Void> draw;
    ToDraw(T obj, Function<Pair<T,Graphics>, Void>
    static void draw(ToDraw<?> d, Graphics g) { d.draw.apply(new Pair(d.obj, g)); }
}

// Now you can put these in a list and draw them like so:
List<ToDraw<?>> drawList = ... ;
for(td in drawList) ToDraw.draw(td);

要正确地捕获这一点有点棘手,因为我正在假装使用某种函数式编程语言,而Java不是。但这里的重点是,您正在捕获某种状态加上对该状态进行操作的函数列表,并且您不知道状态部分的真实类型,但函数知道,因为它们已经与该类型匹配。

Now, in Java all non-final non-primitive types are partly existential. This may sound strange, but because a variable declared as Object could potentially be a subclass of Object instead, you cannot declare the specific type, only "this type or a subclass". And so, objects are represented as a bit of state plus a list of functions that operate on that state - exactly which function to call is determined at runtime by lookup. This is very much like the use of existential types above where you have an existential state part and a function that operates on that state.

在没有子类型和类型转换的静态类型编程语言中,存在类型允许管理不同类型对象的列表。T<Int>的列表不能包含T<Long>。然而,T<?>可以包含T的任何变体,允许将许多不同类型的数据放入列表中,并根据需要将它们全部转换为int(或执行数据结构内部提供的任何操作)。

几乎总是可以将具有存在类型的记录转换为不使用闭包的记录。闭包也是存在类型的,因为它关闭的自由变量对调用者是隐藏的。因此,一种支持闭包但不支持存在类型的语言可以允许您创建闭包,这些闭包共享与放入对象的存在部分相同的隐藏状态。