Haskell: type f a 到底是什么意思？

Question

我偶然发现了这段带有类型签名 :: (Foldable t, Num a) => t a -> (a, a) 的代码 fold ((,) <$> sum <*> product)，我完全迷失了。

我知道它是做什么的，但我不知道怎么做。所以我试图在 ghci 中将它分解成小块：

λ: :t (<$>)
(<$>) :: Functor f => (a -> b) -> f a -> f b
λ: :t (,)
(,) :: a -> b -> (a, b)
λ: :t sum
sum :: (Foldable t, Num a) => t a -> a

一切都很好，只是基本的东西。

λ: :t (,) <$> sum
(,) <$> sum :: (Foldable t, Num a) => t a -> b -> (a, b)

我又迷路了...

我看到有一些魔法将 t a -> a 变成了 f a，但它是如何完成的对我来说是个谜。（sum 甚至不是 Functor 的实例！）

我一直认为f a是某种盒子f，里面装着a，但看起来意思要深得多。

Answer 1

你例子中的仿函数f就是所谓的"reader functor"，定义如下：

newtype Reader r = Reader (r -> a)

当然，在 Haskell 中，这是为函数本地实现的，因此在运行时没有包装或解包。

相应的 Functor 和 Applicative 实例如下所示：

instance Functor f where
  fmap :: (a -> b) -> (r -> a)_-> (r -> b)
  fmap f g = \x -> f (g x) -- or: fmap = (.)

instance Applicative f where
  pure :: a -> (r -> a) -- or: a -> r -> a
  pure x = \y -> x -- or: pure = const
  (<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
  frab <*> fra = \r -> frab r (fra r)

在某种程度上，reader 仿函数也是一个 "box"，就像所有其他仿函数一样，具有生成类型 a 的上下文 r。

那么让我们看看(,) <$> sum:

:t (,) :: a -> b -> (a, b)
:t fmap :: (d -> e) -> (c -> d) -> (c -> e)
:t sum :: Foldable t, Num f => t f -> f

我们现在可以将 d 类型特化为 a ~ f，将 e 特化为 b -> (a, b)，将 c 特化为 t f。现在我们得到：

:t (<$>) -- spcialized for your case
:: Foldable t, Num f => (a -> (b -> (a, b))) -> (t f -> f) -> (t f -> (b -> (a, b)))
:: Foldable t, Num f => (f -> b -> (f, b)) -> (t f -> f) -> (t f -> b -> (f, b))

应用函数：

:t (,) <$> sum
:: Foldable t, Num f => (t f -> b -> (f, b))

这正是 ghc 所说的。

Answer 2

简短的回答是 f ~ (->) (t a)。要了解原因，只需稍微重新排列 sum 的类型签名，使用 -> 作为前缀运算符而不是中缀运算符。

sum :: (Foldable t, Num a) => (->) (t a) a
                              ~~~~~~~~~~
                                  f

一般来说，(->) r 是任何参数类型的函子 r。

instance Functor ((->) r) where
    fmap = (.)

通过将 ((->) r) 插入 f 的 fmap 类型，很容易证明 (.) 是 fmap 的唯一可能实现：

fmap :: (a -> b) -> f a -> f b
     :: (a -> b) -> ((->) r) a -> ((->) r) b
     :: (a -> b) -> (r -> a) -> (r -> b)

这是组合的类型签名，组合是具有此类型签名的唯一函数。

由于 Data.Functor 将 <$> 定义为 fmap 的中缀版本，我们有

(,) <$> sum == fmap (,) sum
            == (.) (,) sum

从这里开始，确认结果类型确实是 (Foldable t, Num a) => t a -> b -> (a, b) 是一项相对简单但乏味的工作。我们有

(b' -> c') -> (a' -> b') -> (a' -> c')  -- composition
b' -> c' ~ a -> b -> (a,b)              -- first argument (,)
a' -> b' ~ t n -> n                     -- second argument sum
----------------------------------------------------------------
a' ~ t n
b' ~ a ~ n
c' ~ a -> b -> (a,b)
----------------------------------------------------------------
a' -> c' ~ t a -> b -> (a,b)

Haskell: type f a 到底是什么意思？

Haskell: What does type f a actually mean?

haskell

functor