在Monad返回多态值

今天在写一个parser，其中要解析整数和小数，想直接用parsec里的naturalOrFloat :: Parser (Either Integer Double)，但它不处理正负号，我要自己加上对正负号的解析。

我第一个想法就是遇到负号返回negate :: Num a => a -> a，正号或没用就返回id，然后作用在naturalOrFloat的结果上：

{-# LANGUAGE RankNTypes          #-}
{-# LANGUAGE ScopedTypeVariables #-}

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Token (naturalOrFloat)
import Text.ParserCombinators.Parsec.Language (haskell)

-- | 解析符号，返回符号函数
parseSign :: Num a => Parser (a -> a)
parseSign = (char '-' >> return negate)
        <|> (char '+' >> return id)
        <|> (return id)

-- | 应用符号函数
applySign :: (forall a. Num a => a -> a)
             -> (Either Integer Double) -> (Either Integer Double)
applySign f (Left  i) = Left  (f i)
applySign f (Right d) = Right (f d)

-- | 解析数值
parseNumber :: Parser (Either Integer Double)
parseNumber = do
    sign <- parseSign
    num  <- naturalOrFloat haskell
    return $ applySign sign num

但是，GHC说类型错误，因为applySign需要一个多态函数，而parseSign返回的是个单态的函数。所以parseSign的类型应该是：Parser (forall a. Num a => a -> a)，就是标题所说，要在Monad返回多态值。

自己折腾一番之后，到群上问了一下，@阅千人而惜知己指出这在Hindley–Milner类型系统是不行的，还给出了王垠的一篇相关的文章，在那篇文章有提到first-class polymorphism，google一下发现GHC也支持(通过ImpredicativeTypes扩展)，不过类型推导不了，要自己写类型：

{-# LANGUAGE RankNTypes          #-}
{-# LANGUAGE ImpredicativeTypes  #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE LiberalTypeSynonyms #-}

parseSign :: Parser (forall a. Num a => a -> a)
parseSign = (char '-' >> return' negate)
        <|> (char '+' >> return' id)
        <|> (return' id)
  where
    -- 返回多态值的return
    return' = return :: Monad m => (forall a. Num a => a -> a)
                                -> m (forall a. Num a => a -> a)

parseNumber = do
    (sign :: forall a. Num a => a -> a) <- parseSign
    num <- naturalOrFloat haskell
    return $ applySign sign num

Impredicative types可以让全称量词出现在类型的任意位置，甚至可以在数据类型里。

因为return'的类型很长，而且模式很明显，所以还可以抽象出来：

{-# LANGUAGE ConstraintKinds #-}

type Poly c f = forall a. c a => f a

type PolyReturn c f = Monad m => (Poly c f) -> m (Poly c f)

type Endo a = (a -> a)

returnNumEndo :: PolyReturn Num Endo
returnNumEndo = return

参数化多态

维基百科Parametric polymorphism说参数化多态可以分为：

• predicative: 类型参数不能实例化多态类型
• impredicative: 类型参数能实例化多态类型

Impredicative是自指（self-referential）的意思，impredicative type说一个多态类型的类型参数能实例化成多态类型。

根据rank（我理解为嵌套的->层数）：

• rank-1: 量词只能在类型的最外层
• rank-k: 对于固定的k，量词最多能在第k层
• rank-n: 量词能在任意层