Tuesday, April 5, 2011

A functional (almost) prelude on the topic of mergesort

I know of table.sort, yes. But thought it was fun nonetheless.


function apply(x, f)
for i, v in ipairs(x) do
f(v, i)
end
end

function filter(x, f)
local out = {}
local fa = function(v, i)
if f(v, i) then table.insert(out, v) end
end
apply(x, fa)
return out
end

function merge(...)
local args = { ... }
local out = {}
local fa = function(v)
table.insert(out, v)
end
apply(args, function(v) apply(v, fa) end)
return out
end

function sort(x)
if #x < 2 then
return x
else
local ix = math.floor(#x/2)
local smallx = sort(filter(x, function(v) return v<x[ix] end))
local samex = filter(x, function(v) return v == x[ix] end)
local bigx = sort(filter(x, function(v) return v>x[ix] end))
return merge(smallx, samex, bigx)
end
end


function show(x)
apply(x, print)
end

a = { 1,3,2,4,2,1,1,23,12,22 }
show(sort(a))


NB: of course this is *not* a functional style by far, since the apply() assumes the f() will have the side effects.

No comments: