10 - Funções de Alta Ordem

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Funções	
  de	
  Alta	
  Ordem	
  
Renata	
  Carvalho	
  
UNICAP	
  –	
  UNIVERSIDADE	
  CATÓLICA	
  DE	
  PERNAMBUCO	
   Renata	
  Carvalho	
  
Função	
  de	
  Alta	
  Ordem	
  
applyBinOper	
  ::	
  (t	
  -­‐>	
  t	
  -­‐>	
  t)	
  -­‐>	
  t	
  -­‐>	
  t	
  -­‐>	
  t	
  
applyBinOper	
  f	
  x	
  y	
  =	
  f	
  x	
  y	
  
	
  
Exemplos:	
  
applyBinOper	
  (+)	
  10	
  20 	
   	
   	
  -­‐-­‐	
  30	
  
applyBinOper	
  (*)	
  10	
  20 	
   	
   	
  -­‐-­‐	
  200	
  
applyBinOper	
  (||)	
  True	
  False 	
   	
  -­‐-­‐	
  True	
  
applyBinOper	
  (++)	
  “abc”	
  “def” 	
   	
  -­‐-­‐	
  “abcdef”	
  
Função	
  de	
  
Alta	
  Ordem	
  
Mapeamento	
  
Por	
  que	
  
funções	
  de	
  
alta	
  ordem?	
  
Exemplos	
  
Folding	
  
Exercícios	
  
UNICAP	
  –	
  UNIVERSIDADE	
  CATÓLICA	
  DE	
  PERNAMBUCO	
   Renata	
  Carvalho	
  
Função	
  de	
  Alta	
  Ordem	
  
•  Exemplos	
  de	
  funções	
  de	
  mapeamento	
  
(mapping)	
  
	
  
double	
  ::	
  [Int]	
  -­‐>	
  [Int]	
  
double	
  []	
  =	
  []	
  
double	
  (a:as)	
  =	
  (2*a)	
  :	
  double	
  as	
  
	
  
sqrList	
  ::	
  [Int]	
  -­‐>	
  [Int]	
  
sqrList	
  []	
  =	
  []	
  
sqrList	
  (a:as)	
  =	
  (a*a)	
  :	
  sqrList	
  as	
  
Função	
  de	
  
Alta	
  Ordem	
  
Mapeamento	
  
Por	
  que	
  
funções	
  de	
  
alta	
  ordem?	
  
Exemplos	
  
Folding	
  
Exercícios	
  
UNICAP	
  –	
  UNIVERSIDADE	
  CATÓLICA	
  DE	
  PERNAMBUCO	
   Renata	
  Carvalho	
  
Função	
  de	
  Alta	
  Ordem	
  
•  Exemplos	
  de	
  funções	
  de	
  transformação	
  dos	
  
elementos	
  
ames2	
  ::	
  Int	
  -­‐>	
  Int	
  
ames2	
  n	
  =	
  2	
  *	
  n	
  
	
  
sqr	
  ::	
  Int	
  -­‐>	
  Int	
  
sqr	
  n	
  =	
  n	
  *	
  n	
  
Função	
  de	
  
Alta	
  Ordem	
  
Mapeamento	
  
Por	
  que	
  
funções	
  de	
  
alta	
  ordem?	
  
Exemplos	
  
Folding	
  
Exercícios	
  
UNICAP	
  –	
  UNIVERSIDADE	
  CATÓLICA	
  DE	
  PERNAMBUCO	
   Renata	
  Carvalho	
  
Mapeamento	
  (map)	
  
map	
  ::	
  (t	
  -­‐>	
  u)	
  -­‐>	
  [t]	
  -­‐>	
  [u]	
  
map	
  f	
  []	
  =	
  []	
  
map	
  f	
  (a:as)	
  =	
  f	
  a	
  :	
  map	
  f	
  as	
  
	
  
doubleList	
  xs	
  =	
  map	
  ames2	
  xs	
  
sqrList	
  xs	
  =	
  map	
  sqr	
  xs	
  
	
  
seconds	
  ::	
  [(t,	
  u)]	
  -­‐>	
  [u]	
  
seconds	
  xs	
  =	
  map	
  snd	
  xs	
  
Função	
  de	
  
Alta	
  Ordem	
  
Mapeamento	
  
Por	
  que	
  
funções	
  de	
  
alta	
  ordem?	
  
Exemplos	
  
Folding	
  
Exercícios	
  
UNICAP	
  –	
  UNIVERSIDADE	
  CATÓLICA	
  DE	
  PERNAMBUCO	
   Renata	
  Carvalho	
  
Mapeamento	
  (map)	
  
•  Outra	
  definição	
  para	
  map	
  
map	
  f	
  l	
  =	
  [f	
  a	
  |	
  a	
  <-­‐	
  l]	
  
Função	
  de	
  
Alta	
  Ordem	
  
Mapeamento	
  
Por	
  que	
  
funções	
  de	
  
alta	
  ordem?	
  
Exemplos	
  
Folding	
  
Exercícios	
  
UNICAP	
  –	
  UNIVERSIDADE	
  CATÓLICA	
  DE	
  PERNAMBUCO	
   Renata	
  Carvalho	
  
Por	
  que	
  funções	
  de	
  alta	
  ordem?	
  
•  Facilitam	
  entendimento	
  das	
  funções	
  
•  Facilitam	
  modificações	
  (mudança	
  na	
  função	
  de	
  
transformação)	
  
•  Aumentam	
  reuso	
  de	
  definições/código	
  
•  Exemplo:	
  usar	
  a	
  função	
  map	
  para	
  remarcar	
  o	
  valor	
  
de	
  uma	
  lista	
  de	
  preços	
  
