haskell 函子示例(新类型Mu f = InF {outF::f(μ f)})

vddsk6oq  于 2022-11-14  发布在  其他
关注(0)|答案(4)|浏览(116)

这把我难住了。如何为newtype Mu f = InF {outF :: f (Mu f)}编写一个Functor示例

83qze16e

83qze16e1#

You can't. In order to define an instance Functor c for some c , c must be of the kind * -> * . So in your case, Mu should have been of that kind, which means that its argument f must have been of the kind * . But clearly this is not the case, as you are applying f to something else (to Mu f ).
To put it more simply, if Mu was a functor, you could use fmap on values of type Mu f for any f . But this would have allowed you to change the type parameter to any other type, e.g., by applying the function fmap (const (0 :: Int)) to any Mu f value, it would have to return a Mu Int value. But you can not form such a value because the outF of that value would have had type Int (Mu Int) which does not make sense.

carvr3hs

carvr3hs2#

redneb很好地解释了为什么Mu不能是正则Functor,但是可以为Mu实现一种类似于函子的Map操作,如下所示

  1. {-# LANGUAGE RankNTypes #-}
  2. newtype Mu f = InF {outF :: f (Mu f)}
  3. mumap :: Functor f => (forall a. f a -> g a) -> Mu f -> Mu g
  4. mumap f (InF m) = InF $ f $ fmap (mumap f) m

虽然我不确定它对你的情况有多有用。:)

ymdaylpp

ymdaylpp3#

与user2297560的不同,对Mu进行轻微的重新措辞,就足以允许Mu的函子示例:

  1. -- Natural transformations
  2. type g ~> h = forall a. g a -> h a
  3. class HFunctor f where
  4. ffmap :: Functor g => (a -> b) -> f g a -> f g b
  5. hfmap :: (Functor g, Functor h) => (g ~> h) -> (f g ~> f h)
  6. newtype Mu f a = In { unIn :: f (Mu f) a }
  7. instance HFunctor f => Functor (Mu f) where
  8. fmap f (In r) = In (ffmap f r)

这个公式来自Patricia和Neil的论文Haskell Programming with Nested Types: A Principled Approach

euoag5mw

euoag5mw4#

正如redneb所描述的,一个函子示例必须有* -> *类型,这就禁止了Mu是一个函子,假设它的参数f被应用于f (Mu f)中的一个参数。
这里有一个涉及到的各种类型的分类。
首先,要创建的新类型在应用了所有参数之后必须具有kind *。因此:
Mu f必须具有*种类
第二,Mu f被设置为等于的东西也必须具有相同的类型。也就是说,
InF { outF :: f (Mu f) }必须具有*种类
第三,outF是一个函数,因此必须返回一个完全实现的类型,无论是参数化的还是具体的,即*类型。f (Mu f)是它的返回类型。因此
f (Mu f)必须具有*种类
最后,f是一个应用类,因为它出现在f (Mu f)中,换句话说,它有类f_argument_kind -> f_result_kind,它有类f_argument_kind和类f_result_kind,而且f (Mu f)告诉我们f_argument_kindf_result_kind的类,也就是说,f_argument_kindMu f的种类(*)匹配,并且f_result_kindf (Mu f)的种类(*)匹配。
f的种类为* -> *
将其与已知类型的Mu f*)结合,我们得到类型构造函数的类型。
Mu的种类为(* -> *) -> *

相关问题