Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #59 da revista programar. Faz já o download aqui!

leia

função maximo

Mensagens Recomendadas

leia    1
leia

Boa noite ,

Precizava de uma ajuda em entender o conceito seguinte:

FOLDR SOBRE LISTAS NÃO VAZIAS

Suponho que quero determinar o máximo dentre os elementos de uma lista (não vazia) usando a função maximo

maxlist :: Ord a => [a] -> a
maxlist = foldr (max) v

tentei substituir o "v" mas nunca acertei para poder obter um resultado. :confused: :confused: :confused: :confused:

Agradeço qualquer ajuda!!!!

Editado por leia

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
thoga31    594
thoga31

Duas coisas:

1) O que é suposto esse v ser?

2) A função foldr tem o seguinte protótipo:

foldr :: (a -> b -> b) -> b -> [a] -> b

Onde está o segundo argumento do tipo b? Não deves colocar 0 nem nenhum valor, imagina que os números são todos negativos: irias obter 0.

Para isto, deves usar a função foldr1 que começa utilizando desde logo o primeiro valor da lista.

Editado por thoga31

Knowledge is free!

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    312
Rui Carlos

É suposto fazer isso em point-free?

Mesmo que seja, acho que é melhor começares pela versão point-wise. Aliás, até te sugeria começares por uma versão com recursividade explícita, que depois podias passar para o foldr.

(thoga31, o segundo argumento é o v, agora de onde ele veio também não sei.)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
leia    1
leia

eu segui a sua dica e fiz isso

maximo2 :: Ord a => [a] -> a
maximo2 = foldr1 (max)

e obtive o resultado que eu quero.

Mas eu queria obter o maximo de uma lista usando apenas foldr e não consigo !! :confused::(

(Rui Carlos) aquela função que esta mesmo em cima com o segundo argumento (v) e exactamente como vinha em uns pdf´s que estou a ler sobre haskell. :confused:

Penso que deve haver uma resolução baseada nisso so que eu dei voltas e voltas e nao consegui por a funcionar...!!!

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
thoga31    594
thoga31

Aquele v não pode ter vindo assim do nada. Aquele v seria o valor inicial a partir do qual o foldr iria processar.

Porque pretendes usar só o foldr? Nesse caso tens de dar um valor inicial, sendo ele um valor da lista a analisar. Não te consegues recordar de uma forma de o fazer? Para tal não podes usar point free notaton.


Knowledge is free!

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    312
Rui Carlos

Resolve o problema com recursividade explícita (e coloca aqui a solução).

Depois de o fazeres, vais ver que a função foldr não é apropriada para o padrão de recursividade que vais utilizar. Aliás, repara que a função foldr dará um resultado para a lista vazia, o que não é suposto acontecer neste caso.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
leia    1
leia

maximo3 [x] = x
maximo3 (x:xs) | x > maximo3 xs = x
              | otherwise = maximo3 xs

Fiz aqui uma recursiva como me pediu . :)

Queria ver um exemplo e perceber como se faz isso com foldr sim porque acho um pouco dificil e ando a moer em cima disso sem conseguir avansar :( :( :confused:

Editado por leia

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    312
Rui Carlos

Uma outra alternativa seria

maximo [x] = x
maximo (x:xs) = max x (maximo xs)

Ora, o foldr é adequado para o padrão

<funcao recursiva> []     = <constante>
<funcao recursiva> (x:xs) = <funcao> x (<funcao recursiva> xs)

Quando tens uma função deste género, podes escrever <funcao recursiva> = foldr <funcao> <constante>

Mas repara que o caso de paragem da função maximo não encaixa neste padrão. Mas já se enquadra no padrão da função foldr1, que é qualquer coisa como:

<funcao recursiva> [x]     = x
<funcao recursiva> (x:xs) = <funcao> x (<funcao recursiva> xs)

Para terminar, podias definir a função com o foldr, por exemplo, da seguinte maneira:

maximo l = foldr max (head l) l

Agora para tornar isto point-free, só com as funções base do Haskell não me parece fácil. A única estratégia que estou a ver passa por usar a função split, que, tanto quanto sei, não existe no Haskell (e mesmo que exista, já é inventar um bocado...).

split f g x = (f x, g x)

maximo :: Ord a => [a] -> a
maximo = (uncurry (foldr max)) . (split head id)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Kimio    10
Kimio

Agora para tornar isto point-free, só com as funções base do Haskell não me parece fácil. A única estratégia que estou a ver passa por usar a função split, que, tanto quanto sei, não existe no Haskell (e mesmo que exista, já é inventar um bocado...).

split f g x = (f x, g x)

maximo :: Ord a => [a] -> a
maximo = (uncurry (foldr max)) . (split head id)

Outra alternativa point-free usando apenas funções de base Haskell (pelo menos no base-4.6.0.1):

maximo :: Ord a => [a] -> a
maximo = head >>= foldr max

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.