编写 "Pretext" 感知版本 Lens.para 时的递归问题

Question

我一直在尝试构建 Lens.para 的替代品，在 para 函数工作时为其提供镜头上下文。但是，我好像在递归的某个地方出错了。

根据我的理解，Lens.para是递归代数数据类型中values的一个paramorphism function。也就是说，它使用 plated 并采用一个函数来展开选项列表，用于遍历一段数据的 "self-similar syntax space" ，同时使其遍历数据上下文可用于该函数因为它做它的工作。它的类型是 Lens.Plated a => (a -> [r] -> r) -> a -> r，其中 [r] 是数据上下文值的列表，a 是每个值的类型，plated 知道如何 "look into" 的连续级别。

我用于概念验证的极其简单的玩具示例数据类型如下：

data EExp a = ELit a | EAdd (EExp a) (EExp a) deriving (Show, Eq)

所以，这是我的代码，包括 showOptions 的现有工作版本和我的新版本 showOptions'，它使用我的自定义 Lens.para，称为 paraApp。不同之处在于，它在工作时将 Pretext 与数据一起传递，以便稍后我可以调整我的代码以利用此 Pretext 来调整原始数据结构（如果需要）。

{-# LANGUAGE RankNTypes, TemplateHaskell, ExplicitForAll, DeriveDataTypeable, StandaloneDeriving #-}

module StepThree where

import qualified Control.Lens as Lens
import qualified Data.Data as DD
import qualified Data.Data.Lens as DDL
import qualified Data.Maybe as DM
import qualified Data.List as DL
import Text.Read (readMaybe)
import StepThreeGrammar (EExp(..), pretty, run)

import Control.Comonad.Store.Class (pos, peek, ComonadStore)
import Control.Lens.Internal.Context (Pretext(..), sell)

import qualified Language.Haskell.Interpreter as I
import Language.Haskell.Interpreter (Interpreter, GhcError(..), InterpreterError(..))

instance DD.Data a => Lens.Plated (EExp a)
deriving instance DD.Data a => DD.Data (EExp a)

eg3' :: EExp Int
eg3' = EAdd (EAdd (EAdd (EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)) (ELit 1)) (ELit 5)) (ELit 0)

showOptions :: (Lens.Plated a, Show a) => (a -> String) -> a -> [String]
showOptions showFn = Lens.para $ \a xs ->
    let
      sa = showFn a
      (_,is) = DL.mapAccumL mapAccumFn (0, sa) xs
    in
      sa : concat is
  where
    mapAccumFn (n, acc) x =
      let
        i = pfxIndex (head x) acc
      in
        ( (n+i+length (head x)
          , drop (i+length (head x)) acc)
        , map (replicate (n+i) ' ' ++) x)


showOptions' :: (Lens.Plated a, Show a) => (a -> String) -> a -> [String]
showOptions' showFn = paraApp $ \(a, ctx) xs ->
    let
      sa = showFn a
      (_, is) = DL.mapAccumL mapAccumFn (0, sa) xs
    in
      sa : concat is
  where
    mapAccumFn (n, acc) x =
      let
        i = pfxIndex (head x) acc
      in
        ( (n+i+length (head x)
          , drop (i+length (head x)) acc)
        , map (replicate (n+i) ' ' ++) x)

paraApp :: Lens.Plated a => ((a, Pretext (->) a a a) -> [r] -> r) -> a -> r
paraApp f x = go id (x, makePretextFocussingOnSelfFor x)
  where
    go p a =
      let p' = Lens.plate . p
          holes = Lens.holesOf p' x
      in f a (go p' <$> (map (\c -> (pos c, c)) holes))
    makePretextFocussingOnSelfFor x = Pretext ($ x)


pfxIndex :: Eq a => [a] -> [a] -> Int
pfxIndex x y = maybe 0 id (DL.findIndex (x `DL.isPrefixOf`) (DL.tails y))

如果我进入 GHCi 并执行以下代码，它会提供预期的输出：

*Main EditorTest StepThree Control.Lens> mapM_ putStrLn $ StepThree.showOptions show eg3'
EAdd (EAdd (EAdd (EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)) (ELit 1)) (ELit 5)) (ELit 0)
      EAdd (EAdd (EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)) (ELit 1)) (ELit 5)
            EAdd (EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)) (ELit 1)
                  EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)
                        EAdd (ELit 11) (ELit 9)
                              ELit 11
                                        ELit 9
                                                  ELit 3
                                                            ELit 1
                                                                      ELit 5
                                                                                ELit 0

