haskell - 如何将 `forall a. a -> a` 转换回 `a -> a` ？

Question

在我的实际问题中，我有一个函数f，作为参数传递，它更改列表中的顺序，但对类型没有要求，也不会更改类型。我想在 [Int] 和 [Bool] 上应用该函数，因此我必须解析两个尝试将 f 类型转换为 的上下文>[Int] -> [Int] 或 [Bool] -> [Bool]。我用 Rank2Types 解决了这个问题。但后来我在 f 等函数列表上使用 any ，并且 any 要求函数为 [a] -> [a ] 而不是 forall a。 [a] -> [a].

下面的代码虽然无意义，但却完美地重现了错误:

{-# LANGUAGE Rank2Types #-}

--debug :: (forall a. [a] -> [a]) -> Bool 
debug swap = any combine [swap]
  where
    combine :: (forall a. [a] -> [a]) -> Bool
    combine f =  usefonBool f && usefonInt f
    --usefonBool :: (forall a. [a] -> [a]) -> Bool
    usefonBool f = f [True,True] == [False]

    --usefonInt :: (forall a. [a] -> [a]) -> Bool
    usefonInt f = (f [1,2]) == [2,1]

错误信息是:

• Couldn't match type ‘a’ with ‘forall a1. [a1] -> [a1]’
  ‘a’ is a rigid type variable bound by
    the inferred type of debug :: a -> Bool
    at /path/debug.hs:(4,1)-(12,36)
  Expected type: a -> Bool
    Actual type: (forall a. [a] -> [a]) -> Bool
• In the first argument of ‘any’, namely ‘combine’
  In the expression: any combine [swap]
  In an equation for ‘debug’:
      debug swap
        = any combine [swap]
        where
            combine :: (forall a. [a] -> [a]) -> Bool
            combine f = usefonBool f && usefonInt f
            usefonBool f = f [True, ....] == [False]
            usefonInt f = (f [1, ....]) == [2, ....]
• Relevant bindings include
    swap :: a (bound at /path/debug.hs:4:7)
    debug :: a -> Bool (bound at /path/debug.hs:4:1)
|

我的目标是找到一个注释，让我可以在不同类型上使用 f，然后将任何类型应用于此类通用函数的列表。

如果我取消注释所有类型注释(或仅取消顶部注释)，错误将更改为

• Couldn't match type ‘[a0] -> [a0]’ with ‘forall a. [a] -> [a]’
  Expected type: ([a0] -> [a0]) -> Bool
    Actual type: (forall a. [a] -> [a]) -> Bool
• In the first argument of ‘any’, namely ‘combine’
  In the expression: any combine [swap]
  In an equation for ‘debug’:
      debug swap
        = any combine [swap]
        where
            combine :: (forall a. [a] -> [a]) -> Bool
            combine f = usefonBool f && usefonInt f
            usefonBool :: (forall a. [a] -> [a]) -> Bool
            usefonBool f = f [True, ....] == [False]
            ....
  |

Answer 1

首先，请注意 Rank2Types 是一个已弃用的名称。它相当于现代 GHC 中的 RankNTypes，并且这是扩展的首选名称。

这是根本问题。 “此类通用函数的列表”可以具有以下类型:

[forall a. [a] -> [a]]

遗憾的是，这不是有效的 Haskell 类型，因为 Haskell 不支持“命令多态性”。具体来说，程序如下:

{-# LANGUAGE RankNTypes #-}
myFunctions :: [forall a. [a] -> [a]]
myFunctions = [f1, f2]
   where f1 (x:y:rest) = y:x:rest
         f2 = reverse

产生错误消息:

DebugRank.hs:2:16: error:
    • Illegal polymorphic type: forall a. [a] -> [a]
      GHC doesn't yet support impredicative polymorphism
    • In the type signature: myFunctions :: [forall a. [a] -> [a]]

有一个扩展，ImpredicativeTypes。它很不稳定且不完整，但它允许编译以下内容:

{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE ImpredicativeTypes #-}

myFunctions :: [forall a. [a] -> [a]]
myFunctions = [f1, f2]
   where f1 (x:y:rest) = y:x:rest
         f2 = reverse

debug :: [forall a. [a] -> [a]] -> Bool
debug = any combine
  where
    combine :: (forall a. [a] -> [a]) -> Bool
    combine f = usefonBool f && usefonInt f
    usefonBool f = f [True,True] == [False]
    usefonInt  f = f [1,2] == [2,1]

main = print (debug myFunctions)

不过，我仍然建议不要使用它。

通常的替代方法是对多态函数使用 newtype 包装器:

newtype ListFunction = ListFunction (forall a. [a] -> [a])

这需要一些样板文件，但除了 RankNTypes 之外没有扩展:

myFunctions :: [ListFunction]
myFunctions = [ListFunction f1, ListFunction f2]
   where f1 (x:y:rest) = y:x:rest
         f2 = reverse

debug :: [ListFunction] -> Bool
debug = any combine
  where
    combine :: ListFunction -> Bool
    combine (ListFunction f) = usefonBool f && usefonInt f
    usefonBool f = f [True,True] == [False]
    usefonInt  f = f [1,2] == [2,1]

完整代码:

{-# LANGUAGE RankNTypes #-}

newtype ListFunction = ListFunction (forall a. [a] -> [a])

myFunctions :: [ListFunction]
myFunctions = [ListFunction f1, ListFunction f2]
   where f1 (x:y:rest) = y:x:rest
         f2 = reverse

debug :: [ListFunction] -> Bool
debug = any combine
  where
    combine :: ListFunction -> Bool
    combine (ListFunction f) = usefonBool f && usefonInt f
    usefonBool f = f [True,True] == [False]
    usefonInt  f = f [1,2] == [2,1]

main = print $ debug myFunctions