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.

Espere aí, é impossível!

Implementar estas operações de lista sem usar nenhuma função embutida é praticamente impossível em Roc, porque você precisa de uma forma de adicionar elementos no fim ou no início de uma lista. Em outras linguagens, você pode usar operadores como : em Haskell ou += em Python, mas em Roc você precisa usar as funções de List.

Então, neste exercício, você pode usar List.append (mas evite usar qualquer outra função embutida).

Muitas linguagens de programação funcional usam listas encadeadas como o principal tipo de coleção. Em uma lista encadeada, adicionar um elemento no início ou remover o primeiro elemento é eficiente, então, nessas linguagens, você implementaria as operações de lista usando List.prepend. Em Roc, porém, uma List é um array (um bloco contíguo de bytes). Arrays têm propriedades diferentes das listas encadeadas, como a capacidade de acessar elementos por índice com eficiência e de adicionar novos elementos ao final. Por isso, em Roc usamos List.append com frequência e raramente usamos List.prepend.

Nomenclatura

Roc usa nomes um pouco diferentes dos listados nas instruções gerais:

• concat em vez de append
• join em vez de concatenate
• len em vez de length
• fold em vez de foldl
• fold_rev em vez de foldr

No entanto, os seguintes nomes de função são padrão em Roc:

• filter
• map
• reverse

Dica

Experimente usar:

match list {
    [] => ...
    [first, .. as rest] => ...
}

ou

match list {
    [] => ...
    [.. as rest, last] => ...
}