4

我正在尝试创建一些代码，可以采用任何递归语法数据类型和该数据类型的任何表达式，并生成相同类型的所有子表达式的列表，建立起来，有点像scan类型的递归.

我在下面为随附的玩具计算器语法类型编写了两个手动示例EExp。第一个示例使用 Lens 库中的棱镜和透镜，仅适用于一个eg1示例表达式，而第二个函数仅使用手动代码，但适用于任何EExp表达式。

理想情况下，我可以使用模板 haskell 或其他东西来自动构建一个递归函数，该函数可以专注于该类型（如棱镜/透镜）中任何类型的表达式的每个子表达式，因此也可以轻松打印出列表赋予它的任何表达式的所有片段。

不过，我对接下来要尝试或研究的内容有点困惑。非常感谢任何帮助！

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
4

1 回答 1

3

您正在寻找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发挥了大部分魔力。使用Datatypeclass提供的信息，它可以一步步进入任何Data友好的数据结构，以找到自相似的孩子。它还在做一些高空缓存体操以提高遍历效率，但我们可以放心地忽略这一点。

universeOf uniplate反复调用uniplate以查找所有传递后代。

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

于 2017-05-29T18:10:09.893 回答