在项目列表上泛化一元表达式

Question

我有一个 monadic 函数，可以帮助将 Expr 类型的值转换为 Term 的值。签名是

fromDM :: (Name -> CompilerM Term) -> Expr -> CompilerM Term

一般来说，我很难处理一个病例。我可以写下每个单独解决方案的实现

import Control.Monad.State

type CompilerM = State Incr

newtype Incr = Incr Int deriving (Show)

generateNameM :: CompilerM Name
generateNameM = state $ \i ->
  let Incr y = i
      j      = (+1) y
  in  (Name j, Incr j)

data Expr = Tuple [Expr]
data Name = Name Int
data Term = Let Name [Name] Term

fromDM :: (Name -> CompilerM Term) -> Expr -> CompilerM Term
fromDM k expr = case expr of
  Tuple [e1, e2]         -> do
    x  <- generateNameM
    t' <- k x
    fromDM (\z1 -> fromDM (\z2 -> pure $ Let x [z1, z2] t') e2) e1

  Tuple [e1, e2, e3]     -> do
    x  <- generateNameM
    t' <- k x
    fromDM (\z1 -> fromDM (\z2 -> fromDM (\z3 -> pure $ Let x [z1, z2, z3] t') e3) e2) e1

  Tuple [e1, e2, e3, e4] -> do
    x  <- generateNameM
    t' <- k x
    fromDM (\z1 -> fromDM (\z2 -> fromDM (\z3 -> fromDM (\z4 -> return $ Let x [z1, z2, z3, z4] t') e4) e3) e2) e1

现在我想用一般规则代替它，即 Tuple es。我觉得这应该可以用 foldlM 或 foldrM 来实现。然而，我有点卡在如何做到这一点上。那么，我如何为这种适用于任意表达式列表的转换编写一般规则？

Answer 1

好吧，我对Cont了解不多，所以让我概述一下我在处理这个问题时的思考过程。我要做的第一件事是只提取依赖于 Tuple 内容的代码位，因此：

fromDM k expr = case expr of
    Tuple es -> do
        x  <- generateNameM
        t' <- k x
        letExprs x t' es

letExprs x t' [e1, e2] = fromDM (\z1 -> fromDM (\z2 -> pure $ Let x [z1, z2] t') e2) e1
-- etc.

我们想抽象化 letExprs 以便它可以处理任何长度的列表。既然我们已经写下了问题，费曼协议的下一步就是认真思考。所以我非常努力地盯着不同的案例。在我看来，列表中的每个 cons 单元格都变成了对 fromDM 的调用；在基本情况下，Let 应用于不同的列表。我们可以将不同的列表放在一个累加器中，如下所示：

fromDM k expr = case expr of
    Tuple es -> do
        x  <- generateNameM
        t' <- k x
        letExprs x t' [] es

letExprs x t' vars [] = pure $ Let x (reverse vars) t'
letExprs x t' vars (e:es) = fromDM (\z -> letExprs x t' (z:vars) es) e

这对我来说已经很不错了。如果你想把它变成折叠（出于通常的原因，这很好：你不会不小心搞砸了递归模式，而且读者知道你没有做任何棘手的事情），我们现在几乎可以直接阅读它：

fromDM k expr = case expr of
    Tuple es -> do
        x  <- generateNameM
        t' <- k x
        foldr (\e k vars -> fromDM (\z -> k (z:vars)) e)
              (\vars -> pure $ Let x (reverse vars) t')
              es

在项目列表上泛化一元表达式

Generalizing a monadic expression over a list of items

monads

haskell