输入错误与rank-2类型和函数组合 [英] Type error with rank-2 types and function composition

问题描述

  { - ＃LANGUAGE ScopedTypeVariables＃ - } 
 
 import Control.Monad.ST 
 import Data.Array.ST 
 import Data.Array 
  

现在，这是我的问题。以下代码typechecks：

  foo :: forall a。 a  - > [a] 
 foo x = elems $ runSTArray $ do 
 newListArray（1,10）（复制10 x）:: ST s（STArray s Int a）
  

但是，当我用组合元素替换 $ 时：

  foo :: forall a。 a  - > [a] 
 foo x = elems。 runSTArray $ do 
 newListArray（1,10）（replicate 10 x）:: ST s（STArray s Int a）
  

我得到这个错误：

 无法匹配预期的类型`forall s。在表达式中：
 newListArray（1，10）（replicate 10 x）：ST s（STArray s i0 e0）'
'ST s0（STArray s0 Int a）'
 ：ST s（STArray s Int a）
在'（$）'的第二个参数中，即
`do {newListArray（1,10）（复制10 x）:: 
 ST s（STArray s Int a）}'
在表达式中：
 elems。 runSTArray 
 $ {newListArray（1，10）（replicate 10 x）:: 
 ST s（STArray s Int a）} 
  

什么是werid，如果我给函数组合自己的名字，那么它会再次敲入：

  elemSTArray = elems。 runSTArray 
 
 foo :: forall a。 a  - > [a] 
 foo x = elemSTArray $ do 
 newListArray（1,10）（复制10 x）:: ST s（STArray s Int a）
  

我不确定这里发生了什么。我期望第二块代码很好地检测。我不明白为什么它会再次敲入，如果我给出组合函数自己的名字。

这是一些代码的简化版本，我在升级时破坏了一些代码从GHC 6.2到7，我试图理解为什么现在发生这种情况。感谢您的帮助！

解决方案

正如你已经在你的帖子的标题中暗示的那样，问题与 runSTArray 具有等级2的多态类型。

  runSTArray :: Ix i => ; （全部ST（STArray s i e）） - >数组即
  

使用

  elems :: Ix i =>阵列i e  - > [e] 
  

和

 （$）::（a  - > b） - > a  - > b 
  

写 runSTArray $ ... 表示需要使用多态类型实例化（$）类型模式中的类型变量 a 而不是单形类型。这需要所谓的impandicative多态性。在2008年ICFP论文中，Dimitrios Vytiniotis，Stephanie Weirich和Simon Peyton Jones解释了GHC如何实现impindicative多态性： FPH：Haskell的一等多态。底线是，虽然FPH经常给你你所期望的行为，但是在你的问题中描述的那些简单的转换中，类型化有时不会被保留下来：参见上述论文的第6.2节。

Here are some pragmas and some imports:

{-# LANGUAGE ScopedTypeVariables #-}

import Control.Monad.ST
import Data.Array.ST
import Data.Array

Now here's my problem. The following code typechecks:

foo :: forall a. a -> [a]
foo x = elems $ runSTArray $ do
    newListArray (1,10) (replicate 10 x) :: ST s (STArray s Int a)

However, when I replace the $ with composition:

foo :: forall a. a -> [a]
foo x = elems . runSTArray $ do
    newListArray (1,10) (replicate 10 x) :: ST s (STArray s Int a)

I get this error:

Couldn't match expected type `forall s. ST s (STArray s i0 e0)'
            with actual type `ST s0 (STArray s0 Int a)'
In the expression:
    newListArray (1, 10) (replicate 10 x) :: ST s (STArray s Int a)
In the second argument of `($)', namely
  `do { newListArray (1, 10) (replicate 10 x) ::
          ST s (STArray s Int a) }'
In the expression:
      elems . runSTArray
  $ do { newListArray (1, 10) (replicate 10 x) ::
           ST s (STArray s Int a) }

What's werid is, if I give the function composition its own name, then it typechecks again:

elemSTArray = elems . runSTArray

foo :: forall a. a -> [a]
foo x = elemSTArray $ do
    newListArray (1,10) (replicate 10 x) :: ST s (STArray s Int a)

I'm not sure what's going on here. I would expect the second piece of code to typecheck nicely. And I don't understand why it typechecks again if I give the composed function its own name.

This is a simplified version of some code that I had that broke when upgrading from GHC 6.2 to 7 and I'm trying to understand why this happens now. Thanks for helping!

解决方案

As you already hint at in the title of your post, the problem has to do with runSTArray having a polymorphic type of rank 2.

runSTArray :: Ix i => (forall s. ST s (STArray s i e)) -> Array i e

With

elems :: Ix i => Array i e -> [e]

and

($) :: (a -> b) -> a -> b

writing runSTArray $ ... means that the type variable a in the type schema of ($) needs to be instantiated with a polymorphic type rather than a monomorphic type. This requires so-called impredicative polymorphism. How GHC implements impredicative polymorphism is explained in the ICFP 2008 paper by Dimitrios Vytiniotis, Stephanie Weirich, and Simon Peyton Jones: FPH : First-class Polymorphism for Haskell. The bottom line is that while FPH often gives you the behaviour that you expect, typeability is sometimes not preserved under simple transformations like the ones you describe in your question: see Section 6.2 of the aforementioned paper.

这篇关于输入错误与rank-2类型和函数组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！