Right, I mean constant-steps, rather than single steps. Could you give an example to what you are describing?
Sure. Just thought you'd like to play with the idea yourself first:-) If you limit beta-reduction to deal only with unary abstractions, there's little chance of deconstructing an expression involving n separate subterms with less than n steps. Otherwise, it is just the old idea of representing data structures by their folds. A selector then returns one of its n parameters, which usual implementations deal with in a single step. You could even compute the selectors for each combination of array-size and position if Haskell's type system didn't get in the way (a job for template Haskell, or some type class hackery). Cheers, Claus -- representing arrays as their folds, -- here for m=5 arr5 a1 a2 a3 a4 a5 s = s a1 a2 a3 a4 a5 show_arr5 a = show $ a (,,,,) list2arr5 [a1,a2,a3,a4,a5] = arr5 a1 a2 a3 a4 a5 -- selectors -- sm_n =~= (ignore^(n-1)) (keep^(m-n)) -- where {- const by any other name -} -- ignore f x = f -- keep x y = x s5_1 a1 a2 a3 a4 a5 = a1 s5_2 a1 a2 a3 a4 a5 = a2 s5_3 a1 a2 a3 a4 a5 = a3 s5_4 a1 a2 a3 a4 a5 = a4 s5_5 a1 a2 a3 a4 a5 = a5 -- updates -- for illustration only; whole-array ops preferable u5_1 a1 a2 a3 a4 a5 f = arr5 (f a1) a2 a3 a4 a5 u5_2 a1 a2 a3 a4 a5 f = arr5 a1 (f a2) a3 a4 a5 u5_3 a1 a2 a3 a4 a5 f = arr5 a1 a2 (f a3) a4 a5 u5_4 a1 a2 a3 a4 a5 f = arr5 a1 a2 a3 (f a4) a5 u5_5 a1 a2 a3 a4 a5 f = arr5 a1 a2 a3 a4 (f a5) -- example uses main = do let a = list2arr5 [1..5::Int] putStrLn $ "a="++show_arr5 a putStrLn $ "a[4]="++show (a s5_4) let b = a u5_4 (const 0) putStrLn $ "b="++show_arr5 b putStrLn $ "b[4]="++show (b s5_4) mapM_ (print . b) [s5_1,s5_2,s5_3,s5_4,s5_5] let c = b u5_1 (+1) u5_3 (+1) u5_5 (*2) putStrLn $ "c="++show_arr5 c