transducers in lua

gistfile1.lua

--Rich Hickey's infamous transducers, demonstrating reversed function composition.
--Look closely.


function transduce(tf, rf, init, iter)
   for i in iter do
      init = tf(rf)(init, i)
   end
   return init
end

--Our transducer-creator is called map, after Clojure's.
--But since this can act as a filter too I wonder if it doesn't
--deserve a new name.
function map(fn)
   return function(rf)
      return function(init, i)
         return rf(init, fn(i))
      end
   end
end

function plus_three(x)
   if x == nil then
      return nil
   end
   return x + 3
end

function is_even(x)
   if x == nil or x % 2 ~= 0 then
      return nil
   end
   return x
end

--f2 acts first?
function compose(f1, f2)
   return function(...)
      return f1(f2(...))
   end
end

t_plus_three = map(plus_three)
t_is_even = map(is_even)

--right?
t_even_plus_three = compose(t_is_even, t_plus_three)

function plus(x, y)
   return x == nil and 0 or y == nil and x or x + y
end

function each(arr)
   local i = 0
   return function()
      i = i + 1
      return arr[i]
   end
end

print(transduce(t_even_plus_three, plus, 0, each({2, 4, 5, 7})))
--> prints 12

--So why does it happen? Essentially, transducers create a stack.
--You have a "collection", we're collecting fog, call it Karl.
--Invent some transducers, skub and xyzzy. Transducers, as you
--can see, apply some function to each element of a collection,
--and we might call this function the atom. The atom of skub is foo,
--the atom of xyzzy is bar. Now, 
--how does skub . xyzzy act on Karl? Pay attention to when it's called:
--assume a reducing function like pair(a, b), and:

--transduce(skub . xyzzy, pair, iota, Karl)
--for thing in Karl do
-----iota = skub . xyzzy(pair)(iota, thing)

-----foo = skub(xyzzy(pair))(iota, thing)

--skub(xyzzy(pair))(iota, thing)
--return xyzzy(pair)(iota, foo(thing))

--xyzzy(pair)(iota, foo(thing))
--return pair(iota, bar(foo(thing)))

--So we can (kinda) see that the reason the transducers are reversed is that they
--apply to the folding function, rather than to the dataset. And the folding
--function is applied last, so each transducer must apply it's atom starting from
--the outside, which means whichever transducer was applied to the folding function
--most recently will get first pick of the data.