递归类型镜头

Question

递归类型镜头

haskellgrammarlensesscrap-your-boilerplate

4

我正在尝试创建一些代码，可以接受任何递归语法数据类型和该数据类型的任何表达式，并生成相同类型的所有子表达式列表，类似于对类型的递归进行扫描。

我已经为附带的玩具计算器语法类型EExp编写了两个手动示例。第一个示例使用Lens库中的prisms和lenses，仅适用于一个eg1示例表达式，而第二个函数只使用手工编写的代码，但可用于任何EExp表达式。

理想情况下，我可以使用模板Haskell或其他东西自动构建递归函数，该函数可以专注于该类型中任何种类的表达式的每个子表达式（如prism / lens），因此也可以轻松打印出给定的任何表达式的所有部分的列表。

不过，我有点困惑，不知道下一步应该尝试什么或研究什么。非常感谢您的帮助！

import qualified Control.Lens as Lens
import qualified Control.Lens.TH as LTH


-- Syntax for toy language

data EExp a
  = ELit a
  | EAdd (EExp a) (EExp a)
  | EMul (EExp a) (EExp a)
  | ESub (EExp a) (EExp a)
  deriving Show

-- build out a set of focus functions using lens / TH

LTH.makePrisms ''EExp


-- An example "text" in the Syntax

eg1 :: EExp Int
eg1 = EAdd
        (ELit 1)
        (EAdd (ELit 2) (ELit 0))

-- using lenses, we build out all the
-- EExp possibilities from the example "text":

lensedOptions :: Show a => EExp a -> [EExp a]
lensedOptions exp =
  let
    maybeGet l = Lens.preview l exp
    listMaybes =
      [ Just exp
      , maybeGet (_EAdd.(Lens._1))
      , maybeGet (_EAdd.(Lens._2))
      , maybeGet (_EAdd.(Lens._2)._EAdd.(Lens._1))
      , maybeGet (_EAdd.(Lens._2)._EAdd.(Lens._2))
      ]
  in
    maybe [] id $ sequenceA listMaybes

printEm :: IO ()
printEm = sequence_ $ map print $ lensedOptions eg1

-- using handwritten code, we build out all the
-- EExp possibilities from the example "text":


buildOptions :: Show a => EExp a -> [EExp a]
buildOptions exp =
  let
    buildBinOpts e1 e2 = [exp] ++ buildOptions e1 ++ buildOptions e2
  in
    case exp of
      ELit i -> [exp]
      EAdd e1 e2 ->
        buildBinOpts e1 e2
      EMul e1 e2 ->
        buildBinOpts e1 e2
      ESub e1 e2 ->
        buildBinOpts e1 e2

printEm2 :: IO ()
printEm2 = sequence_ $ map print $ buildOptions eg1

- Julian Leviston

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hao · Accepted Answer

你正在寻找 Control.Lens.Plated 模块。

首先添加一个 Data 衍生。

{-# language DeriveDataTypeable #-}
import Data.Data
import Data.Data.Lens
import Control.Lens -- for universeOf function

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

然后：

> buildOptions eg1
[EAdd (ELit 1) (EAdd (ELit 2) (ELit 0)),ELit 1,EAdd (ELit 2) (ELit 0),ELit 2,ELit 0]

> universeOf uniplate eg1
[EAdd (ELit 1) (EAdd (ELit 2) (ELit 0)),ELit 1,EAdd (ELit 2) (ELit 0),ELit 2,ELit 0]

uniplate镜头在这里扮演了大部分的魔法角色；利用由Data类型类提供的信息，它能够向任何Data友好的数据结构中步进一步，以找到相似的子节点。它还进行了一些高空缓存体操，以使遍历效率高，但我们可以安全地忽略它。 universeOf uniplate重复调用uniplate来查找所有传递后代。

有关Data.Data的更多信息，请查看Lämmel和SPJ的Scrap Your Boilerplate论文。