坑主在五月底時曾建議可以從最簡單的 context 開始 -- 記錄現在 AST 中含的 expression 數量就好：

type Info = Int

然後會有一個叫做 Desugar 的 data ：

data Desugar a = D (Info, a)
  deriving (Show)

根據她的建議：

定義自己的 monad 來攜帶未來要加的資料結構, 讓這個骨幹的運行是在這個 monad 裡

我們必須要實作：

instance Monad Desugar where
  return = pure
  D (info, module) >>= f = ...

但是， return 所代表的 minimum context 是什麼？我該在何時改變 info 來反應 expression 數量更新了呢？光看 return 和 (>>=) 一點頭緒也沒有。事後我才知道， desugar 這件事可以分成兩個問題來看。

其一是如何從 AST 中把我們要的資訊找出來，如果不對 AST 做任何改變，那就是單純把 AST 拆開，經過一些計算再組合回去。這件事可以靠 Applicative 的 (<$>) 和 (<*>) 幫我們做到。

其二是當遇上放在其他 context （例如 Maybe 或 List ）中的 Desugar 時，要怎麼把已經找出來的資訊組合起來？這件事情靠 Monad 的 (>>=) 做到。

整個 Haskell.Src.Exts 的 AST 太複雜了，不如先從簡單的 AST 開始。哪裡有簡單的 AST 呢？剛好 BYOHC 前面做過 lambda calculus XD

data Term a = Var a
            | Lam a (Term a)
            | App (Term a) (Term a)
  deriving (Show)

現在準備我們的 Desugar ：

type Info = Int

data Desugar a = D { runDesugar :: (Info, a) }
  deriving (Show)

Term 裡面沒有 Maybe 或 List ，於是做到 Applicative 就可以了：

instance Functor Desugar where
  fmap f (D (info, term)) = D (info, f term)

instance Applicative Desugar where
  pure term = D (0, term)
  D (info, f) <*> D (info', t) = D (info + info', f t)

為了方便直接寫 desugar 而不是 desugarVar, desugarLam, desugarApp ，來做一個自己的 type class ：

-- 需要用到 MultiParamTypeClasses 這個 language extension ，我還不是很明白它的意義與重要性
class (Applicative m) => Desugarable m t where
  desugar :: t -> m t

然後就可以實作給各種 Term 用的 desugar ：

instance Desugarable Desugar (Term a) where
  desugar (Var a) = Var <$> pure a
  desugar (Lam a term) = Lam <$> pure a <*> desugar term
  desugar (App term term') = App <$> desugar term <*> desugar term'

看看 Lam a term 和 Lam <$> pure a <*> desugar term ，是不是就像拆開來做些什麼，再組合起來？ XD

現在算算有幾個 Lam 。加上陽春的 count function ：

increase :: Desugar a -> Desugar a
increase (D (info, term)) = D (info + 1, term)

並把 desugar 改成：

instance Desugarable Desugar (Term a) where
  desugar (Var a) = Var <$> pure a
  desugar (Lam a term) = increase (Lam <$> pure a <*> desugar term)
  desugar (App term term') = App <$> desugar term <*> desugar term'

之後會再改進這個 increase ，讓它跟 (>>=) 合作，現在先：

main :: IO ()
main =
  putStrLn . show . runDesugar . desugar $
    App (Lam "x" (Lam "y" (Var "x"))) (Var "z")

就能看到它輸出：

(2,App (Lam "x" (Lam "y" (Var "x"))) (Var "z"))

的確有 2 個 Lam 。