luafun/luafun

Lua Fun is a high-performance functional programming library for Lua designed with LuaJIT's trace compiler in mind.

Lua Functional

Lua Fun is a high-performance functional programming library for Lua designed with LuaJIT's trace compiler in mind.

Lua Fun provides a set of more than 50 programming primitives typically found in languages like Standard ML, Haskell, Erlang, JavaScript, Python and even Lisp. High-order functions such as map, filter, reduce, zip, etc., make it easy to write simple and efficient functional code.

Let's see an example:

> -- Functional style
> require "fun" ()
> -- calculate sum(x for x^2 in 1..n)
> n = 100
> print(reduce(operator.add, 0, map(function(x) return x^2 end, range(n))))
328350

> -- Object-oriented style
> local fun = require "fun"
> -- calculate sum(x for x^2 in 1..n)
> print(fun.range(n):map(function(x) return x^2 end):reduce(operator.add, 0))
328350

Lua Fun takes full advantage of the innovative tracing JIT compiler to achieve transcendental performance on nested functional expressions. Functional compositions and high-order functions can be translated into efficient machine code. Can you believe it? Just try to run the example above with luajit -jdump and see what happens:

-- skip some initialization code --
->LOOP:
0bcaffd0  movaps xmm5, xmm7
0bcaffd3  movaps xmm7, xmm1
0bcaffd6  addsd xmm7, xmm5
0bcaffda  ucomisd xmm7, xmm0
0bcaffde  jnb 0x0bca0024        ->5
0bcaffe4  movaps xmm5, xmm7
0bcaffe7  mulsd xmm5, xmm5
0bcaffeb  addsd xmm6, xmm5
0bcaffef  jmp 0x0bcaffd0        ->LOOP
---- TRACE 1 stop -> loop

The functional chain above was translated by LuaJIT to (!) one machine loop containing just 10 CPU assembly instructions without CALL. Unbelievable!

Readable? Efficient? Can your Python/Ruby/V8 do better?

Status

Lua Fun is in an early alpha stage. The library fully documented and covered with unit tests.

LuaJIT 2.1 alpha is recommended. The library designed in mind of fact that LuaJIT traces tail-, up- and down-recursion and has a lot of byte code optimizations. Lua 5.1-5.3 are also supported.

This is master (development) branch. API may be changed without any special notice. Please use stable branch for your production deployments. If you still want to use master, please don't forget to grep git log for Incompatible API changes message. Thanks!

Please check out documentation for more information.

Misc

Lua Fun is distributed under the MIT/X11 License - (same as Lua and LuaJIT).

The library was written to use with Tarantool - an efficient in-memory store and an asynchronous Lua application server.

See Also

• Documentation
• RockSpec
• RPM/DEB packages
• Hacking
• [email protected]
• [email protected]
• [email protected]

Please "Star" the project on GitHub to help it to survive! Thanks!

---

Lua Fun. Simple, Efficient and Functional. In Lua. With JIT.

luafun's Issues

Is this repo alive?

intersperse should not add to end of array

I noticed this is actually called out in the code here

Though I understand if this breaking change is too late to fix now

Is this still in development?

And do you know any alternatives?

the order of arguments in `reduce`

Why in reduce definition the function comes as first parameter and init value as second? Such order of arguments is inconvenient for using in MoonScript for example. Does this argument order impact on performance?

How to sum digits in a string?

I've tried the following:

local data = "ms0010110"
data:gmatch("%d"):sum() -- runtime error
sum(data:gmatch("%d")) -- runtime error
data:gmatch("%d"):reduce(operation.add, 0) -- runtime error

-- but this works fine
local total = 0
for digit in data:gmatch("%d") do
  total = total + digit
end

What have I misunderstood?

For some background info, this script is just parsing the various messages reported over the serial line of some old motion controllers. If the result is > 0 we know that there are still axes reporting activity, otherwise we can proceed with whatever foobarbizbaz needs to happen once the motors are positioned.

question about operations on tables

What is the recommended way to perform operations on tables?
For example, I have a table of scores and want to create a new table where the scores are doubled.

fun = require("fun")
scores = {7, 4, 12}
function double(n) return n * 2 end
newScores = fun.map(double, scores) -- passing scores here is wrong

Combination of zip and iterators with multiple return values drops all values after first

Example:

