| | 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. |
