Aula 2

• posição do item na lista (0 se nao esta la, 1 se é o primeiro)

posicao it [] = 0
posicao it (x:xs) 
  | it == x = 1
  | otherwise = if (posicao it xs) == 0 then 0 else (posicao it xs) + 1  --- dupla recursao em alguns casos

• maior elemento de uma lista - FAZER p/ proxima aula - variáveis locais

maior [x] = x
maior (x:xs) = if x>(maior xs) then x else (maior xs)  -- dupla recursao

Esses dois codigos sao exponenciais (em alguns casos) no tamanho da lista quando obviamente eles podem ser lineares

Nos dois casos precisamos armazenar os valores posicao it xs e maior xs para usa-los em mais de um lugar

Where - define as variaveis (e funcoes) locais depois da chamada "principal"

maior [x] = x
maior (x:xs) = if x>mm then x else mm
    where mm = maior xs

let - define as variaveis e funcoes locais antes da chamada principal

maior [x] = x
maior (x:xs) = let
         mm = maior xs
      in if x>mm then x else mm 

where permite continuar usando guards

maior [x] = x
maior (x:xs) 
   | x>mm = x
   | otherwise = mm
   where mm = maior xs

As funcoes recursivas ate agora sao do tipo - recursao no tail e depois computa a solucao com o head

soma [] = 0
soma (x:xs) = x + (soma xs)

A ideia do acumulador é fazer o calculo usando o head e o acumulador recebido e passar o acumulador alterado para a recursao.

O acumulador acumula o trabalho das instancias que vieram antes nao recursao

--soma' l acc
soma [] acc = acc   -- caso base sempre retorna o acumulador
soma (x:xs) acc = soma xs (acc+x) -- caso recursivo faz primiro a conta (acc+x) e so no final chama a recursao

Mas a primeira chamada funçao soma' precisa setar o acumulador da forma certa. A funçao soma' é uma função local de soma

soma l = soma' l 0
  where soma' [] acc = acc
        soma' (x:xs) acc = soma' xs (x+acc)

Recursão com acumulador podem fazer a otimizacao de ultima chamada - torna o codigo recursivo tao rapido como um codigo iterativo.

reverte [] = []
reverte (x:xs) = (reverte xs) ++ [x]

append [] l = l
append (x:xs) l = x:(append xs l)

reverte l = reverte' l []
   where 
     reverte' [] acc = acc
     reverte' (x:xs) acc = reverte' xs (x:acc)

maior (x:xs) = maior' xs x
  where maior' [] a = a
        maior' (y:ys) a 
           | y>a = maior' ys y
           | otherwise = maior' ys a

maior [x] = x
maior (x;xs) = max' x (maior xs)
  where max' a b 
        | a > b = a
        | otherwise = b

"quase-lista" de elementos de tipos diferentes. Mas as funcoes de lista NAO funcionam para tuplas

("Jose",47, [4,5])

mas pattern matching funciona em tuplas

somaAno (n,id,l) = (n, id+1,l)

Retornar uma tupla é o jeito para uma função retornar mais de uma coisa

trocaultimo' velho novo []  = ([],False)
trocaultimo' velho novo (x:xs) = let
             (xxs,trocou) = trocaultimo' velho novo xs
          in if trocou || (x /= velho)  then (x:xxs, trocou)
                                        else (novo:xxs, True)
      

trocaultimo' _ _  []  = ([],False)  -- variaveis nao importantes

trocaultimo n v l = reverte (troca1 n v (reverte l))

[ x+10 | x <- [1..10], x `mod` 2 == 0]

somapares xs = soma [x | x <- xs, x `mod` 2 == 0]

refaça os exercicios da aula passada usando variaveis locias, recursao com acumulador, list comprehension, funcoes retornando tuplas, combinando funçoes ja implementadas, etc se for o caso. Em particular tente usar acumuladores para aprender apensar dessa forma.

Fazer os exercícios abaixo usando apenas head tail : ++

• posicoes - dado um item e uma lista, retorna uma lista com todas as posicoes (primeiro elemento esta na posicao 1) do item na lista
• split - dado um item e uma lista retorna uma lista de listas, todos os elementos da lista antes do item (a primeira vez que ele aparece) e todos depois

split "qwertyuiopoiuyt" 't' ==> ["qwer", "yuiopoiuyt"]

• splitall - mesma coisa que o split mas retorna todas as sublistas

splitall "qwertyuiopoiuytxxt" 't' ==> ["qwer", "yuiopoiuy", "xx", ""]  ou  ["qwer", "yuiopoiuy", "xx"]

• drop n lista - a lista sem os n primeiros elementos
• take n lista - os primeiros n elementos da lista