Função	
  de	
  
Alta	
  Ordem	
  
Mapeamento	
  
Por	
  que	
  
funções	
  de	
  
alta	
  ordem?	
  
Exemplos	
  
Folding	
  
Exercícios	
  
UNICAP	
  –	
  UNIVERSIDADE	
  CATÓLICA	
  DE	
  PERNAMBUCO	
   Renata	
  Carvalho	
  
Exemplos	
  
•  Análise	
  de	
  vendas	
  
	
  
total	
  ::	
  (Int	
  -­‐>	
  Int)	
  -­‐>	
  Int	
  -­‐>	
  Int	
  
total	
  f	
  0	
  =	
  f	
  0	
  
total	
  f	
  n	
  =	
  (+)	
  (total	
  f	
  (n-­‐1))	
  (f	
  n)	
  
	
  
totalVendas	
  n	
  =	
  total	
  vendas	
  n	
  
	
  
sumSquares	
  ::	
  Int	
  -­‐>	
  Int	
  
sumSquares	
  n	
  =	
  total	
  sq	
  n	
  
Função	
  de	
  
Alta	
  Ordem	
  
Mapeamento	
  
Por	
  que	
  
funções	
  de	
  
alta	
  ordem?	
  
Exemplos	
  
Folding	
  
Exercícios	
  
UNICAP	
  –	
  UNIVERSIDADE	
  CATÓLICA	
  DE	
  PERNAMBUCO	
   Renata	
  Carvalho	
  
Exemplos	
  
maxFun	
  ::	
  (Int	
  -­‐>	
  Int)	
  -­‐>	
  Int	
  -­‐>	
  Int	
  
maxFun	
  f	
  0	
  =	
  f	
  0	
  
maxFun	
  f	
  n	
  =	
  max	
  (maxFun	
  f	
  (n-­‐1))	
  (f	
  n)	
  
	
  
zeroInRange	
  ::	
  (Int	
  -­‐>	
  Int)	
  -­‐>	
  Int	
  -­‐>	
  Bool	
  
zeroInRange	
  f	
  0	
  =	
  (f	
  0	
  ==	
  0)	
  
zeroInRange	
  f	
  n	
  =	
  (||)	
  (zeroInRange	
  f	
  (n-­‐1))	
  (f	
  n	
  ==	
  0)	
  
Função	
  de	
  
Alta	
  Ordem	
  
Mapeamento	
  
Por	
  que	
  
funções	
  de	
  
alta	
  ordem?	
  
Exemplos	
  
Folding	
  
Exercícios	
  
UNICAP	
  –	
  UNIVERSIDADE	
  CATÓLICA	
  DE	
  PERNAMBUCO	
   Renata	
  Carvalho	
  
Folding	
  
sumList	
  ::	
  [Int]	
  -­‐>	
  Int	
  
sumList	
  []	
  =	
  0	
  
sumList	
  (a:as)	
  =	
  a	
  +	
  sumList	
  as	
  
	
  
fold	
  ::	
  (t	
  -­‐>	
  t	
  -­‐>	
  t)	
  -­‐>	
  [t]	
  -­‐>	
  t	
  
fold	
  f	
  [a]	
  =	
  a	
  
fold	
  f	
  (a:as)	
  =	
  f	
  a	
  (fold	
  f	
  as)	
  
	
  
sumList	
  l	
  =	
  fold	
  (+)	
  l	
  
Função	
  de	
  
Alta	
  Ordem	
  
Mapeamento	
  
Por	
  que	
  
funções	
  de	
  
alta	
  ordem?	
  
Exemplos	
  
Folding	
  
Exercícios	
  
UNICAP	
  –	
  UNIVERSIDADE	
  CATÓLICA	
  DE	
  PERNAMBUCO	
   Renata	
  Carvalho	
  
Folding	
  
•  Exemplos	
  
	
  
and	
  ::	
  [Bool]	
  -­‐>	
  Bool	
  
and	
  xs	
  =	
  fold	
  (&&)	
  xs	
  
	
  
concat	
  ::	
  [[t]]	
  -­‐>	
  [t]	
  
concat	
  xs	
  =	
  fold	
  (++)	
  xs	
  
	
  
maximum	
  ::	
  [Int]	
  -­‐>	
  Int	
  
maximum	
  xs	
  =	
  fold	
  max	
  xs	
  
Função	
  de	
  
Alta	
  Ordem	
  
Mapeamento	
  
Por	
  que	
  
funções	
  de	
  
alta	
  ordem?	
  
Exemplos	
  
Folding	
  
Exercícios	
  
UNICAP	
  –	
  UNIVERSIDADE	
  CATÓLICA	
  DE	
  PERNAMBUCO	
   Renata	
  Carvalho	
  
Exercícios	
  
•  Defina	
  uma	
  função	
  de	
  alta	
  ordem	
  para	
  filtrar	
  
valores	
  de	
  uma	
  lista	
  
•  Defina	
  as	
  seguintes	
  funções	
  sobre	
  listas	
  
(usando	
  as	
  funções	
  de	
  alta	
  ordem	
  definidas)	
  
•  Eleva	
  os	
  itens	
  de	
  uma	
  lista	
  ao	
  quadrado	
  
•  map	
  
•  Retorna	
  a	
  soma	
  dos	
  quadrados	
  dos	
  itens	
  
•  fold	
  
•  Manter	
  na	
  lista	
  todos	
  os	
  itens	
  maiores	
  que	
  zero	
  
•  filter	
  
Função	
  de	
  
Alta	
  Ordem	
  
Mapeamento	
  
Por	
  que	
  
funções	
  de	
  
alta	
  ordem?	
  
Exemplos	
  
Folding	
  
Exercícios