Проблема рекурсии при написании версии Lens.para с поддержкой "Pretext"
Я пытался построить замену Lens.para это обеспечивает линзовые контексты для функции para, когда она выполняет свою работу. Однако, я, кажется, где-то допустил ошибку в рекурсии.
Согласно моему пониманию, Lens.para является функцией параморфизма значений в рекурсивном алгебраическом типе данных То есть он использует plated и принимает функцию, которая анализирует список опций, которые будут использоваться для обхода "самоподобного синтаксического пространства" фрагмента данных, в то же время делая свой контекст данных обхода доступным для функции во время ее работы. Его тип Lens.Plated a => (a -> [r] -> r) -> a -> r, где [r] список значений контекста данных, и a является типом каждого значения, которое указывает, как "изучить" последующие уровни.
Чрезвычайно простой пример типа игрушек, который я использую для проверки концепции, выглядит следующим образом:
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
1 ответ
Это взяло меня в очень интересное путешествие, в котором я все еще нахожусь. Я уверен, что ответ заключается в создании новой функции, которая объединяет функциональность Lens.paraOf plate с этим из Lens.contexts, По крайней мере, я знаю проблему сейчас и намного больше о контексте и рекурсивных схемах. Я бы посоветовал всем, кто заинтересован в написании этой функции, обратиться к ее источнику.
Итак, чтобы ответить на вопрос, ошибка в рекурсии заключается в том, что я использую fmap (<$>) отобразить каждую верхнюю линзу на каждого ребенка в нижней части структуры. Это означает, что каждое поддерево, а не только получает рекурсию в свою конкретную часть дерева, получает полную рекурсию в каждую часть дерева.
Правильная реализация будет учитывать это.