arrays and lamda terms

Claus Reinke
Thu, 6 Feb 2003 10:08:00 -0000

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

As I said, it all depends on how you're counting. But given that the serious
implementations of lambda support one-step reduction of n-ary abstractions
without any problems (think de Bruijn indices, supercombinator reduction,
beta-in-the-large), it may seem overly conservative to restrict counting to 
unary abstractions.

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

I'm not sure I understand your concern here. The selectors are functions,
but they are also all elements of the same type, so one can compute the 
actual selector to use in any given case dynamically, say depending on
runtime user input:

main = do
    let a = list2arr5 [1..5::Int]
    l <- getLine
    let s = case read l of { 1 -> s5_1; ..; 5 -> s5_5 } -- read for selectors
          i = list2arr5 "12345"                                         -- show for selectors
    putStrLn $ "you chose: a["++[i s]++"]= "++show (a s)  -- variable index..

Collecting all selectors/indices in a list was just a quick way of emulating
the typical for-loop over all array indices..

Perhaps you'd be happier if there were more operations defined on selectors?
Haskellers sometimes think of functions as abstract values that can be applied,
but not computed with, but in lambda that's all one does (it's just that Haskell
doesn't support that style all too well) - as further examples, here are successor 
and predecessor (cyclic here; adding out-of-bounds errors instead would be 

succ5 = arr5 s5_2 s5_3 s5_4 s5_5 s5_1
pred5 = arr5 s5_5 s5_1 s5_2 s5_3 s5_4

or equality:

eq5_1 = arr5 True False False False False
eq5_5 = arr5 False False False False True
(==) = arr5 eq5_1 eq5_2 eq5_3 eq5_4 eq5_5