lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index] 

Am 19.12.2012 14:13, schrieb Tomas Lundell:

It's maybe a little silly to use a map for side effects - for that you'd
probably want to use a loop.


Why? Because map unfortunately constructs a superfluous table?



Yes, because the conventional use of a map is to transform something. This
convention dates at least as far back as Lisp, which in turn would have
borrowed it from mathematics (hence the name "map").
What do you use for printing the elements of a list in Lisp? I never wrote a program in a functional language large enough to need output besides the REPL. 





Let's
call the function 'each' like in underscore.js or its Lua equivalent[1]
or Ruby (or table.foreachi like in previous Lua versions).



I don't tend to use functions like 'each' or 'foreach', for that use case I
would just use an idiomatic Lua loop.


Should I really say it? ;-)






Which I would write like this:

      local odd_items = ifilter(is_odd, ipairs(t))
      local new_table = imap(function(i, v) return v * v end,
ipairs(odd_items))


Ok, you have the iterators variant of map/filter, at least for the
input, but not the output. If I were to use map/filter, I would choose
my version[2] with iterator input and output.





The example would look like

      local new_t = {}
      for _,w in map( function( i, v ) return v * v end, filter( is_odd,
ipairs( t ) ) ) do
        new_t[ #new_t+1 ] = w
      end



Returning iterators works ok, but is a) harder to chain (try adding a
couple more transformations and you'll see what I mean) and b) can get a
little awkward when you want to store the final result.

As it stands your example still contains the boilerplate of creating and
assigning to a new table.


Addressing above criticism:

local f1, s1, v1 = ipairs( t )
local f2, s2, v2 = filter( is_odd, f1, s1, v1 )
local f3, s3, v3 = map( function( i, v ) return v * v end, f2, s2, v2 )
local new_t = icollect( 2, f3, s3, v3 )   -- [1]
But then again you have two more public functions (collect/icollect) someone else has to look up (or even three: the icollect below happily adds holes to the result array, you may need a version which doesn't). The "boilerplate" is pretty obvious in comparison (you can even see which value is added to the array and what will happen should w somehow end up being nil) and could handle two or more tables or other side effects. 




So you are *nearly* as flexible (no
break, only one key + one value, no numeric for, can't handle arrays
with holes, etc.) and *nearly* as efficient as Lua's for loop with 4
additional public functions (2 in my case).


map, filter, reduce, fold etc. don't intend to be flexible, they intend to
capture common computational patterns.
Of course they intend to be flexible, that's why they are primitives in most functional languages. And they succeed where everything is a list or a function. 


For the case that I can't express
something using a combination of functional primitives, I would fall back
to using plain imperative loops.
I do it the other way around (with an occasional tail recursive function for varargs). But why do you prefer the functional primitives at all? You don't get the benefits of functional languages like easy parallelization, code proofs, etc. in Lua and you force readers of your code to be familiar with those functions. That is not much of a problem for map and filter, because anyone who has ever seen a functional language knows exactly what they do (*in functional languages*, but as I argued elsewhere not necessarily in Lua). This whole discussion is proof, that currently there is no consensus how a map-function in Lua should behave. But even if you know what reduce, foldl, foldr, zip, etc. do in Lua, reading a complicated expression of those needs getting used to. 



In terms of efficiency I wouldn't worry too much about creating a few extra
tables.
That's the problem with garbage-collected languages: As soon as you don't have to carry out the garbage yourself, you stop caring how much garbage you create. The few extra tables are *linear* with respect to the input size, meaning that those few extra tables can increase the memory allocation for that part of the code a few hundred percent. At least the asymptotic behavior is unchanged. In terms of efficiency I'm satisfied with the full iterator version (-> constant memory overhead). So this is not the reason why I don't use (my) map/filter. 


If you're looking at a performance hotspot you can write imperative
code or fall back to C as needed.
True, but lesser so if you write library code, because you might never run the final program to observe the performance hotspot. And it's not that you have to work hard to avoid those temporaries -- you just have to do the obvious thing ... 



/ Tom



Philipp


  [1]:
    do
      local function icollect_helper( t, i, n, f, s, var_1, ... )
        if var_1 ~= nil then
          t[ i ] = select( n, var_1, ... )
          return icollect_helper( t, i+1, n, f, s, f( s, var_1 ) )
        end
        return t, i-1
      end

      function icollect( n, f, s, var )
        return icollect_helper( {}, 1, n, f, s, f( s, var ) )
      end
    end