为此数据类型定义仿函数实例

Question

我正在尝试为数据类型 Terms 定义仿函数实例，它看起来像：

data Terms a = Var a | App (Terms a) (Terms a) | Abs (Terms (Maybe a)) 
                     | Const Integer | Add (Terms a) (Terms a) 
                     | IfZero (Terms a) (Terms a) (Terms a) | Y
deriving (Show,Eq)

但是，我在 Abs 的情况下遇到了问题。

我的定义目前是这样的：

instance Functor Terms where
    fmap f (Var x) = Var (f x)
    fmap f (App t1 t2) = App (fmap f t1) (fmap f t2)
    fmap f (Abs t) = Abs (fmap f t)
    fmap f (Const n) = Const n
    fmap f (Add t1 t2) = Add (fmap f t1) (fmap f t2)
    fmap f (IfZero t1 t2 t3) = IfZero (fmap f t1) (fmap f t2) (fmap f t3)
    fmap f Y = Y

我尝试了几种不同的方法来绕过 Maybe 以便将函数应用于该术语，但有些事情我不太明白。我知道 Maybe 类型本身就是一个函子，这意味着 fmap 应该自动处理它，我只是不确定如何解决它不能 return 作为 Maybe.

Answer 1

是 Maybe 本身就是一个函子，因此它有 它自己的 fmap:

    fmap f (Abs t) = Abs (fmap₁ (fmap₂ f) t)

-- t               :: Terms (Maybe a)
--              f  ::              a  ->              b
--        fmap₂ f  ::        Maybe a  ->        Maybe b
-- fmap₁ (fmap₂ f) :: Terms (Maybe a) -> Terms (Maybe b)

下标索引不是代码的一部分，仅用于说明目的。或者我们可以用TypeApplications来区分它们：

*Main> :set -XTypeApplications
*Main> fmap @Maybe (+1) $ Just 7
Just 8
*Main> fmap @Terms (+1) $ Abs $ Var $ Just 8
Abs (Var (Just 9))

但这里不需要它们，普通的 fmaps 也可以工作——Haskell 根据参数的类型知道应用哪个：

*Main> fmap (+1) $ Just 7
Just 8
*Main> fmap (+1) $ Abs $ Var $ Just 8
Abs (Var (Just 9))

Answer 2

错误来自这一行：

fmap f (Abs t) = Abs (fmap f t)

Abs包含一个Maybe (Term a)，你想得到一个Maybe (Term b)，但是f的类型是a -> b。因此，当您尝试 fmap 它时，您将 Term a 传递给接受 a 的函数。显然这是行不通的。相反，使用 fmap f 创建 Term a -> Term b，然后 fmap （创建双 fmap）：

fmap f (Abs t) = Abs (fmap (fmap f) t)

Answer 3

另一种选择是通过将 Terms (Maybe a) 转换为 Scoped Terms a 将复合结构移动到数据类型中。您的 Functor Terms 实例保持不变。

相反，组合发生在 Functor (Scoped exp) 中，通过 exp 和 Maybe (Compose exp Maybe) 的组合派生。这就是 fmap = fmap . fmap 的派生方式（模新类型包装）。

{-# Language DerivingVia #-}

type    Scoped :: (Type -> Type) -> (Type -> Type)
newtype Scoped exp a = Scoped (exp (Maybe a))
  deriving (Functor, Applicative, Alternative, Foldable, Arbitrary1, ..)
  via Compose exp Maybe

这是 Edward Kmett 的 bound 图书馆采用的方法。

Bound.Scope.Scope:

type    Scope :: Type -> (Type -> Type) -> (Type -> Type)
newtype Scope bound exp free = Scope (exp (Var bound (exp free)))

Bound.Scope.Simple.Scope:

type    Scope :: Type -> (Type -> Type) -> (Type -> Type)
newtype Scope bound exp free = Scope (exp (Var bound free))

其中 Var = Either:

type Var :: Type -> Type -> Type
data Var bound free
  = B bound -- this is a bound variable
  | F free  -- this is a free variable

为此数据类型定义仿函数实例

Defining a functor instance for this datatype

haskell

functor