解析"f = f(< *)" pure的类型 [英] Resolving the type of `f = f (<*>) pure`

问题描述

最近我注意到liftA可以写成

liftA (<*>) pure

我认为这很整洁，所以开个玩笑，我想我会基于此属性为liftA做出新的定义":

f = f (<*>) pure

现在，我曾希望这与从未停止过的liftA具有相同的类型.但是它无法编译.

• Occurs check: cannot construct the infinite type:
    t ~ (f (a -> b) -> f a -> f b) -> (a1 -> f1 a1) -> t
• In the expression: f (<*>) pure
  In an equation for ‘f’: f = f (<*>) pure
• Relevant bindings include
    f :: (f (a -> b) -> f a -> f b) -> (a1 -> f1 a1) -> t
      (bound at liftA.hs:2:1)

这似乎很明智，我知道编译器有问题.但是，事情变得有些奇怪，因为当我添加注释时:

f :: Applicative f => (a -> b) -> f a -> f b
f = f (<*>) pure

它突然编译.

现在，我最初的怀疑是，我注释f的类型不是最通用的类​​型，并且通过限制类型使我可以统一事物.但是，从类型上看，似乎不是我的类型比编译器试图派生的类型更通用的情况.

这是怎么回事?我在这里不太了解，但是我对编译器在每种情况下的想法以及为什么它在一种情况下却在另一种情况下遇到问题感到好奇.

解决方案

混淆是由Haskell的类型类以及function-from-fixed-type是Applicative的实例(又称为阅读器monad)引起的.如果使用专门的版本写出来，它将变得更加清晰:

type Reader a b = a -> b

fmapFn :: (a -> b) -> Reader c a -> Reader c b
fmapFn = fmap
    -- ≡ liftA
    -- ≡ (.)

fmap' :: Applicative f => (a -> b) -> f a -> f b
fmap' = fmapFn (<*>) pure
      ≡ (<*>) . pure
      ≡ \φ -> (<*>) (pure φ)
      ≡ \φ fa -> pure φ <*> fa

这时需要适用法律

fmap f x = pure f <*> x

如此

 fmap' ≡ \φ fa -> fmap φ fa
       ≡ fmap

duh .但是要点是，在定义fmap' = fmap' (<*>) pure中，(<*>)和pure属于函子，您希望该函子最终适用于该函子，但是fmap'您实际上是在使用始终属于函数函子.在Haskell中没关系:毕竟 定义是多态的，因此，如果顶层知道如何对 all 函子执行此操作，那么您当然也可以将其用于函数函子. (不考虑由于循环依赖而导致的非终止问题...) 但是，因为您以fmap' = ...形式定义它，所以 单态限制中:如果您在顶层编写不带签名的fmap' = fmap' (<*>) pure，编译器将尝试找到一个应该对其工作的具体类型，尤其是单个具体的仿函数.但是，无论您选择哪种具体类型，都将与尝试使用自己的fmapFn类型不同.因此，此定义仅使用带有显式签名的编译器强制其为多态(或者使用-XNoMonomorphismRestriction标志，这会导致编译器在没有显式指令的情况下选择多态类型).. >

^EDIT 令人惊讶的是，试图使类型的多态性比必要的少的不是 单态性限制.为了弄清楚它是什么，让我们尝试找到一个具有相同问题的简单示例.第一次尝试:

fromFloat :: RealFrac a => Float -> a
toFloat :: RealFrac a => a -> Float
fromFloat = realToFrac
toFloat   = realToFrac

s = fromFloat . s . toFloat

(我选择了Float，因为它不是编译器可以自行选择的default类型.)
结果证明该编译很好，但不是最通用的类​​型

s' :: (RealFrac a, RealFrac b) => a -> b
s' = fromFloat . s' . toFloat

它只是简单一些

s :: Float -> Float

...无论是否启用了同构限制. 为什么?我不知道；我会问这个有趣的问题.

Recently I noticed that humourously liftA can be written as

liftA (<*>) pure

I thought this was neat and so as a bit of a joke I thought I would make a new "definition" of liftA based on this property:

f = f (<*>) pure

Now I had expected that this would be something of the same type as liftA that just never halted. However it fails to compile.

• Occurs check: cannot construct the infinite type:
    t ~ (f (a -> b) -> f a -> f b) -> (a1 -> f1 a1) -> t
• In the expression: f (<*>) pure
  In an equation for ‘f’: f = f (<*>) pure
• Relevant bindings include
    f :: (f (a -> b) -> f a -> f b) -> (a1 -> f1 a1) -> t
      (bound at liftA.hs:2:1)

This seems sensible, I see how the compiler has an issue. However things get a little weird because when I add an annotation:

f :: Applicative f => (a -> b) -> f a -> f b
f = f (<*>) pure

It suddenly compiles.

Now my initial suspicion was that the type I was annotating f with was not the most general type and that by restricting the type I had made it possible to unify things. However looking at the types this doesn't seem to be the case my type seems to be more general than the type that the compiler was trying to derive.

What is going on here? I am a bit out of my depth here but I am curious as to what the compiler is thinking in each scenario and why it encounters an issue in one but not the other.

解决方案

The confusion is caused by Haskell's type classes and the fact that functions-from-fixed-type are an instance of Applicative (aka the reader monad). It becomes clearer if you write it out with specialised version:

type Reader a b = a -> b

fmapFn :: (a -> b) -> Reader c a -> Reader c b
fmapFn = fmap
    -- ≡ liftA
    -- ≡ (.)

fmap' :: Applicative f => (a -> b) -> f a -> f b
fmap' = fmapFn (<*>) pure
      ≡ (<*>) . pure
      ≡ \φ -> (<*>) (pure φ)
      ≡ \φ fa -> pure φ <*> fa

And at this point it requires the applicative law

fmap f x = pure f <*> x

so

 fmap' ≡ \φ fa -> fmap φ fa
       ≡ fmap

duh. But the point is, in the definition fmap' = fmap' (<*>) pure, the (<*>) and pure belong to the functor for which you want this to eventually work, but the fmap' you're using actually always belongs to the function functor. That's ok in Haskell: the definition is polymorphic after all, so if the top-level knows how to do this for all functors then you can certainly also use it for the function functor. (Leaving aside the issue of nontermination due to circular dependency...) However, because you're defining it in the form fmap' = ..., the monomorphism restriction kicks in: if you write fmap' = fmap' (<*>) pure without signature at the top-level, the compiler tries to find a concrete type for which this should work, in particular a single, concrete functor. But whatever concrete type you choose, this will then be a different type from the fmapFn that you're trying to use yourself. So, this definition only compiles with an explicit signature that forces it to be polymorphic (or alternatively, with the -XNoMonomorphismRestriction flag, which causes the compiler to pick the polymorphic type without explicit instruction).

^EDIT Surprisingly it turns out it is not the monomorphism restriction what tries to make the type less polymorphic than necessary. To figure out what it is, let's try to find a simpler example with the same problem. First attempt:

fromFloat :: RealFrac a => Float -> a
toFloat :: RealFrac a => a -> Float
fromFloat = realToFrac
toFloat   = realToFrac

s = fromFloat . s . toFloat

(I chose Float because it's not a default type that the compiler might pick by itself.)
Turns out this compiles just fine, but instead of the most general type

s' :: (RealFrac a, RealFrac b) => a -> b
s' = fromFloat . s' . toFloat

it just picks up the simpler

s :: Float -> Float

...regardless of whether the monomorphism restriction is enabled. Why? I don't know; I'd find this an interesting question to ask.

这篇关于解析"f = f(< *)" pure的类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！