
% -----------------------------------------------------------------------------
\subsection{Tupling and intermediate vectors}
The following code is based on the core operation of the QuickHull benchmark. With the stream fusion approach we cannot inline the @detsAbove@ binding directly into its consumer (@maximumP@) because there is a second use of this variable in the result of the function. Given the type signature of this function, we might be inclined to accept this behavior as, after all, the first component of the result tuple has the type of a (mainifest) @Array Float@ instead of a @Stream Float@. However, if we consider the runtime behavior of the function, the entire @detsAbove@ array will be written out into memory before being read back in by @maximumP@. Even if @qsplit@ returns a manifest array, it should sum the elements ``on the fly'' instead of shuffling them back and forth across the memory bus.

\begin{small}
\begin{code}
type Point = (Float, Float)
type Line  = (Point, Point)

qsplit :: Line -> Array Point -> (Array Float, Float)
qsplit line points
 = let dets      = mapP   (det line) points
       detsAbove = filter (> 0) dets
       detMax    = maximumP detsAbove
   in  (detsAbove, detMax)

det :: Line -> Point -> Double
det ((x1, y1), (x2, y2)) (xo, yo) 
  = (x1 - xo) * (y2 - yo) - (y1 - yo) * (x2 - xo)
\end{code}
\end{small}


% -----------------------------------------------------------------------------
\subsection{Fusing into multiple consumers}
\label{s:IntroMultipleConsumers}
The following example is related to the one in the previous section, but highlights a more general problem.

\begin{small}
\begin{code}
 sumProd :: Stream (Int, Int) -> (Int, Int)
 sumProd xs
  = let (ys, zs) = unzip xs
    in  (sum ys, prod zs)
\end{code}
\end{small}

This problem is folklore, and well known in the context of lazy functional programming. Suppose the @sumProd@ function above is applied to a stream created by an arbitrary producer, which we'll call @create@: @sumProd (create ...)@. Now, although @create@ produces pairs of elements jointly, if we assume @sum@ and @prod@ are implemented in the standard way as tail-recursive functions, all of the @ys@ values will be demanded before the @zs@ values. This leads to a space-leak, because the @zs@ values must be stored while the @ys@ values are being consumed.

If we were to allow a programmer to intervene we could write a custom consumer that manually fuses the sum and product operations.

\begin{small}
\begin{code}
 sumProd' :: Stream (Int, Int) -> (Int, Int)
 sumProd' stream
  = foldlS (\\(x, y) (accX accY) -> (accX + x, accY * y)) 
           (0, 1) stream
\end{code}
\end{small}

There isn't an existing transform that does this automatically. A key problem is that the uses of @sum@ and @prod@ may appear in different places of the program text, but they need to be evaluated jointly in the same loop.


% -----------------------------------------------------------------------------
\subsection{Space usage in flattened programs}

Branching data flows are also created by the vectorisation transform used in Data Parallel Haskell, which is the main driving force for this work. Suppose we start with the following expression:
\begin{code}
 let f x = let y = g x 
           in  h1 y + h2 y
 in  map f zs
\end{code}

Vectorising this produces an expression equivalent to:
\begin{code}
 let f^ xs = let ys = g xs
             in  
\end{code}





The fact that flattening breaks the asymptotic complexity of flattened programs is a classic problem in the flattening approach to nested data parallelism. Consider the following example, which naively computes the closest pair of points. Here, @furthest@ is the source program and @furthest_v@ is the flattened version. The full flattening transform and derivation of @furthest_v@ is presented in our previous work \CITEME{Replicate Tech report}.

\begin{small}
\begin{code}
 type Point = (Float, Float)

 furthest :: Array Point -> Float
 furthest ps = maxP (mapP (\p. maxP (mapP (dist p) ps)) ps)

 furthest_v :: Array Point -> Float
 furthest_v ps
  = let c    = length ps
        ps1  = replicate  c ps
        ns   = lengths ps1
        ps2  = replicates ns ps
    in  max  \$ max_l c 
             \$ unconcat ps1 
             \$ dist_l (U.sum ns) ps2 (concat ps1)
\end{code}
\end{small}

Suppose we evaluate @furthest [p1 p2 p3 p4]@ where @p1 p2 ..@ represent whole points. Writing @ps1'@ for @concat ps1@ the flattened version, @furthest_v@ constructs the following intermediate vectors.

\begin{small}
\begin{code}
ps1' = [p1 p2 p3 p4  p1 p2 p3 p4  p1 p2 p3 p4  p1 p2 p3 p4]
ps2  = [p1 p1 p1 p1  p2 p2 p2 p2  p3 p3 p3 p3  p4 p4 p4 p4]
\end{code}
\end{small}

From this we can see why vector programming naturally provides the wrong cost model. If we take the peak space usage of @furthest_v@ to be the maximum of the space usage of all its subterms, then this is clearly going to be $O(n^2)$ in the length of the input array.

However, the structure of this computation is that of a \emph{fused hylomorphism}, the vectors that are created are immediately reduced by the surrounding context, namely the applications of @max@ and @max_l@. Both the cost model and fusion framework need to account for this. Any cost model that deals with this cannot be strictly compositional.

