livro texto (cap 6)

haskell online

outro - so compilado

Para o compilado

main = do
       print $ sua funcao com argumentos

Mergesort

mergesort :: Ord a => [a] -> [a]

mergesort [] = []
mergesort [x] = [x]
mergesort xs =
  merge (mergesort x1) (mergesort x2)
  where
    n = (length xs) `div` 2
    x1 = take n xs
    x2 = drop n xs

merge [] b = b
merge a [] = a
merge (a:as) (b:bs)
  | a< b = a: (merge as (b:bs))
  | otherwise = b : (merge (a:as) bs)

Um algoritmo com aspectos do merge sort

Proposto por um aluno

merge a [] = a
merge [] b = b
merge (a:as) (b:bs) = if a <= b then a:(merge as (b:bs))
                                else b:(merge (a:as) bs)

merge_pairs [] = []
merge_pairs (a:[]) = [a]
merge_pairs (a:(b:bs)) = (merge a b):(merge_pairs bs)

merge_sort' [] = []
merge_sort' (a:[]) = a
merge_sort' a = merge_sort' (merge_pairs a)

mergesort a = merge_sort' $ (map (\b -> [b]) a) a

--- O merge sort implementado aqui separa a lista inicial em uma lista de
--- listas de um elemento, fazendo o merge em pares de elementos dessa lista
--- recursivamente e retornando uma lista nova, repetindo o processo até que
--- a lista possua apenas um elemento, que é a lista original ordenada.
--- fiz assim porque o método de dividir a lista ao meio tradicional do
--- merge sort não é tão bom para listas ligadas como é o caso do haskell.
--- Esse algoritmo ainda se enquadra como merge sort pois o mesmo funciona
--- dando merge em listas ordenadas para produzir uma lista ordenada maior.
--- Ele apenas substitui o processo de dividir a lista ao meio cada vez,
--- pois esse processo é custoso em haskell, em prol de um processo que
--- assume que cada elemento já está dividido em uma lista individual de
--- tamanho 1.

Exemplos

Conta quantas vezes um item aparece numa lista

conta item lista = sum $ map (\ x -> if x==item then 1 else 0) lista

conta item lista = sum [ if x==item then 1 else 0 | x<- lista]

conta item lista = foldl (\ acc x -> if x==item then acc+1 else acc) 0 lista

conta item lista = foldr (\ x res -> if (x==item then res+1 else res) 0 lista

conta item = foldr (\ x res -> if (x==item then res+1 else res) 0 -- point-free

veja que a função anonima faz acesso ao parametro item

isso significa que ele nao pode ser uma funçao externa (precisa ser local ou anonima)

membro e remove

membro item lista = foldl (\ acc x -> x==item || acc) False lista


remove it lista = foldr (\ x res -> if x==it then res else x:res) [] lista

ja existe a função elem

reverte

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

reverte lista = foldl (\ acc x -> x:acc) [] lista

reverte = foldl (\ acc x -> x:acc) []

reverte = foldl (flip (:)) []    -- !!!!!!!

soma cumulativa

-- recussao tradicional (foldr) com um parametro a mais (soma ate agora)

somacum (x:xs) = sc xs x
    where
        sc [] soma = [soma]
        sc (a:as) soma = (soma+a) : (sc as (soma+a))



-- com accumulador mas monta a lista ao contrario

somacumx (x:xs) = scx xs [x]
    where 
        scx [] acc = acc
        scx (x:xs) (a:as) = sc xs ((x+a):(a:as))


somacum (x:xs) = reverse $ foldl comb [x] xs
    where 
        comb all@(x:xs) a = x+a:all

todas as posicoes de um item numa lista

let lista1 = [2,3,1,4,5,4,3,4,6,1,1,0]


-- tradicional 

posicoes it [] = []
posicoes it (x:xs) 
    | x == it = 1:res
    | otherwise = res
    where 
        res = map (1+) $ posicoes it xs

-- foldl passando uma tupla (posicao autual e resultado) 

posicoesx it lista = foldl comb (1,[]) lista
    where 
        comb (n,l) x 
            | x == it = (n+1,n:l)
            | otherwise = (n+1,l)

posicoes it lista = reverse $ snd $ posicoesx it lista

        

transposta de uma matriz

let mat1 = [[1,2,3],[4,5,6],[7,8,9],[0,0,-1]]
let mat1tr = [[1,4,7,0],[2,5,8,0],[3,6,9,-1]]


-- caso recursivo tansp m = (map head m) : (transp (map tail m))
-- caso base? quando a matriz para ser transposta é da forma [[],[],[],...,[]]

transposta ([]:_) = []
transposta mat = (map head mat) : (transposta (map tail mat))

Outra versão do transposta poposto por um aluno

-- caso base trnasposta de uma linha da uma coluna
transposta [x] = map (\z -> [z]) x

-- caso recursivo: insere os elementos da linha (l) no comeco das
-- linhas da transposta
transposta (l:ls) = zipWith (:) l (transposta ls)

multiplicacao de duas matrizes

let m1 = [[1,2,3],[4,5,6]]
let m2 = [[7,8],[9,10],[11,12]]
let mresp = [[58,64],[139,154]] -- https://www.mathsisfun.com/algebra/matrix-multiplying.html
    
let m2transp = [[7,9,11],[8,10,12]]    
    
    
prodesc l1 l2 = sum $ zipWith (*) l1 l2

matmul' [] _ = []
matmul' (x:xs) m2t = (map (prodesc x) m2t) : (matmul' xs m2t)


matmul m1 m2 = matmul' m1 $ transposta m2