是否可以在不破坏等式推理的情况下使用教会编码？

Question

注意这个程序：

{-# LANGUAGE RankNTypes #-}

import Prelude hiding (sum)

type List h = forall t . (h -> t -> t) -> t -> t

sum_ :: (Num a) => List a -> a
sum_ = \ list -> list (+) 0

toList :: [a] -> List a
toList = \ list cons nil -> foldr cons nil list

sum :: (Num a) => [a] -> a
-- sum = sum_ . toList        -- does not work
sum = \ a -> sum_ (toList a)  -- works

main = print (sum [1,2,3])

和的两个定义在等式推理上是相同的。然而，编译第二个定义的作品，但第一个没有，出现这个错误：

tmpdel.hs:17:14:
    Couldn't match type ‘(a -> t0 -> t0) -> t0 -> t0’
                  with ‘forall t. (a -> t -> t) -> t -> t’
    Expected type: [a] -> List a
      Actual type: [a] -> (a -> t0 -> t0) -> t0 -> t0
    Relevant bindings include sum :: [a] -> a (bound at tmpdel.hs:17:1)
    In the second argument of ‘(.)’, namely ‘toList’
    In the expression: sum_ . toList

看来RankNTypes打破了等式推理。有没有办法在不破坏 Haskell 的情况下使用教会编码的列表？？

Answer 1

这里有一个有点吓人的技巧，你可以试试。在任何地方都有 rank-2 类型变量，请改用空类型；在任何你会选择类型变量实例化的地方，使用 unsafeCoerce。使用空类型可以确保（尽可能地）您不会做任何可以观察到应该是不可观察的值的事情。因此：

import Data.Void
import Unsafe.Coerce

type List a = (a -> Void -> Void) -> Void -> Void

toList :: [a] -> List a
toList xs = \cons nil -> foldr cons nil xs

sum_ :: Num a => List a -> a
sum_ xs = unsafeCoerce xs (+) 0

main :: IO ()
main = print (sum_ . toList $ [1,2,3])

你可能想写一个更安全的 unsafeCoerce 版本，比如：

instantiate :: List a -> (a -> r -> r) -> r -> r
instantiate = unsafeCoerce

然后 sum_ xs = instantiate xs (+) 0 作为替代定义工作得很好，并且您运行没有将您的 List a 变成真正任意的东西的风险。

Answer 2

我的印象是 ghc 尽可能地渗透所有 for-alls：

forall a t. [a] -> (a -> t -> t) -> t -> t)

和

forall a. [a] -> forall t . (h -> t -> t) -> t -> t

可以互换使用：

toList' :: forall a t. [a] -> (a -> t -> t) -> t -> t
toList' = toList

toList :: [a] -> List a
toList = toList'

这可以解释为什么无法检查 sum 的类型。您可以通过将多态定义打包在 newtype 包装器中来避免此类问题，以避免出现此类 hoisting （该段落未出现在较新版本的文档中，因此我之前使用了条件）。

{-# LANGUAGE RankNTypes #-}
import Prelude hiding (sum)

newtype List h = List { runList :: forall t . (h -> t -> t) -> t -> t }

sum_ :: (Num a) => List a -> a
sum_ xs = runList xs (+) 0

toList :: [a] -> List a
toList xs = List $ \ c n -> foldr c n xs

sum :: (Num a) => [a] -> a
sum = sum_ . toList

main = print (sum [1,2,3])

Answer 3

一般等式推理只在Haskell表示的"underlying System F"中成立。在这种情况下，正如其他人指出的那样，您会被绊倒，因为 Haskell 向左移动 foralls 和会自动在各个点应用正确的类型。您可以通过 newtype 包装器提供关于类型应用程序应该出现在哪里的提示来修复它。如您所见，您还可以通过 eta 扩展来操作何时发生类型应用，因为 let 和 lambda 的 Hindley-Milner 类型规则不同：forall 是通过 "generalization" 引入的规则，默认情况下，单独在 lets（和其他等效的命名绑定）。

是否可以在不破坏等式推理的情况下使用教会编码？

Is it possible to use church encodings without breaking equational reasoning?

haskell

list

church-encoding

equational-reasoning