tarantool> fun.duplicate(1, 2, 3):take(3):each(print)
1       2       3
1       2       3
1       2       3
---
...
tarantool> fun.zip({1, 2, 3}, fun.duplicate(1, 2, 3)):take(3):each(print)
1       1
2       1
3       1
---
...

Expected:

tarantool> fun.duplicate(1, 2, 3):take(3):each(print)
1       2       3
1       2       3
1       2       3
---
...
tarantool> fun.zip({1, 2, 3}, fun.duplicate(1, 2, 3)):take(3):each(print)
1       1       2       3
2       1       2       3
3       1       2       3
---
...

Probably error is in zip_gen_r in line:

local state_x, r = gen_x(param_x, state[i])

where other values are dropped

Force iter to consider argument as table or map?

Is there a way to force iter to consider argument as table or map? It is useful when dealing with tables that can be both.

function 'foldl' causes stack overflow error

The function 'foldl' causes stack overflow when 'chain' is used as accumulating function.

2017-06-09 22:34:52.671 [34859] main/628/main [C]:-1 E> main:  builtin/fun.lua:47: **stack overflow**
stack traceback:
        builtin/fun.lua:47: in function 'gen_x'
        builtin/fun.lua:953: in function 'gen_x'
        builtin/fun.lua:953: in function 'gen_x'
        builtin/fun.lua:953: in function 'gen_x'
        builtin/fun.lua:953: in function 'gen_x'
        builtin/fun.lua:953: in function 'gen_x'
        builtin/fun.lua:953: in function 'gen_x'
        builtin/fun.lua:953: in function 'gen_x'
        builtin/fun.lua:953: in function 'gen_x'
        builtin/fun.lua:953: in function 'gen_x'
        builtin/fun.lua:953: in function 'gen_x'
        ...
        builtin/fun.lua:953: in function 'gen_x'
        builtin/fun.lua:953: in function 'gen_x'
        builtin/fun.lua:953: in function 'gen_x'
        builtin/fun.lua:773: in function 'totable'

How to reproduce:

-- Make an array containing 10000 arrays  {{1,2}, {2, 4}, {3, 6}, ...}:
local a = map(function (x) return {x, x+x}, range(10000))
-- use foldl and chain to flatten an array to get something like {1,2,2,4,3,6,...}
local f = foldl(function (acc, x) return chain(acc, x) end, {}, a)
-- convert iterator to table
totable(f)

toarray, tomap support

It would be convenient if there was a function to convert an iterator to an array, or an iterator of tuples to a map.

The equivalent of pythons list(...) and dict(...) respectively.

[feature request] chain from iterable, bind?

Hey,

one composition that seems to be missing is chaining iterators when the list of iterators is given as an iterator - similar to itertools.chain.from_iterable in python.

E.g. something like this:

