递归方法如何工作？

Question

考虑以下将类型级自然数映射到值级自然数的方法count：

{-# LANGUAGE
    DataKinds
  , KindSignatures
  , PolyKinds
  , FlexibleInstances
  , FlexibleContexts
  , ScopedTypeVariables
  #-}


module Nat where

data Nat = Z | S Nat

data Proxy (a :: k) = Proxy

class Count a where
    count :: a -> Int

instance Count (Proxy Z) where
    count _ = 0

instance Count (Proxy n) => Count (Proxy (S n)) where
    count _ = succ $ count (Proxy :: Proxy n)

它似乎在 repl 中有效：

λ count (Proxy :: Proxy (S(S(S Z))) )
3

要终止递归，必须在运行时间指示 Proxy 的类型，但类型应该在运行时间擦除。我什至可以在 Proxy 定义中用 newtype 替换 data：

newtype Proxy (a :: k) = Proxy ()

— 这将迫使它每次都具有相同的内存表示，因此它是 Coercible。考虑到这一点：

我完全不明白方法是如何分派的。我认为，要么：
- A table 形式 (Type, Method name) ⟶ Function 由编译器生成。然后，在运行时间，所有对象都用它们的类型标记，方法是一个高阶函数，它查看类型标记并在 table 中查找相应的函数。但是人们说类型在编译过程中被完全擦除，所以这并不成立。
- 形式为方法名⟶函数的table附加到每个对象，方法调用表示为方法名.然后，一个function application查找对应的Function，并在强制时应用它。要保存space，table可能会被该类型的所有成员共享，但这样就和用类型标记对象没有区别了。
- A table of form (Method name, Instance index) ⟶ Function 由编译器生成，tables of form (方法名称 -> 实例索引) 在运行时间附加到对象。这意味着一个对象不知道它的类型，但知道它所属的类，以及实例的正确选择。不知道这种做法有没有什么优势。
所以，我不明白运行如果对象没有以某种方式（直接或间接）标记其类型，那么时间系统如何确定方法实例的正确选择。周围的人都在谈论一些字典传递的东西，但我完全不明白：
- 按键是什么？
- 值是多少？
- 字典在哪里？（在堆上，在程序文本里，还是在别处？）
- 谁有字典的指点？
...等等。
即使有一个技巧允许选择方法实例而不用类型标记对象，也只有2个Count实例，所以方法的选择可能只携带 1 比特的信息。（例如，可能有一个 Proxy，其标记为 "apply methods from instance A₁ to me"，并且方法实例在 A₁ 将 Proxy 重新标记为 "apply methods from instance A₀ to me"。）这显然是不够的。每次应用递归实例时，必须在运行时间滴答作响。

你能引导我完成这段代码的执行过程，或者提供一些描述运行时间系统适用细节的链接吗？

Answer 1

类型类被脱糖到记录中。一切都在编译时发生。

data Count a = Count { count :: a -> Int }

instance_Count_ProxyZ :: Count (Proxy Z)
instance_Count_ProxyZ = Count { count = \_ -> 0 }

instance_Count_ProxySn :: Count (Proxy n) -> Count (Proxy (S n))
instance_Count_ProxySn context = Count {
  count = \_ -> succ (count context (Proxy :: Proxy n)) }

每当我们调用 count :: Count n => n -> Int 时，脱糖器（在类型检查器之后运行）会查看 n 的推断类型，并尝试构建 Count n 类型的记录。

所以如果我们写count (Proxy :: Proxy (S (S (S Z))))，我们需要一个Count (S (S (S Z)))类型的记录，并且唯一匹配的实例是Count (Proxy n) -> Count (Proxy (S n))，和n ~ S (S Z)。这意味着我们现在必须构造它的参数，类型为 Count (Proxy (S (S Z)))，依此类推。

请注意，这也是在 Proxy (S n) 的实例中对 count 的应用程序进行脱糖的过程中发生的情况。

在这个过程之后没有类型类留下，一切都只是记录。

Answer 2

每当约束出现在函数声明的 LHS 时，例如

count :: (Count a) => a -> Int

它就像是

的语法糖

count' :: CountDictionary a -> a -> Int

其中 CountDictionary a 是一个 runtime-suitable（但是单例——编译器总是为每种类型选择一个实例！）实际上，方法的 Count class，即

data CountDictionary a = CountDict {
         countMethod :: a -> Int
       }

在我进一步阐述之前，让我重写所有内容，去掉那些有利于 TypeApplications 的丑陋代理：

{-# LANGUAGE AllowAmbiguousTypes, TypeApplications, ScopedTypeVariables, UnicodeSyntax #-}

class Count a where
    count :: Int
⇒ count' :: CountDictionary a -> Int
w/ data CountDictionary a = CountDict Int

instance Count Z where
    count = 0

instance ∀ n . Count n => Count (S n) where
    count = succ $ count @n

现在当你写count @(S(S(S Z)))时，它表示为

count @(S(S(S Z)))
  = count' ( CountDict (succ $ count @(S Z)) )
  = count' ( CountDict (succ $ count' (CountDict (succ $ count @Z))) )
  = count' ( CountDict (succ $ count' (CountDict (succ $ count' (CountDict 0)))) )

递归方法如何工作？

How does a recursive method work?

recursion

haskell

runtime

typeclass

dependent-type