构建可复用节点的DAG：避免重复计算的实现难题

我希望构建一个DAG，但不确定如何在构建计算图（用于C++结合XLA的场景）时避免重复工作。最初使用的AST定义如下：

data Node =
    Lit Double
  | Neg Node
  | Add Node Node

但遍历let x = Lit 1.0 in Add x x时，x会被重复处理两次。*注：这里的“评估”并非传统求值概念，实际是用来在C++中结合XLA构建计算图。

我提出了几种方案，但均存在问题：

方案1：缓存已处理节点 #

缓存已处理的节点，在节点相等时复用实例。但这种方式效率低下——用户明确知道哪些节点会被复用，我们理应直接利用这一信息，而非事后通过节点相等性检查来复用。

方案2：基于拓扑排序的列表表示 #

我尝试用拓扑排序后的List Node来表示DAG，定义如下：

data Node =
    Lit Double
  | Neg Nat
  | Add Nat Nat

比如let x = Lit 1.0 in Add x x可以表示为[Lit 1.0, Add 0 0]，这个思路在简单场景下可行，但我不知道如何构建这个列表。
遇到复杂结构时问题更突出，比如下面的图：

Lit 1.0
      |
     Neg  Lit 2.0
      | \ /
      | Add
      | /
      Add

构建过程中无法提前看到完整的图结构，因此不知道如何对列表中的节点进行拓扑排序。

方案2a：带全局状态的拓扑排序 #

如果使用命令式语言，可以通过全局状态在创建节点时将其加入列表。转换到函数式环境时，首先想到State monad，但我希望封装这部分逻辑，不要让用户编写monadic代码。我期望用户能写出这样的代码：

let x = val 1.0
    y = x + x
 in y + y

而非：

do x <- val 1.0
   y <- x + x
   y + y

我想知道是不是引用透明性直接导致这个需求无法实现——毕竟表达式应该可以被其值替代。

方案2b：拓扑排序+子图合并 #

依旧基于拓扑排序，但分别构建子图，遇到Add这类组合节点时合并子图。但我不清楚具体的实现方式。如果通过检查节点相等性来合并，就又回到了方案1的问题：先丢弃了复用信息，之后又要重新计算，完全是浪费。

我使用Idris进行开发，但Haskell中的情况应该类似。

内容的提问来源于stack exchange，提问作者joel