我正在尝试在Scala中对组合器演算进行非常轻量级的编码。最初，我只是实现S和K组合器，应用程序和常量值。稍后，我希望引入scala函数，并允许将表达式评估为scala函数。但是，这是稍后的内容。到目前为止，这就是我所拥有的。
/** Combinator expression */
sealed abstract class CE
/** Application: CE| (x y) <=> LC| (x:(A=>B) y:A) : B */
case class Ap[A <: CE, B <: CE, X](e1: A, e2: B) extends CE
/** A raw value with type */
case class Value[T](v: T) extends CE
/** Some combinator */
sealed abstract class Comb extends CE
/** The S combinator: CE| S x y z
* LC| λx:(A=>B=>C).λy:(A=>B).λz:A.(x z (y z)) : C
* S : ∀A.∀B.∀C. (A => B => C) => (A => B) => A => C
*/
case object S extends Comb
/** The K combinator: CE| K x y
* LC| λx:A.λy:B.x:A : A
* K : ∀A => ∀B => A
*/
case object K extends Comb
现在，我想对此进行一些类型推断。为了简化实现小步和大步简化，数据模型是无类型的，因此我希望类型在此结构的外部。让我们介绍一些保存类型信息的东西。
trait TypeOf { type typeOf }
值类型很容易。
implicit def typeOfValue[T](vt: Value[T]) : TypeOf =
new TypeOf { type typeOf = T }
应用程序比较棘手，但基本上可以归结为功能应用程序。让我们为组合器应用程序引入类型,，以避免与普通的scala应用程序混淆。
/** Combinator application */
class ⊃[+S, -T]
implicit def typeOfAp[Ap[A, B], A <: CE, B <: CE], X, Y](Ap(A, B)
(implicit aIsFXY: A#typeOf =:= (X⊃Y), bIsX: B#typeOf =:= X) : TypeOf =
{ type typeOf = Y }
这就是我卡住的地方。我需要代表S和K组合器的类型。但是，它们是普遍量化的类型。在开始应用它们之前，您不知道它们的实际类型。让我们以K为例。
(K x:X y:Y) : X
(K x:X) : ∀Y.Y => X
(K) : ∀X.x => ∀Y.Y => X
我尝试使用它的前几次，我将K参数化为K [X，Y]，但是(灾难性地)这是不够多态的。 K的类型应等待第一个参数的类型，然后是下一个参数的类型。如果仅将K应用于一个值，则下一个参数的类型尚未确定。您应该可以采用(K x:X)并将其应用于字符串，int或所需的任何类型。
所以我的问题是如何编写为S和K生成typeOf的隐式，以及如何正确处理quan量化的类型。也许我想要这样的东西？
implicit def typeOfK(k: K.type): TypeOf = { type typeOf = ∀[X, X ⊃ (∀[Y, Y⊃X])] }
但是，我不确定应该如何编写∀型来进行管道连接。我有一种感觉，除了正确理解∀之外，还有另外一个隐含的typeOfAp处理A＃typeOf =:=∀[...]情况，除了现有的A＃typeOf =:=⊃[ ...] 一。
谢谢，
马修
最佳答案
这有帮助吗？
trait λ {
type ap[X] <: λ
}
type K = λ {
type ap[X<:λ] = λ {
type ap[Y<:λ] = X
}
}
type S = λ {
type ap[X<:λ] = λ {
type ap[Y<:λ] = λ {
type ap[Z<:λ] = X#ap[Z]#ap[Y#ap[Z]]
}
}
}
type I = S#ap[K]#ap[K]
def ap[X<:λ,Y<:λ](x:X,y:Y): X#ap[Y]
关于scala - Scala组合器演算数据模型的类型推断，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4528953/