The Lua Combinatory Logic Zoo!

README.md

The Lua script CurryZoo.lua contains a basic 'zoo' of cobinatory logic. It's mainly for demonstration, mind you. There's no entrypoint.

• S, K and I combinators are the most basic combintors;
• Functions like 'map' and 'apply', or 'filter', these are 'functors'. The 'map' function is homomorphic with the * operator which is the 'transitive closure operator', but it appears in regular expression as the 'zero or more operator'. A lot is to be said about these.
• A parsec (parser combintor). zero_or_more is homomorphic (or isomorphic? dunno I'm learning myself) with map.

Enjoy.

CurryZoo.lua

#!/usr/bin/env lua

function I(x)
	return x
end

function K(x, y)
	return x
end

function S(fn, gn, x)
	return gn(fn(x), gn(x))
end

function map(fn, a)
	local result = {}
	for x in a do
		table.insert(result, fn(x))
	end
	return result
end

function fold_left(fn, a, init)
	local result = init
	for i = 1, #a do
		result = fn(result, a[i])
	end
	return result
end

function fold_right(fn, a, init)
	local result = init
	for i = #a, 0 do
		result = fn(result, a[i])
	end
	return result
end

function apply(fn, a)
	local result = a
	for i = 1, #a do
		result[i] = fn(result[i])
	end
	return result
end

function filter(fn, a)
	local result = {}
	for x in a do
		if fn(x) then
			table.insert(result, x)
		end
	end
	return result
end

function condition(fn, consumer, modifier)
	return function()
		local x = consumer()
		assert(fn(x))
		return modifier(x)
	end
end

function zero_or_more(parser, modifier)
	return function()
		local result = {}
		while not eof() do
			ps = save_parser(parser)
			ok, res = pcall(parser)
			if not ok then
				restore_parser(parser, ps)
				break
			else
				table.insert(result, modifier(res))
			end
		end
		return result
	end
end

function one_or_more(parser, modifier)
	local rest = zero_or_more(parser)
	return function()
		return modifier(table.concat(parser(), rest))
	end
end