Operações com listas

Instruções

Implementa operações básicas com listas.

Em linguagens funcionais, operações sobre listas como length, map e reduce são muito comuns. Implementa uma série de operações básicas com listas, sem usar as funções já existentes.

O número exato e os nomes das operações a implementar variam de track para track, para evitar conflitos com nomes já existentes, mas as operações gerais que vais implementar incluem:

• append (dadas duas listas, acrescenta todos os itens da segunda lista ao fim da primeira lista);
• concatenate (dada uma série de listas, combina todos os itens de todas as listas numa única lista achatada);
• filter (dado um predicado e uma lista, devolve a lista de todos os itens para os quais predicate(item) é True);
• length (dada uma lista, devolve o número total de itens que ela contém);
• map (dada uma função e uma lista, devolve a lista dos resultados de aplicar function(item) a todos os itens);
• foldl (dada uma função, uma lista e um acumulador inicial, aplica fold (reduce) a cada item no acumulador, a partir da esquerda);
• foldr (dada uma função, uma lista e um acumulador inicial, aplica fold (reduce) a cada item no acumulador, a partir da direita);
• reverse (dada uma lista, devolve uma lista com todos os itens originais, mas pela ordem inversa).

Repara que a ordem pela qual os argumentos são passados às funções de fold (foldl, foldr) é importante.

Implementação

Vais precisar de usar polimorfismo de parâmetros do Odin (mais comummente chamado de genéricos) neste exercício . Se ainda não viste esta funcionalidade antes, aqui fica um resumo rápido para começares.

O polimorfismo de parâmetros é uma funcionalidade das linguagens de programação que permite aos programadores serem menos específicos (mais genéricos, daí o nome) quanto aos tipos usados no seu código, mantendo ainda assim a segurança de tipos. Obviamente, isto só faz sentido em linguagens fortemente tipadas como o Odin.

Vamos começar com um exemplo. Digamos que queres incrementar todos os elementos de um array num valor fixo, um problema bastante simples.

incr_array_int :: proc(a: []int, by: int) -> []int {

    new_array := make([]int, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

E se agora também precisares da mesma funcionalidade para números de vírgula flutuante?

incr_array_f64 :: proc(a: []f64, by: f64) -> []f64 {

    new_array := make([]f64, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

E depois para inteiros sem sinal, números de vírgula flutuante de 32 bits, e por aí adiante?

Em pouco tempo acabas com uma infinidade de procedimentos que fazem exatamente a mesma coisa, mas sobre tipos diferentes. Se alguma vez precisares de atualizar a lógica, tens de garantir que o fazes para todas as variantes, o que pode dar muito trabalho de manutenção. A outra chatice é que tens de dar nomes diferentes a cada procedimento, porque o Odin não suporta sobrecarga implícita de procedimentos (ainda podes usar sobrecarga explícita, mas isso é conversa para outro exercício).

O Odin, sendo uma linguagem prática, oferece uma solução com o polimorfismo de parâmetros. Desde que o compilador consiga descobrir o tipo de um parâmetro em tempo de compilação, podes dar-lhe um nome genérico, como T. Vamos reescrever o procedimento acima:

incr_array :: proc(a: []$T, by: T) -> []T {

    new_array := make([]T, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

Repara que substituímos todas as anotações de tipo (int ou f64) por T e que a primeira ocorrência de T é precedida de um símbolo de dólar ($T). O tipo $T diz ao compilador do Odin que o nome T é um nome genérico para o tipo, a substituir pelo nome real durante a compilação. E, como o compilador agora conhece o tipo genérico T, as ocorrências seguintes do mesmo tipo só precisam de ser marcadas com o nome de tipo escolhido (T).

Agora podes escrever código como:

a_int := incr_array([]int{1, 2, 3}, 10)
a_f64 := incr_array([]f64{1.0, 2.0, 3.0}, 10.0)

Na primeira instrução, o compilador do Odin vai identificar o tipo do primeiro parâmetro ([]int) com o tipo do parâmetro genérico ([]$T), deduzir que T = int e passar a compilar uma versão com todas as ocorrências seguintes de T substituídas por int (equivalente à versão especializada incr_array_int() acima). Se omitisses o símbolo de dólar na definição do primeiro parâmetro, o compilador teria procurado, no pacote atual e na lista de importações, um tipo chamado T e muito provavelmente devolveria um erro de compilação Error: Undeclared name: T.

A segunda instrução funciona exatamente como a primeira, mas com o compilador a identificar T como f64.

É habitual dar aos tipos genéricos nomes de uma só letra (T e E são frequentemente usados).

Deves agora saber o suficiente sobre polimorfismo de parâmetros, também conhecido como tipos genéricos, para enfrentar o exercício Operações com Listas.