arrays and lamda terms

Claus Reinke
Wed, 5 Feb 2003 10:55:24 -0000

>Right, I mean constant-steps, rather than single steps. Could you give an example to what you are

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


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