Listas:
Haskell
x
Prolog
Claudio Cesar de Sá
[email protected]
Haskell
Prolog
A formatação desses slides, créditos a João Paulo Cattani (2002/2)
• O material original, e a sua origem na WEB foi
perdida
• O código em Haskell foi alterado, testado e
corrigido
• O de Prolog...
• Ninguém precisa digitar, é só enviar um email que
mando todo código em Haskell
• A maioria das funções aqui apresentadas, tem
embutidas no módulo Prelude.hs, na seção das listas,
mas com outro nome. Os nomes das funções não
podem coincidir com os já existentes em um módulo
já carregado.
• [5,2,3,8,1,4]
1 2 3 4 5 6
a lista
a posição relativa
• Isto é: [inicio, próximo elemento, .., fim]
[1..10]
= [1,2,3,4,5,6,7,8,9,10]
[1,3..10]
= [1,3,5,7,9]
[1,3..]
= [1,3,5,7,9,… (seqüência infinita)
• O uso de letras minúsculas como variáveis, oposto ao Prolog
• Tipagem, existente. Contudo, polimórfica
• .....
1. cabeca([X|_],X).
1. cabeca :: [a] -> a
2. cabeca (x:_) = x
No Preludio
tem “head”
1. cauda([_|Xs],Xs).
1. cauda :: [a] -> [a]
2. cauda (_:xs) = xs
No Preludio
tem “tail”
{- se a lista é nula ? -}
1. nula :: [a] -> Bool
2. nula [ ] = True
3. nula (_:_) = False
1. null([ ]).
No Preludio
tem “null”
1. ultimo :: [a] -> a
2. ultimo [x]
= x
1. ultimo ([X],X).
2. ultimo ([_|Xs], Y) :- ultimo(Xs,Y).
3. ultimo (_:xs) = ultimo xs
{- exclui o último da lista -}
1. inicio :: [a] -> [a]
1. inicio( [ _ ], [ ] ).
2. inicio [ _ ]
2. inicio( [X | Xs] , [ X | Ys ] ) :- inicio( Xs , Ys ).
= []
3. inicio (x:xs) = x : inicio xs
inicio [ 1 ,2, 3, 5, 6 ]
[1,2,3,5]
1. comp_lista :: [a] -> Int
1. comp_lista ([ ],0).
2. comp_lista [ ]
2. comp_lista ([_|L],N):-comp_lista(L,N0), N is 1+N0.
=0
3. comp_lista (_:l)=1 + comp_lista l
1. sumList :: ( Num a ) => [ a ] -> a
1. sumList([ ],0).
2. sumList [ ]
2. sumList([X|Xs],N):-sumList(Xs,N0),
N is X+N0.
=0
3. sumList (x:xs) = x + sumList xs
{- qual é o n-ésimo termo? -}
1. nth :: Int -> [ a ] -> a
2. nth 0 ( x : _ ) = x
3. nth n ( _ : xs )
4.
| n > 0 = nth (n-1) xs
nth 40
45
[5 .. 100]
1. nth(0,[X|_],X).
2. nth(N,[_|Xs],Y) :- N>0,
N1 is (N-1),nth(N1,Xs,Y).
1. pegue_n_elem :: Int -> [a] -> [a]
2. pegue_n_elem 0 _ = [ ]
3. pegue_n_elem _ [ ] = [ ]
4. pegue_n_elem n ( x : xs)
5.
| n > 0 = x : pegue_n_elem (n - 1) xs
pegue_n_elem
4
1. pegue_n_elem(0, _ ,[ ] ).
2. pegue_n_elem(_,[ ],[ ]).
3. pegue_n_elem(N,[X|Xs],[X|Ys]):-N>0,
N1 is N-1, pegue_n_elem(N1,Xs,Ys).
[10 .. 20]
[10,11,12,13]
{- do n-ésimo até o final da lista, nova lista -}
1. do_n_elem_fim :: Int -> [ a ] -> [ a ]
2. do_n_elem_fim 0 x_full = x_full
3. do_n_elem_fim _ [ ] = [ ]
4. do_n_elem_fim n ( _ : xs )
5.
| n > 0 = do_n_elem_fim ( n-1 ) xs
do_n_elem_fim
3
[5 .. 17]
[8,9,10,11,12,13,14,15,16,17]
1. do_n_elem_fim (0,Xs,Xs).
2. do_n_elem_fim (_,[ ],[ ]).
3. do_n_elem_fim (N,[_|Xs],Ys):-N>0,
N1 is (N-1),
do_n_elem_fim (N1,Xs,Ys).
1. diviAt :: Int -> [a] -> ([a],[a])
2. diviAt 0 xs = ( [ ] , xs )
3. diviAt _ [ ] = ( [ ] , [ ] )
4. diviAt n (x : xs )
5. | n > 0 = (x: xs1 , xs2 )
6.
where ( xs1 , xs2 ) = diviAt (n - 1) xs
1. diviAt( 0,Xs,[ ],Xs).
2. diviAt( _ , [ ],[ ],[ ]).
3. diviAt( N , [X|Xs] , [X|Xs1] , Xs2) :-
diviAt 3
[10 .. 20]
([10,11,12],[13,14,15,16,17,18,19,20])
{- separa numa sub-lista os 3 primeiros objetos... -}
N>0,N1 is N-1, diviAt(N1,Xs,Xs1,Xs2).
1. pertence( X , [X|_] ).
2. pertence( X , [_|Ys] ) :- member( X,Ys )
1. pertence :: (Eq a) => a->[a]->Bool
2. pertence x [ ]
= False
3. pertence x (y : ys) = x == y || pertence x ys
pertence 9
[5,6,7]
False
1. append :: [a] -> [a] -> [a]
1. append([ ],Ys,Ys).
2. append [ ] ys
2. append([X|Xs],Ys,[X|Zs]):-append(Xs,Ys,Zs).
= ys
3. append (x : xs) ys = x : append xs ys
append
[1,2,3,4]
[1,2] [3,4]
1. inverte_1 :: [a] -> [a]
1. inverte_1 ([ ],[ ]).
2. inverte_1 [ ]
2. inverte_1 ([X|Xs],Ys):- inverte_1 (Xs,Ys1)
append(Ys1,[X],Ys).
= []
3. inverte_1 (x:xs) = append (inverte_1 xs)
[x]
inverte_1
[6,5,4]
[4,5,6]
1. inverte_2 :: [a] -> [a]
1. inverte_2 (Xs,Ys):- rev(Xs,[ ],Ys).
2. inverte_2 xs = rev xs [ ]
inverte_2
[4,5,6]
[6,5,4]
{- auxiliar.... -}
1. rev :: [a] -> [a] -> [a]
1. rev([ ],Ys,Ys).
2. rev [ ] ys
2. rev([X|Xs],Y0s,Ys):- rev(Xs,[X|Y0s],Ys).
= ys
3. rev (x:xs) y0s = rev xs (x:y0s)
1. maior_lista :: (Ord a, Num a) => [a] -> a
1. maior_lista (Xs,N) :- maxL (Xs,0,N).
2. maior_lista (h:xs) = maxL (h:xs) 0
maior_lista [5, 7, 6]
7
{- auxiliar... -}
1. maxL :: (Ord a) => [a]-> a -> a
1. maxL([ ],N,N).
2. maxL [ ] maior
2. maxL([X|Xs],N0,N) :-
= maior
3. maxL (x:xs) maior
4.
| x > maior
= maxL xs x -- troca
5.
| otherwise = maxL xs maior -- não
( X>N0 ->
maxL(Xs,X,N);
otherwise -> maxL(Xs,N0,N)
).
1. xmapear :: (a -> b) -> [a] -> [b]
2. xmapear f [ ] = [ ]
3. xmapear f (x:xs) = f x : xmapear f xs
{- ... Abstração lambda calculus....
xmapear (\x -> (x+7) ) [10 .. 20]
[17,18,19,20,21,22,23,24,25,26,27]
-}

Aguardando algumas novas funções
1. filtrar
:: (a -> Bool) -> [a] -> [a]
2. filtrar p [ ]
=[]
3. filtrar p (x : xs) = if p x then x : filtrar p xs
4.
else filtrar p xs
{- ... Abstração lambda calculus....
filtrar (3<) [1,3,6,5,6]
[6,5,6]
equivalente há:
filtrar (\x -> (x>3) ) [1,3,6,5,6]
[6,5,6]
-}
Aguardando algumas novas funções