当我不想对上下文做任何事情（比如更新原始值的特定部分）时，这很好

所以当我尝试替换函数时，会发生以下情况（应该与上述相同）：

    *Main EditorTest StepThree Control.Lens> mapM_ putStrLn $ StepThree.showOptions' show eg3'
    EAdd (EAdd (EAdd (EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)) (ELit 1)) (ELit 5)) (ELit 0)
          EAdd (EAdd (EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)) (ELit 1)) (ELit 5)
                EAdd (EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)) (ELit 1)
                      EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)
                            EAdd (ELit 11) (ELit 9)
                                  ELit 11
                                            ELit 9
                                                      ELit 3
                                                      ELit 11
                                                             ELit 9
                                                                ELit 1
                                                                EAdd (ELit 11) (ELit 9)
                                                                      ELit 11
                                                                                ELit 9
                                                                                       ELit 3
                                                                                       ELit 11
                                                                                              ELit 9
                                                                          ELit 5
                                                                          EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)
                                                                                EAdd (ELit 11) (ELit 9)
                                                                                      ELit 11
                                                                                                ELit 9
                                                                                                          ELit 3
                                                                                                          ELit 11
                                                                                                                 ELit 9
                                                                                                                 ELit 1
                                                                                                                 EAdd (ELit 11) (ELit 9)
                                                                                                                       ELit 11
                                                                                                                                 ELit 9
                                                                                                                                        ELit 3
                                                                                                                                        ELit 11
                                                                                                                                               ELit 9
                                                                                    ELit 0
                                                                                    EAdd (EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)) (ELit 1)
                                                                                          EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)
                                                                                                EAdd (ELit 11) (ELit 9)
                                                                                                      ELit 11
                                                                                                                ELit 9
                                                                                                                          ELit 3
                                                                                                                          ELit 11
                                                                                                                                 ELit 9
                                                                                                                                    ELit 1
                                                                                                                                    EAdd (ELit 11) (ELit 9)
                                                                                                                                          ELit 11
                                                                                                                                                    ELit 9
                                                                                                                                                           ELit 3
                                                                                                                                                           ELit 11
                                                                                                                                                                  ELit 9
                                                                                                                                           ELit 5
                                                                                                                                           EAdd (EAdd (ELit 11) (ELit 9)) (ELit 3)
                                                                                                                                                 EAdd (ELit 11) (ELit 9)
                                                                                                                                                       ELit 11
                                                                                                                                                                 ELit 9
                                                                                                                                                                           ELit 3
                                                                                                                                                                           ELit 11
                                                                                                                                                                                  ELit 9
                                                                                                                                                                                  ELit 1
                                                                                                                                                                                  EAdd (ELit 11) (ELit 9)
                                                                                                                                                                                        ELit 11
                                                                                                                                                                                                  ELit 9
                                                                                                                                                                                                         ELit 3
                                                                                                                                                                                                         ELit 11
                                                                                                                                                                                                                ELit 9

显然我的递归某处有误，但我无法解决。一如既往，我们将不胜感激。

如果您不熟悉 Lens.para 的原始定义，可以在 https://hackage.haskell.org/package/lens-4.15.2/docs/src/Control.Lens.Plated.html#para

找到它

Answer 1

这让我踏上了一段非常有趣的旅程，我仍在继续。我很确定答案在于创建一个新函数，将 Lens.paraOf plate 的功能与 Lens.contexts 的功能合并。至少我现在知道这个问题，并且更多地了解上下文和递归方案。我建议任何有兴趣编写此函数的人都应该查看这些函数的来源。

所以，为了回答这个问题，递归中的错误在于我正在使用 fmap (<$>) 映射 every single upper 镜头在每个 child 结构的 lower 部分。这意味着每个子树，而不是只递归到树的特定部分，而是将完整递归到树的每个部分。

正确的实施会考虑到这一点。

编写 "Pretext" 感知版本 Lens.para 时的递归问题

Recursion issue when writing a "Pretext" aware version of Lens.para

recursion

haskell

haskell-lens

recursion-schemes