Re: arrays and lamda terms
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
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
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 straightforward): 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 Cheers, Claus
participants (2)
-
Cagdas Ozgenc -
Claus Reinke