function chain_from_iterable(iter, gen, state)
  return chain(table.unpack(totable(iter, gen, state))
--return reduce(chain, {}, iter, gen, state)
end

But of course without going through the intermediate table (or doing the reduction) - which might be large, time consuming or even infinite.

IMO, chain_from_iterable is more natural and can easily be used to implement chain = function(...) return chain_from_iterable({...}) end, but not the other way round.

list comprehensions

with this function, you can implement the bind operation of monads (i.e. Haskell's >>=) like this:

function bind(x, f)
  return chain_from_iterable(map(f, x))
end
getmetatable((wrap({}))).__index.bind = bind

which allows to write something like list comprehensions

function even(n) return n%2 == 0 end

range(10):filter(even):bind(function(a) return
  range(a):map(function(b) return
    a*b
  end)
end):each(print)

corresponding to a generator expression such as this:

(a*b
 for a in range(10)
 if a%2 == 0
 for b in range(a))

it seems confused to has 'op' (and 'operator') in methods table.

min_by documentation and implementation

min_by function documentation contradicts itself:

Return a minimum value from the iterator using the cmp as a < operator. The iterator must be non-null, otherwise an error is raised.

Examples:

function min_cmp(a, b) if -a < -b then return a else return b end end
print(min_by(min_cmp, range(1, 10, 1)))
9

If cmp was really used as a < operator, the example should have looked like this:

function min_cmp(a, b) return -a < -b end
print(min_by(min_cmp, range(1, 10, 1)))
9

I think using cmp as a < operator makes more sense, since it matches table.sort behavior. In addition, I would also prefer min_by/max_by to accept two functions: prj and cmp. prj would default to identity and cmp would default to < or > respectively. For example, if I wanted to find the most distant location from home, I would use something like:
iter(locations):min_by(function(l) return l:dist2(home) end)
In this implementation, cmp could be omitted in most cases, since < (implemented as a __le metamethod for custom types) would suffice. You would also need to project each item only once, so this could potentially improve the performance.

Another nitpick is that range() is inclusive on both endpoints, so the real return value from that example should be 10, not 9

Added support of multi args pass to each.

Passed only one arg to function:

One arg:

tarantool> fun.each(function (a,b) print(a,b) end, {'some','data'})
some    nil
data    nil

---
...

With more than one args to function:

tarantool> fun.each(function (a,b) if b ~= nil then print(a) end end, {'some','data'}, 1234)

---
...

[Q] cartesian product of lists

I see the related #36 ...
what's the best way to generate the cartesian product of 2 lists currently, with the available functions?

P.S. I see no Discussion/chat mentioned. May there's one? besides the Matrix room on general Lua: https://matrix.to/#/#LuaLang:matrix.org

What is missing? How to help?

Hello. It would be nice some documentation explaining what is still missing for this project or how to help. The project's idea is quite nice.

Inconsistency between code&documentation of `partition`.

Documentation says that partition returns {gen1, param1, state1}, {gen2, param2, state2}, yet what is really being returned is gen1, gen2, param2, state2.

`operator.mul` missing from API Reference

The function operation.mul is missing from the online API Reference . I believe it should be between mod and neq.

Pattern matching syntax

Does Luafun have a syntax for pattern matching, similar to functional programming languages such as Elixir?

I wish Luafun had something similar to the ex-patterns JavaScript library, which implements Elixir-style pattern matching.

Using io.lines() as an iterator

Hi! For some command-line experimenting, I would love to do things like:

each(print, io.lines())

Of course with many more transformations applied. However, such things don't work. Studying the source, I see why:

local call_if_not_empty = function(fun, state_x, ...)
    if state_x == nil then
        return nil
    end
    return state_x, fun(...)
end

local each = function(fun, gen, param, state)
    repeat
        state = call_if_not_empty(fun, gen(param, state))
    until state == nil
end

Normal usage of io.lines() outside of a magical for loop:

fn = io.lines()
print(fn()) -- line 1
print(fn()) -- line 2

However, it appears that call_if_no_empty takes the state, which in this case is the line, and only checks it for being nil.

Is this a missing generalization or just the io.lines() style of iteration being incompatible with luafun?

Fix support of Lua 5.3

roman@desktop:~/luafun/tests$ lua5.3 ./runtest *.lua
Testing basic.lua
lua5.3: ./runtest:54: attempt to call a nil value (global 'loadstring')
stack traceback:
        ./runtest:54: in local 'process'
        ./runtest:86: in main chunk
        [C]: in ?

sorted iterators

When I write anything in Lua using luafun, I frequently could directly convert Perl 1-liner approach (if there are map or grep iterators, etc), but there is an important omission - there is no support for sorted iterators in luafun, for this we need to use separate table.sort. It would be nice to create wrappers of

• sort and reverse iterators to provide access in ascending and descending order.

i.e. try to convert this perl one-liner into lua one-liner?

git log --pretty='%an' \
$(git merge-base origin/2.10 origin/master)..origin/master|\
perl -ne 'chomp;' -e '$N{$_}++;' \
-e 'END{ print map { "$_\t$N{$_}\n" } sort {$N{$b} <=> $N{$a} 

Side traces

I am really happy to discover this project! I am also interested in writing code that specifically exploits the strengths of LuaJIT. I find your example on the README very powerful.

There is one optimization challenge on my mind that I think we share: how to prevent unwanted side-traces. I have written a little bit about this over at LuaJIT/LuaJIT#208 and had some success with optimizations - but not really nailed the issue closed.

Here is an illustration of how it seems to affect luafun. Consider this example program that is based on the README but with multiple operations:

require("fun")()
local n = 100
print(reduce(operator.add, 0, map(function(x) return x^2 end, range(n)))) -- first
print(reduce(operator.add, 0, map(function(x) return x^2 end, range(n)))) -- second

The first call does indeed compile down to a tight loop of around 10 instructions. However, the second call compiles down to around 62 instructions - even though it is exactly the same code! The difference is that the second call is compiling to a side trace within the reduce() subroutine and on each iteration it re-enters the root trace and repeats all of the loop invariant code. So you end up with the first call compiling very tight while the subsequent ones are less efficient. There is a cumulative effect too: each call will create a new side-trace, and the side traces will be chained together, and each link in the chain will add around 9 more instructions.

Just wondering: are you already aware of this issue? If not then you may be able to solve it in a neat way using the tips from @corsix in LuaJIT/LuaJIT#208. If you are already aware of this I would be very interested in your view e.g. if you already have some recommendations that you make to users to explain the best usage and generally set expectations.

Sadly it seems like the simplest workaround would be to avoid programming in a functional style :-) because the problem only arises when many different pieces of code are all executing the same loop statement (for, while, etc) in the source code. If you would write for ... end every time then you have no problem because each for bytecode will have a separate trace complex.

pluck a property?

fun.totable(
  fun.map(
    fun.pluck('foo'),
    {{foo = 1}, {foo = 2}}
  )
) -- {1, 2}

missing flatmap and its recursive version?

items, keys, values (pairs support)

The problem currently is that pairs doesn't work with fun, because it returns the key and value instead of key(state), key, value.

This means there is no way to iterate over sparse arrays and mixed tables.

I'd propose adding an items(tbl) iterator that works with a modified pairs to return all key, value pairs in the table. Likewise values() which can easily be defined as iter(pairs(tbl)). keys is maybe not needed because you can just ignore the value from items().

In moonscript:

items = (tbl) ->
    gen = (param, state) ->
          k, v = next param, state
          return k, k, v

    return iter gen, tbl, nil

values = (tbl) -> iter pairs(tbl)

What do you guys think?

A curry()/partial() function for even more functional style

I read your comment #31 about giving over working on this project, but just in case - a fundamental function in the functional style is curry().

For example, instead of each(function(el) draw(time, el) end, els) we'd write each(partial(draw, time), els) which is more clear because there are no long function definition. With more arguments a curry/partial function would be even more useful.

Minor error in documentation

The doc say that cdr is an alias for head, but it's an alias for tail.
http://rtsisyk.github.io/luafun/slicing.html#fun.cdr

GroupBy Support

Feature request:
It would be nice to add the GroupBy function to the library to make groups with aggregation

Clone function

Hi

Could you include some cloning function in luafun?
I mean something that produces completely independent copy of argument?

Haskell style is ok until there is no risk of changing original arguments/tables.
Lua/LuaJIT does not match entirely here unfortunately.

BTW, deepcopy seems to exists, but it's declared local.

map_gen() is defined twice

the name map_gen is used twice as local functions. In both cases it's used immediately by some function that is close by. It seems a bit dangerous though in case the code is ever shifted around.

One or the other should probably change name. Maybe one could be gen_map?

remove_if name misleading

Documentation says:

fun.remove_if(predicate, gen, param, state)
iterator:remove_if(predicate)

An alias for filter().

The name remove_if strongly suggests that elements satisfying the predicate will be removed, keeping only those that do not satisfy the predicate; while filter actually keeps the elements satisfying the predicate.

In other words, the linguistic expectation would be that remove_if is sugar for filter(function(x) return not p(x) end).

(Of course it’s your call how to solve this without breaking existing code if any. I’d suggest deprecating the remove_if name for a while.)

Immutability

Hi :)

