README.md

functional

Functional programming utilities implemented in pure Lua.

The motivation behind this module is, again, portability. If you want to embed this code on a webpage, or use it in some weird system for which a C binding wouldn't work, this project is aimed at you.

The docs can be found here, and were generated by LDoc. This module is published as a rock at luarocks.org/modules/wqferr/functional.

About

This module seeks to provide some utility functions and structures which are too verbose in vanilla Lua, in particular with regards to iteration and inline function definition.

The module is writen completely in vanilla Lua, with no dependencies on external packages. This was a decision made for portability, and has drawbacks. Since none of this was written as a C binding, it is not as performant as it could be.

For example, luafun is "high-performance functional programming library for Lua designed with LuaJIT's trace compiler in mind". If your environment allows you to use LuaJIT and performance is a concern, perhaps luafun will be more suited for your needs.

The motivation behind this module is, again, portability. If you want to embed this code on a webpage, or use it in some weird system for which a C binding wouldn't work, this project is aimed at you.

Teal

This project also includes functional.d.tl, which allows it to be used with Teal: a typed dialect of Lua. The Makefile included is a workaround so LuaRocks actually installs the .d.tl file as well.

Teal support is not complete, however, since some functions require features not yet stable on the Teal compiler side. For more information on how to use this library with Teal, see "Usage with Teal" below.

Learning the Ropes

If this is your first time using (or even seeing) these kinds of "stream manipulating operators" and all those other fancy words, don't worry: we'll start from the beginning.

Iterators

Sometimes called "streams", they are just that: some... thing that can produce values over time through iteration.

Let's say we want to get an array with the numbers from 1 to 10. Sounds easy?

local f = require "functional"

local my_counter = f.counter()
local my_capped_counter = my_counter:take(10)
local my_array = my_capped_counter:to_array()

print(type(my_array))
for i, v in ipairs(my_array) do
  print(i, v)
end

That may seem like a lot, but those three lines make sense if you think of each step individually. Starting from the top down:

f.counter() is a function that creates an iterator that just counts up. Forever. Well, this is a start, but we don't want an infinite array! We want to cut it short!

my_counter:take(10) will do just that: cut the previous thing short, and stop after 10 elements have gone through this step.

The to_array method just collects all the items in the stream into an array. That transforms the abstract and scary "iterator" into a more familiar face.

From that point on, it's just regular Lua: ipairs into printing.

Operator Chains

Now here's the neat part: you don't have to assign each step to a new variable. We don't even use most of them except to define the next step.

Instead, we can just collapse them all, as below:

local my_array = f.counter()     -- my_counter
                    :take(10)    -- my_capped_counter
                    :to_array()  -- my_array
for i, v in ipairs(my_array) do
  print(i, v)
end

And of course, the line breaks between each step are optional: I just put them there for clarity. In other words, you can create that 1-10 array in a single line!

What? You could've just typed {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, yeah, but what about getting an array with all numbers from 1 to 1000? You'd have to write a for loop, and for loops in Lua are verbose.

And this is the bare-bones example: how about we try something a little more interesting?

Filtering

Given a list of names, which ones contain the letter B? Let's assume you already have this chunk of code:

local names = {
  "Arya",
  "Beatrice",
  "Caleb",
  "Dennis"
}

local function has_b(name)
  if name:find("[Bb]") then
    return true
  else
    return false
  end
end

In pure Lua, you could write something like:

local names_with_b = {}
for _, name in ipairs(names) do
  if has_b(name) then
    table.insert(names_with_b, name)
  end
end

Here, has_b is called a predicate: a simple function which returns true or false for any given name. Predicates are especially good for filtering. Either you keep something, or you throw it out. In fact, the whole loop is a really common pattern: if predicate(val): keep(val). functional has the function filter and the operator :filter to do just that:

local names_with_b = f.filter(names, has_b):to_array()

Mapping

Now, what if you wanted all these names in all caps? In pure Lua, you'd have to change the core loop:

local names_with_b = {}
for _, name in ipairs(names) do
  if has_b(name) then
    table.insert(names_with_b, string.upper(name))
  end
end

In a functional environment, you can just add another operator. Since we're applying the same function to all elements in a stream, we can use the :map operator. It transforms (or "maps") every element in the stream to the return value of a function.

local names_with_b = f.filter(names, has_b)
  :map(string.upper)
  :to_array()

Now with line breaks for readability.

TODO Reducing

Lambdas

What are lambdas?

If you've never heard of lambdas, you might be thinking this is some sort of "ligma" joke. It isn't.

Many languages (including Lua!) have a way to declare anonymous functions. That is, a function that is declared "on the spot", just to be used as an argument to another function, or to be stored in a variable. What most of these languages have that Lua lacks is a shorthand notation for creating such functions.

In Lua, there's no getting around typing function() (plus parameters) and end. That's 13 characters typed minimum for the simplest anonymous functions. As an example, here's the definition of a function that doubles its argument:

triple = function(x) return 3*x end

Compare that to Python:

triple = lambda x: 3*x

That's nearly half the characters, and the Lua example doesn't even declare triple as a local. And JavaScript's is even shorter!

triple = (x) => 3*x

OK, but why does it matter?

It's perfectly fine to use vanilla Lua's notation to declare anonymous functions, and for anything more complex than a single operation, you should create a proper Lua function instead of using this library's lambdas. But for extremely short functions, it's nice to have a shortcut, both for coding quick and dirty examples and for readability.

Defining lambdas

