可访问上下文数据的折叠索引仿函数

Question

这是一道遍历相互递归数据类型的题。我正在使用 Indexed Functor 为一堆相互递归的数据类型建模 AST，如本要点 here 中所述。这足以满足我的预期目的。

现在我需要转换我的数据结构，使数据自上而下流动。是一个在 Functor 上下文中提出的 SoF 问题，其中显示代数的载体可以是一个允许在遍历期间向下推送数据的函数。但是，我正在努力将这种技术与 Indexed Functor 一起使用。我认为我的数据类型需要更改，但我不确定如何更改。

这里有一些代码可以说明我的问题。请注意，我不包括相互递归类型或多个索引，因为我不需要它们来说明问题。

setDepth 应将每个 (IntF n) 更改为 (IntF depth)。编写的函数不会进行类型检查，因为种类“AstIdx -> *”与“Int -> Expr ix”不匹配。也许我遗漏了一些东西，但我看不出有什么方法可以解决这个问题而不放宽 f 的种类以减少 IxFunctor 中的限制，但这似乎是错误的。

欢迎任何想法、建议或指点！

{-# LANGUAGE PolyKinds #-}

infixr 5 ~>

type f ~> g = forall i. f i -> g i

class IxFunctor (f :: (k -> *) -> k -> *) where
  imap :: (a ~> b) -> (f a ~> f b)

-- Indexed Fix
newtype IxFix f ix = IxIn {ixout :: f (IxFix f) ix}

-- Fold
icata :: IxFunctor f => (f a ~> a) -> (IxFix f ~> a)
icata phi = phi . imap (icata phi) . ixout

-- Kinds of Ast
data AstIdx = ExprAst | TypeAst

-- AST
data ExprF (f :: AstIdx -> *) (ix :: AstIdx) where
  IntF :: Int -> ExprF f ExprAst
  AddF :: f ExprAst -> f ExprAst -> ExprF f ExprAst

type Expr = IxFix ExprF

instance IxFunctor ExprF where
  imap f (IntF n) = IntF n
  imap f (AddF a b) = AddF (f a) (f b)

-- Change (IntF n) to (IntF (n + 1)).
add1 :: Expr ix -> Expr ix
add1 e = icata go e
  where
    go :: ExprF Expr ix -> Expr ix
    go (IntF n) = IxIn (IntF (n + 1))
    go (AddF a b) = IxIn (AddF a b)

{-
-- Change (IntF n) to (IntF depth)
-- Doesn't type check
setDepth :: Expr ix -> Expr ix
setDepth e = icata ((flip go) 0) e
  where
    --  byDepthF :: TreeF a (Integer -> Tree Integer) -> Integer -> Tree Integer
    --  byDepthF :: TreeF a (Integer -> Tree Integer) -> Integer -> Tree Integer ix
    go :: ExprF (Int -> Expr ix) ix -> Int -> Expr ix
    go (IntF n) d = IxIn (IntF d)
    go (AddF a b) d = IxIn (AddF (a d) (b d))
-}

Answer 1

我在这里假设您正在尝试将每个 IntF 节点设置为它在树中的深度 （就像来自 byDepthF 的函数链接的问题）而不是一些名为 depth.

的固定整数参数
如果是这样，我认为您可能正在寻找类似以下的内容：

newtype IntExpr ix = IntExpr { runIntExpr :: Int -> Expr ix } setDepth :: Expr ix -> Expr ix setDepth e = runIntExpr (icata go e) 0 where go :: ExprF IntExpr ix -> IntExpr ix go (IntF n) = IntExpr (\d -> IxIn (IntF d)) go (AddF a b) = IntExpr (\d -> IxIn (AddF (runIntExpr a (d+1)) (runIntExpr b (d+1)))

即需要定义一个newtype作为ExprF的索引第一个类型参数，通过Int ->reader传递索引。剩下的只是包装和展开。

可访问上下文数据的折叠索引仿函数

Folding indexed functors with access to contextual data

haskell

traversal

functor