在镜片样式uniplate库中，如何实现孔和上下文对于更高级的类型？ [英] How can holes and contexts be implemented for higher-kinded types in a lens style uniplate library?

问题描述

AndrásKovács提出了这个问题：回答了上一个问题的答案。

在类型为 * - >的透镜式uniplate库中， * 基于类

  class Uniplate1 f其中
 uniplate1 :: Applicative m = > f a  - > （全部b·f b→m（f b））→> m（fa）
  

类似于类型类的类 * < code



  class Uniplate on 
 uniplate :: Applicative m =>在 - > （on  - > m on） - > m 
  

是否可以实现类似于上下文和 holes ，它们的类型都是 Uniplate on =>在 - > [（on，on - > on）] 不需要 Typeable1 ？

很显然，这可以在使用 Str 的uniplate库的旧式实现中通过返回一个具有类型级别列表的结构来表示数据结构

一个洞可以用下面的数据类型表示，它可以代替（on，on - > on） 上下文和孔


$ b的签名 $ b

 数据孔fa其中
 Hole :: fb  - > （f b  - > f a） - > Hole f a 
 
 holes :: Uniplate1 f => f a  - > [Hole fa] 
 ... 
  

然而，目前还不清楚是否有一个实施 holes 不需要 Typeable1 。

解决方案

建议的类型 Hole 在函数的返回类型中是不必要的限制。以下类型可以表示前 Hole 所代表的所有内容，并且不会丢失任何类型信息。

<$ p $
$ {$＃$} b
$ - $ L $ $ $ $ ; （f b - > a） - >如果我们需要一个返回类型 fa

c $ c>，我们可以使用 Hole f（fa）来表示它。由于我们会使用 Hole 很多，所以有一些实用功能会很好。因为 Hole 中函数的返回类型不再局限于 f 中，所以我们可以使 Functor >

  instance Functor（Hole f）其中
 fmap f（Hole bg）= Hole b（f。g）
  

contexts1通过替换uniplate库的上下文中元组的构造函数，可以为 Hole 版本写入 with Hole ：

  contexts1 :: Uniplate1 f => f a  - > [Hole f（f a）] 
 contexts1 x = Hole x id：f（holes1 x）
其中
 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 fa = Replace1 {replaced1 :: [Hole fa] ，replaceValue1 :: a} 
 
实例Functor（Replace1 f）其中
 fmap f（Replace1 xs v）= Replace1（map（fmap f）xs）（fv）
 
实例Applicative（Replace1 f）其中
 pure v = Replace1 [] v 
 Replace1 xs1 f * Replace1 xs2 v = Replace1（ys1 ++ ys2）（fv）
其中ys1 = map（fmap（$ v））xs1 
 ys2 = map（fmap（f））xs2 
 
 holes1 :: Uniplate1 f => f a  - > [Hole f（fa）] 
 holes1 x = replaced1 $ descendM1（\v  - > Replace1 [Hole v id] v）x 
  

decendM1 在前面的答案。 替换和 Replace1 可以统一;如何做到这一点在后面的例子中描述。

让我们按照上一个问题的代码尝试一些例子。 Hole s中的以下实用函数将很有用。

  onHole： ：（全部b。fb→c）→>孔f a  - > c 
 onHole f（Hole x _）= f x 
 
 inHole ::（全部b。f b  - > f b） - >孔f a  - > （洞x f）= f中的
。 g $ x 
  

例子

我们将根据前面问题的代码使用以下示例数据和函数：

  example = If（B True）（ I 2`Mul` I 3）（I 1）
 
 zero ::表达式b  - >表达式b 
 zero x = case x of 
 I _  - > I 0 
 B _  - > B False 
 Add _ _  - > I 0 
 Mul _ _  - > I 0 
 Eq _ _  - > B假
和_ _  - > B False 
或_ _  - > B假
如果_ a _  - >零a 
  

空洞

  sequence_。地图（onHole打印）。 hole1 $示例
 
 B真
 Mul（I 2）（I 3）
 I 1 
  

上下文

  sequence_。地图（onHole打印）。如果（B真）（Mul（I 2）（I 3））（I 1）
 B真
 Mul（I 2）（I 3） 
 I 2 
 I 3 
 I 1 
  

替换每个上下文

  sequence_。地图打印。地图（inHole零）。 （B真）（I 0）（I 0）（I 3））（I 1）
如果（B真）（I 0）（I 1）
 $ b I 0 
