Operações com Listas

Instruções

Implemente operações básicas com listas.

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

O número e os nomes exatos das operações a serem implementadas vão depender da trilha, para evitar conflitos com nomes já existentes, mas as operações gerais que você vai implementar incluem:

• append (dadas duas listas, adicione todos os itens da segunda lista ao final da primeira lista);
• concatenate (dada uma série de listas, combine todos os itens de todas as listas em uma única lista achatada);
• filter (dados um predicado e uma lista, retorne a lista de todos os itens para os quais predicate(item) é True);
• length (dada uma lista, retorne o número total de itens dentro dela);
• map (dadas uma função e uma lista, retorne a lista dos resultados de aplicar function(item) a todos os itens);
• foldl (dados uma função, uma lista e um acumulador inicial, faça o fold (reduza) de cada item no acumulador, a partir da esquerda);
• foldr (dados uma função, uma lista e um acumulador inicial, faça o fold (reduza) de cada item no acumulador, a partir da direita);
• reverse (dada uma lista, retorne uma lista com todos os itens originais, mas em ordem inversa).

Observe que a ordem em que os argumentos são passados para as funções de fold (foldl, foldr) faz diferença.

Implementação

Você vai precisar usar polimorfismo de parâmetros de Odin (mais comumente chamado de generics) neste exercício. Se você nunca viu esse recurso antes, aqui vai um resumo rápido para você começar.

O polimorfismo de parâmetros é um recurso de linguagem de programação que permite aos programadores serem menos específicos (mais genéricos, daí o nome) quanto aos tipos usados no código, sem deixar de manter a segurança de tipos. Obviamente, isso só faz sentido em linguagens fortemente tipadas, como Odin.

Vamos começar com um exemplo. Digamos que você queira incrementar todos os elementos de um array em um valor fixo, um problema simples o bastante.

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 você também precisar da mesma funcionalidade para números de ponto 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 ponto flutuante de 32 bits, e assim por diante?

Em pouco tempo você acaba com uma infinidade de procedimentos que fazem exatamente a mesma coisa, mas com tipos diferentes. Se um dia você precisar atualizar a lógica, vai ter que garantir que fez isso em todas as variantes, o que pode virar bastante trabalho de manutenção. Outro incômodo é que você precisa dar nomes diferentes a cada procedimento, já que Odin não oferece sobrecarga implícita de procedimentos (você ainda poderia usar sobrecarga explícita, mas isso é assunto para outro exercício).

Odin, por ser uma linguagem prática, oferece uma solução com polimorfismo de parâmetros. Desde que o compilador consiga descobrir o tipo de um parâmetro em tempo de compilação, você pode dar a ele um nome genérico, como T. Vamos reescrever nosso 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
}

Repare que substituímos todas as anotações de tipo (int ou f64) por T e que a primeira ocorrência de T é precedida por um cifrão ($T). O tipo $T diz ao compilador de Odin que o nome T é um nome genérico para o tipo, a ser substituído 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 ser marcadas com o nome de tipo escolhido (T).

Agora você pode 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 de Odin vai identificar o tipo do primeiro parâmetro ([]int) com o tipo do parâmetro genérico ([]$T), deduzir que T = int e 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 você omitisse o cifrão na definição do primeiro parâmetro, o compilador procuraria no pacote atual e na lista de importações um tipo chamado T e provavelmente retornaria um erro de compilação Error: Undeclared name: T.

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

É costume dar a tipos genéricos nomes de uma única letra (T e E são bastante usados).

Agora você já deve saber o suficiente sobre polimorfismo de parâmetros, também conhecido como tipos genéricos, para encarar o exercício List Operations.