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.

Espera, é impossível!

Implementar estas operações de listas sem usar nenhuma função incorporada é praticamente impossível em Roc, porque precisas de uma forma de acrescentar elementos ao fim de uma lista ou de os inserir no início. Noutras linguagens podes usar operadores como : em Haskell ou += em Python, mas em Roc tens de usar as funções List.

Por isso, neste exercício podes usar List.append (mas evita usar qualquer outra função incorporada).

Muitas linguagens de programação funcional usam listas ligadas como o principal tipo de coleção. Inserir um elemento no início ou retirar o primeiro elemento de uma lista ligada é eficiente, por isso nessas linguagens implementarias as operações de listas com List.prepend. Em Roc, no entanto, uma List é um array (um bloco contíguo de bytes). Os arrays têm propriedades diferentes das listas ligadas, como a capacidade de aceder eficientemente a elementos por índice e de acrescentar novos elementos. Por isso, em Roc usamos List.append com frequência e raramente usamos List.prepend.

Nomenclatura

O Roc usa nomes ligeiramente diferentes dos que estão 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ções são padrão em Roc:

• filter
• map
• reverse

Dica

Experimenta usar:

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

ou

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