>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
