haskell - Haskell 中的 AST 转换

Question

我有一个根节点类型为 E.Root 的 AST .我需要将其转换为根节点类型为 I.Root 的 AST .

我现在可以定义一个函数 eToI带有类型签名:

eToI :: E.Root -> AdditionalInfo -> I.Root

但是，两个 AST 共享许多节点。因此，函数 eToF有很多样板代码构建 I's来自 E's 的节点本质上相同的节点。

我想解决这两个问题:

在类型级别，避免定义 I 的节点.我有所有节点
的 E定义。我在 I 中定义了哪些节点会发生变化.我可以有吗
编译器生成 I 中的所有类型，通过某种方式映射什么
需要改变吗？

在值(value)层面，我只想为
变化的节点(假设 E 的 A 映射到 I 的 Z ..):

    aToZ :: E.A -> AdditionalInfo -> I.Z
    bToY :: E.B -> AdditionalInfo -> I.Y

现在，编译器可以生成像 eToI 这样的函数吗？

    eToI :: E.Root -> AdditionalInfo -> I.Root

Haskell 的惯用方法是什么？

Answer 1

有时您可以找出 E.Root 的共同点。和 I.Root成一种或多种可重用的数据类型。它通常也有助于隐藏 AdditionalInfo -> ...在 monad 或应用仿函数中。例如，这里有一些伪代码:

module Common where
  {-# LANGUAGE DeriveTraversable #-}
  data Reusable root = ... root ...
    deriving (Functor, Foldable, Traversable)

module E where
  import Common
  data Root = Leaf (Reusable Root) | Node Root

module I where
  {-# LANGUAGE GeneralizedNewtypeDeriving #-}
  import Common

  import Data.Monoid

  data Root = Root [Reusable Root]
    deriving Monoid

module Transform where
  import Common
  import qualified E
  import qualified I

  import Control.Applicative
  import Control.Monad.Reader
  import Data.Monoid

  type AdditionalInput = ...
  type F = Reader AdditionalInput

  convertRoot :: E.Root -> F I.Root
  convertRoot (Leaf reusable) =
    traverse convertRoot reusable
  convertRoot (Node left right) =
    liftA2 mappend (convertRoot left) (convertRoot right)

现在我可以使用 traverse在 Reusable E.Root 之间转换和 Reusable I.Root .