Approaches like the Abstract Algorithm (that you link to) turn out to just shift the costs elsewhere; in particular to the "book keeping" (IIUC nodes act differently depending on which "path" we're traversing, and keeping track of that exactly cancels out the benefits of optimal sharing).
For example, see links at https://www.reddit.com/r/haskell/comments/2zqtfk/why_isnt_an...