是否可以在不破坏等式推理的情况下使用教会编码？ [英] Is it possible to use church encodings without breaking equational reasoning?

问题描述

  { - ＃LANGUAGE RankNTypes＃ - } 
 
 import前奏曲隐藏（总和）
 
类型列表h = forall t。 （h→t→t）→> t  - > t 
 
 sum_ ::（Num a）=>列表a  - > a 
 sum_ = \ list  - >列表（+）0 
 
 toList :: [a]  - >列出
 toList = \ list cons nil  - > foldr cons nil list 
 
 sum ::（Num a）=> [a]  - > 
  -  sum = sum_。 toList  - 不起作用
 sum = \ a  - > sum_（toList a） -  works 
 
 main = print（sum [1,2,3]）
  

直到等式推理，和的两个定义都是相同的。然而，编译作品的第二个定义，但第一个没有，带有这个错误：

  tmpdel.hs：17 ：14：
无法匹配类型'（a  - > t0  - > t0） - > t0  - > t0'
与'forall t。 （a  - > t  - > t） - > t  - > t'
预期类型：[a]  - >列出
实际类型：[a]  - > （a→t 0→t 0）→> t0  - > t0 
相关绑定包括sum :: [a]  - > a（绑定在tmpdel.hs：17：1）
在'（。）'的第二个参数中，即'toList'
在表达式：sum_中。 toList 
  

似乎 RankNTypes 打破了等式推理。有没有什么办法可以在Haskell中使用教会编码的列表而不会破坏它？ 解决方案

我的印象是ghc渗透所有尽可能地保留所有权利：

  forall a t。 [a]  - > （a  - > t  - > t） - > t  - > t）
  

和

  forall a。 [a]  - >全部（h→t→t）→> t  - > t 
  

可互换使用，见证如下：

  toList':: forall a t。 [a]  - > （a  - > t  - > t） - > t  - > t 
 toList'= toList 
 
 toList :: [a]  - >列出一个
 toList = toList'
  

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

  { - ＃LANGUAGE RankNTypes＃ - } 
前导隐藏（总和）
 
新类型列表h =列表{ runList :: forall t。 （h→t→t）→> t  - > t} 
 
 sum_ ::（Num a）=>列表a  - > a 
 sum_ xs = runList xs（+）0 
 
 toList :: [a]  - >列出
 toList xs = List $ \ c n  - > foldr c n xs 
 
 sum ::（Num a）=> [a]  - > 
 sum = sum_。 toList 
 
 main = print（sum [1,2,3]）
  

Mind this program:

{-# 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])

Both definitions of sum are identical up to equational reasoning. Yet, compiling the second definition of works, but the first one doesn't, with this error:

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

It seems that RankNTypes breaks equational reasoning. Is there any way to have church-encoded lists in Haskell without breaking it??

解决方案

I have the impression that ghc percolates all for-alls as left as possible:

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

and

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

can be used interchangeably as witnessed by:

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

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

Which could explain why sum's type cannot be checked. You can avoid this sort of issues by packaging your polymorphic definition in a newtype wrapper to avoid such hoisting (that paragraph does not appear in newer versions of the doc hence my using the conditional earlier).

{-# 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])

这篇关于是否可以在不破坏等式推理的情况下使用教会编码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！