arrays and lamda terms

Cagdas Ozgenc co19@cornell.edu
Wed, 5 Feb 2003 15:53:28 +0200


Thanks for the example. It is quite sophisticated.

I can see how you select an element randomly using the function parameters
(it's cheating actually because lamda calculus will still reduce this it in
steps, so it works for Haskell implementation because it does things
smarter)
One thing I object is, probably I did not understand that part, is that you
still can't seem to access an element with a variable index (index is a
variable instead of a literal constant). You placed all selector functions
in a List, but then you have to go through the list sequentially instead of
random access. What you seem to have done is to get a value using compiler's
symbolic evaluation. If you cheat like that you could have instead do the
following:

a1 = 1
a2 = 2
a3 = 3
...

then put [a1,a2,a3,a4...] etc.

And you will not again be able to access the items with a variable index in
O(1) time.
Please enlighten me on this detail.

Thank you.

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