Does your documentation lack passages about the core feature of functional programming or does your implementation?

Create RPM spec

subj

nth slicing function doesn't work as intended

Documentation says that nth should return n-th element from iterator, which is not true for some cases.
Example:

tarantool> require "fun"()

tarantool> nth(1, drop_while(function(t) return t ~= "5" end, "123456789")) -- expecting '5'
---
- '1'
...

tarantool> nth(1, drop_while(function(t) return t ~= 5 end, {1,2,3,4,5,6,7,8,9})) --expecting 5
---
- 1
...

tarantool> nth(1, drop_while(function(t) return t ~= 5 end, range(9))) -- now it's correct
---
- 5
...

question about iterators

I want to learn how to use a for loop to loop over the values in an iterator.
Why doesn't the for loop below work?
The error I get is "attempt to index a nil value"

fun = require("fun")
scores = {7, 4, 13}
function double(n) return n * 2 end
iter = fun.map(double, scores)
for v in iter() do
  print(v)
end

Rock fails to install

So apparently github blocks git:// now, which causes installation to fail as the rockspec on luarocks.org hasn't yet been updated to use git+https:// instead. Simply uploading a new version of the rockspec that uses HTTPS should easily fix this problem.

Bitwise functions in fun.operator removal

Hi All,

Thanks for your great feedback!

