Изучение связующей структуры в свободной монаде АСТ

Question

Возьмите этот простой базовый функтор и другие механизмы для бесплатной монады с обязательными условиями:

{-# LANGUAGE DeriveFunctor #-}

import Control.Monad.Free

data ProgF r =
    FooF (Double -> r)
  | BarF Double (Int -> r)
  | EndF
  deriving Functor

type Program = Free ProgF

foo   = liftF (FooF id)
bar a = liftF (BarF a id)

А вот простая программа

prog :: Program Int
prog = do
  a <- foo
  bar a

Он имеет следующий (ручной) AST:

prog =
  Free (FooF (\p0 ->
    Free (BarF p0 (\p1 ->
      Pure p1))

То, что я хотел бы сделать, это рассуждать о связанных терминах следующим образом:

• посмотри на Pure срок в АСТ
• обратите внимание на связанные переменные, которые встречаются там
• аннотировать соответствующие узлы привязки в AST

Аннотирование свободной монады AST напрямую через cofree comonad кажется невозможным без какого-либо сопряжения, но вы можете представить себе что-то вроде следующего аннотированного AST (например, через Fix) в каких узлах связываются переменные, которые появляются в Pure помечены Just True:

annotatedProg =
  Just False :< FooF (\p0 ->
    Just True :< BarF p0 (\p1 ->
      Nothing  :< EndF))

Итак: есть ли способ проверить привязки в программе, подобной этой, таким специальным способом? Т.е. без введения отдельного типа переменной а-ля этот вопрос, например.

Я подозреваю, что это может быть невозможно сделать. Варианты как data-reify привлекательны, но, кажется, это очень трудно или невозможно сделать ProgF экземпляр необходимых классов типов (Foldable, Traversable, MuRef).

Правильна ли эта интуиция, или есть какие-то способы сделать это, которые я не рассматривал? Обратите внимание, что я рад развлечь любые ужасные небезопасные или динамичные средства.

Answer 1

Я удовлетворен тем, что это невозможно сделать каким-либо "вменяемым" специальным методом, по той же причине, по которой невозможно изучить структуру привязки, например: \a -> \b -> \c -> b + a,