livro texto capítulo 3 (tipos)

haskell online

Por que aprender Haskell!!

qs [] = []
qs (x:xs) = qs menores ++ [x] ++ qs maiores
    where  menores = [y | y <- xs, y<=x]
           maiores = [y | y <- xs, y>x]

Tarefa 1

trocatodos _ _ [] = []
trocatodos velho novo (x:xs)
           | x == velho = novo:(trocatodos velho novo xs)
           | otherwise = x:(trocatodos velho novo xs)

Uma outra versão do trocatodos

trocatodos velho novo lista = [ if x==velho then novo else x | x <- lista]

Soma cumulativa - voce precisa passar um parametro a mais que é a soma dos números vistos ate agora. Isso nao é o acumulador, pois o trabalho da função é montar a lista das somas acumuladas e esse parametro a mais não esta montando esta lista.

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

com acumulador (um versão bem complexa)

cumsum (x:xs) = cumsum1 xs [x]
    where
        cumsum1 [] acc = acc
        cumsum1 (x:xs) acc = cumsum1 xs (acc ++ [x + last acc])
         
         

last lista – retorna o ultimo de uma lista

last [x] = x
last (x:xs) = last xs

Essa solução com acumulador esta bem complexa. Ha 2 problemas ou dicas de como melhorar

• nos vimos que coisas como isso acc ++ [x] (acrescentar ao final de uma lista) torna a função potencialmente quadráticas se a lista é implementada como uma lista ligada.
• nos precisamos pegar o ultimo elemento de uma lista (que tem um custo linear) a cada chamada e de novo torna a função quadratica.

Mas juntar no começo e pegar o primeiro elemento de uma lista são operações em tempo constante e sintaticamente claras : faz a o mesmo tempo pegar o primeiro ou juntar na frente.

Assim é mais interessante que o acumulador seja sempre manipulando no 1o elemento - o que torna a lista construida ao contrario. Assim no final, reverta a lista

cumsum (x:xs) = reverte (cumsum2 xs [x])
        where
            cumsum2 [] acc = acc
            cumsum2 (x:xs) (a:as) = cumsum2 xs ((x+a):(a:as))

reverte l -- reverte uma lista 

Finalmente veja que nós quebramos o acumulador no 1o e no resto (a:as) mas depois precisamos dos 2 pedaços juntos (x+a):(a:as) Existe uma notação @ para atribuir um nome ao conjunto e ainda usar o : para quebrar nas partes. Veja na seção pattern matching do livro texto

cumsum (x:xs) = reverte (cumsum2 xs [x])
        where
            cumsum2 [] acc = acc
            cumsum2 (x:xs) acc@(a:as) = cumsum2 xs ((x+a):acc)

Sobre parenteses em haskell

• aplicação de função tem a maior prioridade maior que qualquer operador

• link para a lista de prioridades de operadores

• sempre que tiver alguma função (antes) os operadores precisam estar entre parenteses

cumsum2 xs ((x+a):acc) -- OK

cumsum2 xs (x+a:acc)  -- OK tambem o + é feito antes do : (veja a lista de precedencia)
 
cumsum2 xs (x+a):acc  -- nao funciona o : é feito depois, o (x+a) é o argumento da funcao
  == (cumsum2 xs (x+a)) : acc

cumsum2 xs x+a:acc   -- nao funciona
   == ((cumsum2 xs x) + a) : acc -- + tem maior prioridade que : 

• sempre coloque parenteses para os argumentos da função!!!

Tipos

:t head
head :: [a] -> a

indica uma função que recebe uma lista de valores do tipo a e retorna um valor do tipo a

a é uma variável de tipo (type variable)

removeAll c lista = [y | y <- lista, y /= c]

:t removeAll
removeAll :: Eq t => t -> [t] -> [t]

a parte “t -> [t] -> [t]” indica que é uma função de 2 argumentos, um dado e uma lista de dados, que retorna uma lista de dados (porque os 2 argumentos são separados por uma flecha fica para outra aula - currying)

“Eq t ==>” indica que o tipo t tem restrições, e tem que pertencer ao typeclass Eq que sao tipos para os quais a comparação de igualdade esta definida (quase todos mas não funções!!)

• Eq tem igualdade (==)

• Ord tem ordem (>)

• Num tem as operações aritméticas (+, -, * e abs) definidas . Num é parte do Eq mas não do Ord (números complexos não tem ordem!!) Divisão nao esta incluida nos Num

• Show pode ser impresso ( convertido para string) - função show

• Read pode ser lido (de um string) - função read

Quando voce definir seus tipos, voce poderá definir o que == (Eq) significa para o seu tipo, da mesma forma o show, read, < etc

tipos básicos

• Int inteiros de maquina

• Integer inteiros sem limite de tamanho (como no Python)

• Float do C

• Double do C

• Bool booleano

• Char caracter

outros tipos genéricos

• Integral genérico de inteiros e operação de divisão inteira e resto

• Fractional genérico para floats e operação de divisão real

• Floating generico para floats e operações exponenciais, trigonométricas, etc

Definindo o tipo na declaração da variável

ordenada :: Ord a => [a] -> Bool
ordenada [] = True
ordenada [x] = True
ordenada (a:b:xs)
   | a <= b = ordenada (b:xs)
   | otherwise = False

-- ou 

ordenada [b] = True
ordenada (a:b:xs) = a<=b && ordenada (b:xs)

remove1 :: Eq a => a -> [a] -> [a]
remove1 _ _ [] = []
remove1 it (x:xs) 
  | x == it = xs
  | otherwise =  x : (troca1 it xs)

remove1 8  [2,4,5,8,7,6,8,7]

Booleanos

• True

• False

• || or

• && and

membro x [] = False
membro x (a:as) 
    | x == a = True
    | otherwise = membro x as

-- ou

membro x [] = False
membro x (a:as) = x==a || membro x as

4 `membro` [ 3,2,4,5,6,4,3,2,1]