Lista Funcional em JavaScript

JavaScript apresenta algumas caracteristicas de linguagens funcionais, como tratar funções como cidadões de primeira classe. Neste post, mostro uma implementação de uma lista funcional em JavaScript. Definição da lista:

// construtoras
function Nil () {
 return []
}
function Cons (e,l) {
 return [e].concat (l);
}
// acesso
function empty (l) {
 return l.length == 0
}
function head (l) {
 return l[0]
}
function tail (l) {
 return l.slice (1, l.length)
}

A partir destas operações podemos tratar o array do JavaScript como listas funcionais. A seguir é apresentado a função foldr presente em Haskell. Ela descreve um comportamento comum a diversas operações, como somatoria, produto e até mesmo a operação de inserção:

function foldr (f,z,l)
{
 if (empty (l)) return z
 else return f (head (l), foldr (f,z,tail (l)) )
}
function sum (l) {
 return foldr (function (a, b) {return a+b},0,l)
}
function prod (l) {
 return foldr (function (a, b) {return a*b},1,l)
}
function insert (e, l) {
 if (empty (l) || e < head(l) ) return Cons (e, l)
 else return Cons (head (l), insert (e, tail (l)))
}

function insertion_sort (l) {
 return foldr (insert,[],l)
}

Usando as funções acima:

var l = Cons (8, Cons (5, Cons (10, Nil()))) // 8, 5, 10
var lo = insertion_sort (l) // 5,8, 10

Advertisement