[Haskell-cafe] wanted: Function to break circular data dependencies

[Bertram Felgenhauer]

Job Vranish wrote:

> Is a function like the following possible?:
> 
> avoidCircularDataDependency :: a -> a -> a
> avoidCircularDataDependency a b = ?

For one, it breaks purity. If we have

  let x = avoidCircularDataDependency y True
      y = avoidCircularDataDependency x False

then whether x and y are True or False depends on which of them is
evaluated first. Note that x and y might be evaluated in parallel
by different threads.

Secondly, an implementation of avoidCircularDataDependencies in a
threaded runtime system requires cycle detection on the heap, because
running into a black hole does not reliably indicate a data dependency
cycle. GHC currently only does this when things have already gone wrong;
cycles are detected during garbage collection and the threads involved
receive NonTermination exceptions as a result. To make
avoidCircularDataDependencies useful, you'd need a more efficient way of
detecting cycles, which looks like a hard problem to me.

> I've often found myself wanting a function like this. It would make certain
> kinds of knot-tying/cycle detection _much_ easier.

Actually I'd be interested in seeing an example for this.

Cheers,

Bertram