Hi Oleg, at the possible risk of straying from Tom's original problem, consider the following generator that could conceivably occur in practice:
sklansky f [] = [] sklansky f [x] = [x] sklansky f xs = left' ++ [ f (last left') r | r <- right' ] where (left, right) = splitAt (length xs `div` 2) xs left' = sklansky f left right' = sklansky f right
test_sklansky n = runState sk exmap0 where sk = sequence (Prelude.map unA (sklansky add xs)) xs = Prelude.map (variable . show) [1..n]
(Example due to Chalmers folk, Mary Sheeran and Emil Axelsson; sklanksy is similar to scanl1, but contains more parallelism.) If a 128-bit processor were being developed, sklansky could reasonably be passed 128 elements, *Main> test_sklansky 128 -- on an AMD64 2200 (3.71 secs, 296129440 bytes) and could form part of a larger expression, and be called several times. So I think this is close to a real situation where CSE is not practical. But like you say, a human would not write such a humungous expression by hand; hand-written expressions may therefore be ideal for crunching by your CSE method. Still, we might like to write generators like sklansky. Hope is offered by the new "let_" construct, but it's not clear how to use it in this case. The problem is that sklansky is a function over lists of expressions rather than single expressions, and the "let_" construct can only bind single expressions and return single expressions. To write sklansky using your approach, it seems (to me) that the DSL's expression type needs to be extended to support lists. Will this not be complicated and introduce notational inconvenience? (In an earlier post, I outlined a method for embedding algebraic data types in Haskell, and it does have some notational burden.) Matt.