haskell - 如何在镜头式单片库中为更高种类的类型实现孔和上下文？

AndrásKovács提出了这个问题in response to an answer to a previous question.

在镜头风格的单板库中，用于基于类的* -> *类型的类型

class Uniplate1 f where
    uniplate1 :: Applicative m => f a -> (forall b. f b -> m (f b)) -> m (f a)

类似于类*类型的类

class Uniplate on where
    uniplate :: Applicative m => on -> (on -> m on) -> m on

是否有可能实现contexts和holes的类似物，它们都具有Uniplate on => on -> [(on, on -> on)]类型，而无需Typeable1？

显然，这可以在单板库的旧样式中实现，该库使用Str表示数据结构，方法是返回带有子类型类型列表的结构。

孔可由以下数据类型表示，它将替换(on, on -> on)和contexts的签名中的holes

data Hole f a where
    Hole :: f b -> (f b -> f a) -> Hole f a

holes :: Uniplate1 f => f a -> [Hole f a]
...

但是，尚不清楚是否有不需要holes的Typeable1实现。

最佳答案

建议的类型Hole不必要地限制了函数的返回类型。以下类型可以表示以前Hole所表示的所有内容，以及更多信息，而不会丢失任何类型信息。

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE GADTs #-}

data Hole f a where
    Hole :: f b -> (f b -> a) -> Hole f a

如果需要返回类型为f a，则可以使用Hole f (f a)表示它。由于我们将大量使用Hole，因此拥有一些实用程序功能会很好。因为Hole中函数的返回类型不再受f中的约束，所以我们可以为其创建Functor实例

instance Functor (Hole f) where
    fmap f (Hole b g) = Hole b (f . g)

通过用contexts1替换单板库的Hole中元组的构造函数，可以为每种版本的contexts编写Hole:

contexts1 :: Uniplate1 f => f a -> [Hole f (f a)]
contexts1 x = Hole x id  : f (holes1 x)
    where
        f xs = [ Hole y (ctx . context)
               | Hole child ctx <- xs
               , Hole y context <- contexts1 child]

holes1比较棘手，但是仍然可以通过修改holes库中的uniplate来制作。它需要使用Replace1而不是元组的新Applicative Functor Hole。每次元组的第二个字段都被second (f .)修改，我们将fmap f替换为Hole。

data Replace1 f a = Replace1 {replaced1 :: [Hole f a], replacedValue1 :: a}

instance Functor (Replace1 f) where
    fmap f (Replace1 xs v) = Replace1 (map (fmap f) xs) (f v)

instance Applicative (Replace1 f) where
    pure v = Replace1 [] v
    Replace1 xs1 f <*> Replace1 xs2 v = Replace1 (ys1 ++ ys2) (f v)
        where ys1 = map (fmap ($ v)) xs1
              ys2 = map (fmap (f)) xs2

holes1 :: Uniplate1 f => f a -> [Hole f (f a)]
holes1 x = replaced1 $ descendM1 (\v -> Replace1 [Hole v id] v) x

decendM1在the preceding answer中定义。 Replace和Replace1可以统一；示例后将介绍如何执行此操作。

让我们根据上一个问题中的代码尝试一些示例。以下对Hole的实用程序功能将很有用。

onHole :: (forall b. f b -> c) -> Hole f a -> c
onHole f (Hole x _) = f x

inHole :: (forall b. f b -> f b) -> Hole f a -> a
inHole g (Hole x f) = f . g $ x

例子

基于上述问题的代码，我们将使用以下示例数据和函数:

example = If (B True) (I 2 `Mul` I 3) (I 1)

zero :: Expression b -> Expression b
zero x = case x of
    I _ -> I 0
    B _ -> B False
    Add _ _ -> I 0
    Mul _ _ -> I 0
    Eq  _ _ -> B False
    And _ _ -> B False
    Or  _ _ -> B False
    If  _ a _ -> zero a

孔洞

sequence_ . map (onHole print) . holes1 $ example

B True
Mul (I 2) (I 3)
I 1

语境

sequence_ . map (onHole print) . contexts1 $ example

If (B True) (Mul (I 2) (I 3)) (I 1)
B True
Mul (I 2) (I 3)
I 2
I 3
I 1

替换每个上下文

sequence_ . map print . map (inHole zero) . contexts1 $ example

I 0
If (B False) (Mul (I 2) (I 3)) (I 1)
If (B True)  (I 0)             (I 1)
If (B True)  (Mul (I 0) (I 3)) (I 1)
If (B True)  (Mul (I 2) (I 0)) (I 1)
If (B True)  (Mul (I 2) (I 3)) (I 0)

统一更换

可以重构Replace Applicative Functor，以便它不知道Uniplate或Uniplate1的孔类型，而只知道该孔是Functor。 Uniplate的孔使用(on, on -> a)类型，本质上使用fmap f = second (f .)；这是(on, )和on->仿函数的组成。

而不是从转换器库中获取Compose，我们将为Hole的Uniplate创建新的类型，这将使​​此处的示例代码更加一致和独立。

data Hole on a = Hole on (on -> a)

instance Functor (Hole on) where
    fmap f (Hole on g) = Hole on (f . g)

我们将从前面将Hole重命名为Hole1。

data Hole1 f a where
    Hole1 :: f b -> (f b -> a) -> Hole1 f a

instance Functor (Hole1 f) where
    fmap f (Hole1 b g) = Hole1 b (f . g)

Replace可以删除所有关于孔类型的知识。

data Replace f a = Replace {replaced :: [f a], replacedValue :: a}

instance Functor f => Functor (Replace f) where
    fmap f (Replace xs v) = Replace (map (fmap f) xs) (f v)

instance Functor f => Applicative (Replace f) where
    pure v = Replace [] v
    Replace xs1 f <*> Replace xs2 v = Replace (ys1 ++ ys2) (f v)
        where ys1 = map (fmap ($ v)) xs1
              ys2 = map (fmap (f)) xs2

holes和holes1都可以根据新的Replace实现。

holes :: Uniplate on => on -> [Hole on on]
holes x = replaced $ descendM (\v -> Replace [Hole v id] v) x

holes1 :: Uniplate1 f => f a -> [Hole1 f (f a)]
holes1 x = replaced $ descendM1 (\v -> Replace [Hole1 v id] v) x

关于haskell - 如何在镜头式单片库中为更高种类的类型实现孔和上下文？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25393870/