The way you declare a lambda with functional is with a simple function call:

triple = f.lambda "(x) => 3*x"

This syntax is quite similar to the Javascript one, where the parameter names are given between parenthesis and there is an arrow separating the parameters from the body. The syntax also allows for higher order lambdas easily by chaining ()=> sections:

linear_combinator = f.lambda "(m) => (x, y) => m*x + y"
comb2 = linear_combinator(2)
print(comb2(3, 4)) --> 10

Security concerns and limitations

Under the hood, f.lambda uses load() (or loadstring() in older versions of Lua).

That means creating lambdas from unknown strings is a security risk.

If you're hardcoding all lambdas, it should be fine. There are some checks done internally before load() takes place, to prevent simple errors or naïve attacks. You can check the documentation proper for the exact restrictions, but you shouldn't run into any of them with simple functions.

Environments

By default, a lambda function's environment is set to an empty table. That means it only has access to its own parameters, and cannot read or write to globals or variables in the enclosing scope of its creation. For example, the following lambda:

local constant = 3.14
local l = f.lambda "() => constant"
print(l()) --> nil

Will print out nil: constant is an undefined variable from the lambda's point of view, so its value is nil since it was never assigned.

You can get around this and set the desired environment for a lambda as follows:

local constant = 3.14
local l = f.lambda("() => 3*con", {con=constant})
print(l()) --> 9.42

Or, as a shorthand:

local constant = 3.14
local l = f.lambda{"() => 3*con", con = constant}
print(l()) --> 9.42

Of course you could use (almost) any name you wish for the lambda environment variables. In this case, we chose to distinguish the names for con and constant for the sake of clarity for what is and isn't in the lambda scope.

You don't need :to_array() (probably)

In most cases, unless you specifically need an array, you can use the iterator itself in a for loop. For example, if we wanted to print all the names with "b", we could write:

local names_with_b = f.filter(names, has_b)  -- note the lack of :to_array()
for name in names_with_b do
  print(name)
end

This is preferred for a couple reasons: (1) it removes the need to allocate a new table which would be later discarded; and (2) it postpones processing to when it actually needs to happen.

The second point is due to iterators being lazy, in the technical sense. They don't actually go through their input and save whichever values they should return. Instead, whenever they're asked for the next value, they process it and return it.

This also means, however, that an iterator can't rewind. If you need to iterate through the same values twice, then maybe :to_array() is indeed the solution. If the sequence is too large to be put into an array, you could instead :clone() the iterator. It will make a snapshot of the iterator and all its dependencies, and return it as a new, independent iterator.

Yet another alternative is using the :foreach() operator: it applies the given function to all elements in a sequence. Rewriting the above example using :foreach():

local names_with_b = f.filter(names, has_b)
names_with_b:foreach(print)

Or simply:

f.filter(names, has_b):foreach(print)

Examples

Filter

Print all even numbers up to 10:

local is_even = function(v) return v % 2 == 0 end
f.range(1, 10)      -- run through all the numbers from 1 to 10 (inclusive)
  :filter(is_even)  -- take only even numbers
  :foreach(print)   -- run print for every value individually

Map

Fix capitalization on names:

local names = {"hellen", "oDYSseuS", "aChIlLeS", "PATROCLUS"}
local function fix_case(name)
  return name:sub(1, 1):upper() .. name:sub(2):lower()
end

for name in f.map(names, fix_case) do
  print("Fixed: ", name)
end

Reduce

Sum all numbers in a range:

local add(acc, new)
  return acc + new
end

local numbers = f.range(10, 120)
local sum = numbers:reduce(add, 0)
print(sum)

Lambdas

Keep even numbers

local numbers = {2, 1, 3, 4, 7, 11, 18, 29}
local is_even = f.lambda "v % 2 == 0"
local even_numbers = f.filter(numbers, is_even):to_array()

Or you could inline the lambda, which is the more common approach:

local numbers = {2, 1, 3, 4, 7, 11, 18, 29}
local even_numbers = f.filter(numbers, f.lambda "v % 2 == 0"):to_array()

Get first element of each row

local matrix = {
  {1, 2, 3}, -- first element of matrix
  {4, 5, 6}, -- second element of matrix
  {7, 8, 9}  -- third element of matrix
}

-- map will iterate through each row, and the lambda
-- indexes each to retrieve the first element
local vals = f.map(matrix, f.lambda "v[1]"):to_array()

Usage with Teal

It is recommended that you read the Learning the Ropes section first so you're not completely lost here.

Due to the nature of Lua, Teal's types can be a bit too strict at times. That's why Teal has casts. However, when you're dealing with functions, casts can be quite verbose, and this is something the library is meant to remedy!

For that, there are 3 aliases for common function types:

Alias	Explicit Teal type
consumer<T>	function(T)
producer<T>	function(): T
mapping<U, V>	function(U): V

Short story long: consumers take in a value and return nothing; producers take in nothing and produce a value; and mappings take a value and transform it into another.

A practical example

Let's say you want to print every third number up to 20, except if it's prime.

local is_prime = function(n: integer): boolean ... end
local my_numbers = f.range(20)
  :every(3)
  :filter(f.negate(is_prime))

So far, so good! is_prime is a mapping from integer to boolean, so negate properly propagates the types and filter accepts it, since range produces integers.

However, when we try to print the numbers:

my_numbers:foreach(print)

A type error! print is a consumer of any, but foreach expected a consumer of integers! A simple cast will suffice though:

my_numbers:foreach(print as f.consumer<integer>)