Questão 10: intersperse

Voltar

Apresente uma definição recursiva da função (pré-definida) intersperse :: a -> [a] -> [a] que, dado um elemento e uma lista, constrói uma lista em que o elemento fornecido é intercalado entre os elementos da lista fornecida.

Exemplo

> intersperce 1 [10,20,30]
[10,1,20,1,30]

Resolução

Clica para revelar

intersperse :: a -> [a] -> [a]
intersperse _ [] = []
intersperse _ [h] = [h]
intersperse x (h:t) = h : x : intersperse x t

Explicação

Clica para revelar

Para esta função, apenas precisamos de percorrer a lista fornecida, colocando o elemento dado em cada chamada recursiva.

intersperse :: a -> [a] -> [a]
intersperse _ [] = []
intersperse x (h:t) = h : x : intersperse x t

Contudo, esta definição tem um problema. Vamos usá-la num exemplo concreto. Qual será o resultado de intersperse 1 [10,20,30] com a nossa definição?

intersperse 1 [10,20,30] =
    = 10 : 1 : intersperse 1 [20,30] =
    = 10 : 1 : 20 : 1 : intersperse 1 [30] =
    = 10 : 1 : 20 : 1 : 30 : 1 : intersperse 1 [] =
    = [10,1,20,1,30,1]

Temos ali um 1 a mais no fim da lista. Quando a lista só tem um elemento, a função está a colocar o valor fornecido entre o elemento da lista e o fim da mesma. Contudo, neste caso, não é possível intercalar, são precisos pelo menos 2 elementos na lista.

Desta forma, precisamos de um novo caso de paragem. Por outras palavras, a função não deve parar quando a lista está vazia, mas sim quando tem apenas um elemento, para evitar o comportamento indesejado.

intersperse :: a -> [a] -> [a]
intersperse _ [] = []
intersperse _ [h] = [h]
intersperse x (h:t) = h : x : intersperse x t

Apesar de, agora, a definição para a lista vazia não ser necessária para a recursão, devemos mantê-la de forma a ter uma definição mais completa. Caso contrário, ao chamar a função com uma lista vazia, obteríamos um erro.