Jump to content
leia

função maximo

Recommended Posts

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!!!!

Edited by leia

Share this post


Link to post
Share on other sites
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.

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
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.)

Share this post


Link to post
Share on other sites
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...!!!

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

  • Vote 1

Share this post


Link to post
Share on other sites
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:

Edited by leia

Share this post


Link to post
Share on other sites
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)

  • Vote 2

Share this post


Link to post
Share on other sites
leia

Muito obrigada mais uma vez pela ajuda e dicas que me derom.

Já percebi melhor umas coisinhas. :)

Share this post


Link to post
Share on other sites
pdfrod

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.