Listas, compreensões e algoritmos recursivos

Construir, aceder e gerar

• x:xs acrescenta uma cabeça em tempo constante; xs ++ ys percorre xs. 3:5 nem sequer tem tipo: o lado direito de : tem de ser uma lista.
• head e tail exigem lista não vazia. xs !! i exige 0 <= i < length xs, a contar de zero. take n e drop n aceitam a lista vazia; para n <= 0 dão [] e a lista original.
• zip para na lista mais curta; length e reverse precisam de listas finitas.
• Numa compreensão, o primeiro gerador é o exterior: [(x,y) | x <- [1,2], y <- [4,5]] dá [(1,4),(1,5),(2,4),(2,5)]. Um gerador dependente só usa nomes de geradores anteriores; trocar a ordem pode deixar x por definir.

indices :: Eq a => a -> [a] -> [Int]
indices valor xs = [i | (x,i) <- zip xs [0..], x == valor]
-- indices 'a' "casa" = [1,3]

A enumeração [0..] é infinita, mas zip para ao acabar xs: só a lista finita é percorrida.

Terminar a recursão

Identifica o caso base e uma medida que diminui: numa lista finita, o comprimento restante; num contador, a distância até zero. Se o tipo admite valores fora do domínio (negativos em replicar), trata-os ou declara a pré-condição.

Decisão	Condição
curta com três padrões	Termina em listas infinitas depois de três células.
perfeito n	Exige n > 0; a soma vazia de 0 passaria sem essa guarda.
Primalidade com d*d > n	O teste de paragem usa >, para não saltar a raiz exata.
toBits com Int -> [Int]	Domínio não negativo; escolhe [0] para zero e trata < 0.
(-1) div 2 == -1	Impede o progresso da mesma recursão para negativos.

• Em Pascal, a linha seguinte é zipWith (+) (0:linha) (linha ++ [0]): [1,3,3,1] produz [1,4,6,4,1].
• myindex segue índice e lista em conjunto. O domínio exclui negativos e índices além do fim; cada chamada recebe uma cauda estritamente menor.

Ordenar sem perder dados

Método	Ideia e custo para $n$ elementos finitos
Inserção	Insere a cabeça na cauda já ordenada. Pior caso $O(n^2)$.
Merge sort	Divide em metades menores, ordena e junta. $O(n \log n)$.

• Ao juntar, retira só a cabeça escolhida e conserva a outra para a chamada seguinte.
• Ao dividir, trata zero e um elemento antes da recursão, garantindo partes estritamente menores.
• Ambos os métodos conservam todas as ocorrências, incluindo repetidos.

Intercalar, permutar e converter

intercalar :: a -> [a] -> [a]
intercalar _ [] = []
intercalar _ [x] = [x]
intercalar s (x:xs) = x:s:intercalar s xs
-- intercalar '-' "rt" = "r-t"

Os casos de zero e um elemento impedem o separador final.

posicoes :: a -> [a] -> [[a]]
posicoes x [] = [[x]]
posicoes x (y:ys) = (x:y:ys) : map (y:) (posicoes x ys)

permutar :: [a] -> [[a]]
permutar [] = [[]]
permutar (x:xs) = concatMap (posicoes x) (permutar xs)

• permutar [] = [[]]: existe uma ordenação da lista vazia onde inserir. Há $n!$ resultados para $n$ ocorrências, mesmo com repetidos (permutar "aa" dá "aa" duas vezes); visitar cada resultado custa $O(n\,n!)$.
• Bits para inteiro: foldl (\n b -> 2*n+b) 0 sobre bits 0 ou 1 pela ordem. [1,0,1,1] passa por 0,1,2,5,11.
• Inteiro para bits: divide por dois até zero, recolhe os restos e inverte. 10 dá restos [0,1,0,1], logo bits [1,0,1,0].

Agrupar pela relação com o primeiro

agruparPor rel (x:xs) fixa x, usa span (rel x) xs para separar o prefixo e continua no resto. O caso vazio dá []. Não exige Eq: recebe a comparação.

Se a relação não for transitiva, comparar com o primeiro difere de comparar vizinhos. Com proximidade até 1 em [0,1,2], o contrato do primeiro dá [[0,1],[2]]; vizinhos dariam [[0,1,2]]. A recursão retira pelo menos a cabeça; para terminar, a entrada tem de ser finita.

Recursão, ordenação e contratos.