| 6 | {{{ |

| 7 | smvm :: [:[: (Int, Double) :]:] -> [:Double:] -> [:Double:] |

| 8 | smvm m v = [: sumP [: x * (v !: i) | (i,x) <- row :] | row <- m :] |

| 9 | }}} |

| 10 | Here the variable 'v' is constant in the array comprehensions and will be replicated while lifting the expression `v !: i`. In other words, for every single element in a `row`, lifting implies the allocation of a separate copy of of the entire array `v` — and this only to perform a single indexing operation on that copy of `v`. More precisely, in the lifted code, lifted indexing (which we usually denote by `(!^)` is applied to a nested array consisting of multiple copies of `v`; i.e., it is applied to the result of `replicateP (length row) v`. |

| 11 | |

| 12 | This is clearly wasted effort and space. However, the situation is even worse in Ben's pathological example: |

| 13 | {{{ |

| 14 | treeLookup :: [:Int:] -> [:Int:] -> [:Int:] |

| 15 | treeLookup table xx |

| 16 | | lengthP xx == 1 |

| 17 | = [: table !: (xx !: 0) :] |

| 18 | | otherwise |

| 19 | = let len = lengthP xx |

| 20 | half = len `div` 2 |

| 21 | s1 = sliceP 0 half xx |

| 22 | s2 = sliceP half half xx |

| 23 | in concatP (mapP (treeLookup table) [: s1, s2 :]) |

| 24 | }}} |

| 25 | Here `table` is constant in `mapP (treeLookup table) [: s1, s2 :]`; hence, the entire `table` gets duplicated on each level of the recursion, leading to space consumption that is exponential in the depth of the recursion. |