I see that I added to many unnecessary wrappers in operator module:

band = bit.band,
rol = bit.rol,
ror = bit.ror,
arshift = bit.arshift,
lshift = bit.lshift,
rshift = bit.rshift,
bswap = bit.bswap,
bor = bit.bor,
bnot = bit.bnot,
bxor = bit.bxor,

min = math.min, 
max = math.max,

Functions from bit and math can be directly used without these worthless wrappers. Furthermore, different versions of Lua have different bit modules (LuaJIT - bit, Lua 5.2 - bit32, Lua 5.1 - nothing).

I plan to remove the shortcuts above from API. Note that mod, pow are not affected because Lua has corresponding operator in language and this shortcuts make sense. This fix is also needed for #4.

I can add version detection (and disable bitops on 5.1) as an alternative. I found universal bitops modules in Rocks repository and I think that we don't need another one.

Any suggestions?

Using a wrong table length when nil is in a table

luafun uses # to get a table size. However "if the array has "holes" (that is, nil values between other non-nil values), then #t can be any of the indices that directly precedes a nil value.", see http://www.lua.org/manual/5.1/manual.html#2.5.5.
Probably it would be better to use table.maxn(), this function does a linear traversal of the whole table, but provides a real length of array.

Example of current behavior of iter with array with nil:

tarantool> for _it, a in fun.iter({1, 2, 3}) do print(a) end
1
2
3
---
...

tarantool> for _it, a in fun.iter({1, nil, 3}) do print(a) end
1
---
...

tarantool> 

Advantage of changing legth function - 'real' length is better for users.

And disadvantages are:

• With table.maxn() luafun operations that accept arrays may get a slowdown (due to traversal of the whole table).
• Changing of the old behavior may broke backward compatibility.

I think it at least needs to be described in Luafun documentation if no fixes is planned for this.

Create Debian spec

I already has packages for Debian/Ubuntu/Fedora/Centos:
https://packagecloud.io/rtsisyk/master?page=1 (search for tarantool-fun).
It would be nice to push deb package to the main repository.

Remove analytics from documentation

Google Analytics is I think the most privacy invasive option that could have been chosen. I don't understand, why would analytics even be needed in documentation anyway.

Missing functions: foldr, reverse

I'm trying to reduce an array right-to-left. In Haskell, I would use foldr for that, but that's missing in luafun. Alternatively, one could build it by applying foldl to a reversed array, but the reverse function is also missing. I think both functions should be present in a good functional library.

Setup CI/CD workflows

As Travis CI is dead I propose to setup GH Actions with CI/CD where:

• automatically generate Sphinx docs per push
• publish HTML files generated by Sphinx to gh-pages on tag push (?)
• run tests (see appropriate section in .travis.yaml) with
  • lua 5.1
  • lua 5.2
  • lua 5.3
  • lua 5.4
  • luajit (latest)
  • tarantool 1.10
  • tarantool 2.[2-8]
• run doc tests to test examples from documentation
• run luacheck (?)

Non-JIT Lua support

I was asked about non-JIT Lua support many times, so I decided to open the ticket and fix the compatibility with reference Lua implementations ASAP.

fn.nth(3, "abc") == nil

Hello. Here is simple test case:

print(fn.nth(3, {"a", "b", "c"})) -- prints c
print(fn.nth(2, "abc")) -- prints b
print(fn.nth(3, "abc")) -- prints nil

[Feature Request] Add Flatten function

It would be very cool to have. I sometimes face problems where I have a table of tables like

{
  { "thing1", "thing2" },
  { "thing3", "thing4" },
  -- ...
}

And want to flatten this mess out using just one simple operation:

fun.flatten(mess)

And get this majestic data structure in the end:

{
  "thing1",
  "thing2",
  "thing3",
  "thing4",
  -- ...
}

I realize that I can simulate flatten with reduce and chain, but it's far less intuitive

fun.reduce(function(acc, x) return fun.chain(acc, x) end, {}, mess)

in Fennel it's a bit nicer, but still noisy

(fun.reduce #(fun.chain $1 $2) [] mess)