Prevent observable exchange for specific subtrees in Haskell

Question

I have an EDSL that offers a list of similar combinators for arrays ( map , zipWith , etc.)

Some combinators require certain inputs to be random access. For example. a Gather dataset that selects items from the dataset at the indices specified by others:

 Gather (Manifest [10,11,12]) (Manifest [2,0,0,1,2]) = [12,10,10,11,12] 

The language uses the data-reify to restore sharing. The problem is that sometimes the same subtree contains both nodes that need random access and those that can be calculated sequentially. After they separate, the subsequent appraiser is torn.

For example, in the tree below, I would like [1,2,3] to continue to be used together, but Manifests wrapped them as different nodes in the restored graph:

  [1, 2, 3] / \ Manifest Manifest | | | Map (+1) \ / Gather 

A more complex example may include several common nodes, all of which should become different (even if Map (+1) (Manifest [1,2,3]) can be divided.

  [1, 2, 3] / \ Manifest Manifest | | Map (+1) Map (+1) | /| Map (*2) / | \ / | Gather | \ | ZipWith (+) 

Even if I find a solution for a simple case ( Gather Manifest links directly), it will already cover most use cases.

Any pointers are welcome!

Below is a simple language layout.

 module NoSharing where data AST = Manifest [Int] | Map (Int -> Int) AST | ZipWith (Int -> Int -> Int) AST AST | Gather AST -- ^ Data AST -- ^ Indices complex = ZipWith (+) gathered indexes where gathered = Gather (Map (*2) indexes) indexes indexes = Map (+1) $ Manifest [1,2,3] simple = Gather dat indexes where dat = Manifest [1,2,3] indexes = Map (+1) dat 

Answer 1

One way to do this is to manually eliminate sharing before you call data-reify . For example, this function should, we hope, parse the Manifest top-level constructor, but leave its argument general:

 rebuildManifest :: AST -> AST rebuildManifest (Manifest xs) = Manifest xs rebuildManifest t = t 

Now, to parse any Manifest under Gather , you can do the same recursively, taking care to reuse the original, if necessary

 rebuildAllManifestsUnderGather :: AST -> (AST, Bool) rebuildAllManifestsUnderGather t@ (Map f t') = let (newt', reuse) = rebuildAllManifestsUnderGather t' in if reuse then (t, True) else (Map f newt', False) rebuildAllManifestsUnderGather t@ (ZipWith f t1 t2) = let (newt1, reuse1) = rebuildAllManifestsUnderGather t1 (newt2, reuse2) = rebuildAllManifestsUnderGather t2 in if reuse1 && reuse2 then (t, True) else (ZipWith f newt1 newt2, False) rebuildAllManifestsUnderGather t@ (Gather t1 t2) = let (newt1, reuse1) = rebuildManifest $ rebuildAllManifestsUnderGather t1 (newt2, reuse2) = rebuildManifest $ rebuildAllManifestsUnderGather t2 in if reuse1 && reuse2 then (t, True) else (Gather newt1 newt2, False) where rebuildManifest (Manifest xs, _) = (Manifest xs, False) rebuildManifest (t, reuse) = (t, reuse) rebuildAllManifestsUnderGather t@ (Manifest xs) = (t, True) 

However, it should be warned : the observed sharing is not guaranteed and may be unreliable in both directions. The GHC optimizer may well “split up” attempts to drop Manifest higher. I don’t know how it will be in practice.

Also, this solution is rather complicated, so given the fragility, it might be better to have an explicit opaque pass after calling data-reify .