如果（I 1）
如果（B真）（Mul（I 0）（I 3））（I 1）
 If 1）
如果（B真）（Mul（I 2）（I 3））（I 0）
  

Unifying Replace

Replace Applicative Functor 可以重构，以便它不知道 Uniplate 或<$ c的孔类型$ c> Uniplate1 ，而是只知道这个洞是 Functor 。针对 Uniplate 的洞号使用类型（on，on - > a），并且基本上使用 fmap f = second（f。）;这是（on，）和 on-> 函子的组成。

不是从变形库中抓取 Compose ，而是为 Hole Uniplate ，这将使这里的示例代码更加一致并且自成体系。

<$ p $ （上 - > a）

实例Functor（Hole on）其中
fmap f（Hole on g）= Hole （f。g）

我们将重命名 Hole 从前到 Hole1 。

 数据Hole1 fa where 
 Hole1 :: fb  - > （f b  - > a） - >孔1 fa 
 
实例Functor（Hole1 f）其中
 fmap f（Hole1 bg）= Hole1 b（f。g）
  

$ b

替换可以删除任何类型洞的所有知识。

  data替换fa = Replace {replaced :: [fa]，replacedValue :: a} 
 
实例Functor f => Functor（替换f）其中
 fmap f（替换xs v）=替换（map（fmap f）xs）（f v）
 
实例Functor f => Applicative（替换f）其中
 pure v = Replace [] v 
替换xs1 f *替换xs2 v =替换（ys1 ++ ys2）（fv）
其中ys1 = map（fmap（$ v））xs1 
 ys2 = map（fmap（f））xs2 
  

孔和 holes1 可以用新的替换。

  holes :: Uniplate on =>在 - > [打开的孔] 
孔x =替换$ descendM（\v  - >替换[Hole v id] v）x 
 
 holes1 :: Uniplate1 f => f a  - > [Hole1 f（fa）] 
 holes1 x =替换$ descendM1（\v  - >替换[Hole1 v id] v）x 
  




András Kovács proposed this question in response to an answer to a previous question.

In a lens-style uniplate library for types of kind * -> * based on the class

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

analogous to the class for types of kind *

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

is it possible to implement analogs to contexts and holes, which both have the type Uniplate on => on -> [(on, on -> on)] without requiring Typeable1?

It's clear that this could be implemented in the old-style of the uniplate library which used Str to represent the structure of the data by returning a structure with a type-level list of the types of the children.

A hole could be represented by the following data type, which would replace (on, on -> on) in the signatures for contexts and holes

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

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

However, it is unclear if there is an implementation for holes which doesn't require Typeable1.

解决方案

The suggested type Hole is needlessly restrictive in the return type of the function. The following type can represent everything the former Hole represents, and more, without loss of any type information.

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

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

If we need to have a return type of f a, we can use Hole f (f a) to represent it. Since we will be using Holes a lot, it'd be nice to have a few utility functions. Because the return type of the function in Hole is no longer constrained to be in f, we can make a Functor instance for it

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

contexts1 can be written for either version of Hole by replacing the constructors for tuples in the uniplate library's contexts with 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 is trickier, but can still be made by modifying holes from the uniplate library. It requires a new Replace1 Applicative Functor that uses Hole instead of a tuple. Everyhwere the second field of the tuple was modified by second (f .) we replace with fmap f for the 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 is defined in the preceding answer. Replace and Replace1 can be unified; how to do so is described after the examples.

Let's try some examples in terms of the code in the previous question. The following utility functions on Holes will be useful.

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

Examples

We'll use the following example data and function, based on the code from the preceding questions:

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

Holes

sequence_ . map (onHole print) . holes1 $ example

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

Contexts

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

Replacement of each context

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)

Unifying Replace

The Replace Applicative Functor can be refactored so that it doesn't know about the type of holes for either Uniplate or Uniplate1, and instead only knows that the hole is a Functor. Holes for Uniplate were using the type (on, on -> a) and essentially using fmap f = second (f .); this is the composition of the (on, ) and on-> functors.

Instead of grabbing Compose from the transformers library, we'll make a new type for a Hole for Uniplate, which will make the example code here be more consistent and self-contained.

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

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

We'll rename our Hole from before to 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 can drop all knowledge of either type of hole.

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

Both holes and holes1 can be implemented in terms of the new 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

这篇关于在镜片样式uniplate库中，如何实现孔和上下文对于更高级的类型？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！