[Haskell-cafe] Designing DSL with explicit sharing [was: I love purity, but it's killing me]

Matthew Naylor mfn-haskell-cafe at cs.york.ac.uk
Wed Feb 13 09:27:30 EST 2008

Hi Oleg,

it's not immediately clear (to me at least) how efficient your method
will be in "practice".  Any method based on common sub-expression
elimination surely must inspect every node in the flattened graph.  In
the worst case, an acyclic graph containing n nodes could have 2^n
nodes when flattened to a tree:

  tricky 0 = constant 0
  tricky d = add g g
      g = tricky (d-1)

Of course, in "practice" the worst case may not occur.  Also, my
mental model is big circuits, which may be different to yours and

(Sorry if I'm just pointing out the obvious.)


More information about the Haskell-Cafe mailing list