• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Nazgulled

Dividir uma lista de inteiros em duas, mehor forma?

8 mensagens neste tópico

Isto é um daqueles exercícios básicos que eu resolvi de uma forma, mas acho que é possível resolver de outra forma só que eu não estou a ver como...

A função recebe uma lista de inteiros e um número X e devolve um par de listas onde a lista da esquerda tem os números inferiores a X e a da direita todos os outros. É suposto usar recursividade e eu fiz assim:

parLista2 :: [int] -> Int -> ([int], [int])
parLista2 [] _ = ([], [])
parLista2 (x:[]) a | x >= a = ([], [x])
parLista2 (x:xs) a | x < a = ([x] ++ fst (parLista2 xs a), snd (parLista2 xs a)) -- snd a mais?
	   | otherwise = ([], [x] ++ snd (parLista2 xs a))

Mas para mim, aquele snd (comentado) está a mais, mas o código não funciona sem ele. Por um lado, eu vejo este código com montes de chamadas recursivas em que nunca mais acabava, só que o função da o resultado exacto que eu pretendo.

O que é que eu estou a complicar?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acho que estás a complicar demais algo que pode ser implementado com um padrão que consiste em fazer o teste entre o elemento da lista e o 'a' e, caso seja menor, fica do lado esquerdo, caso contrário fica do lado direito. Este "ficar de um lado ou outro", pode ser expresso através de um par (x:z,b) ou (z,x:b) conforme o resultado da comparação, sendo (z,b) o resultado da invocação recursiva sobre o resto da lista:

parte [] _ = ([],[])
parte (x:xs) a | x<a = (x:z,b)
       | otherwise = (z,x:b)
where (z,b) = parte xs a

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu acho a tua bem mais confusa. Tenta fazer as reduções à mão e vês como funciona.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

parLista2 :: [int] -> Int -> ([int], [int])
parLista2 [] _ = ([], [])
parLista2 (x:[]) a | x >= a = ([], [x])
parLista2 (x:xs) a | x < a = ([x] ++ fst (parLista2 xs a), snd (parLista2 xs a)) -- snd a mais?
	   | otherwise = ([], [x] ++ snd (parLista2 xs a))

Isto está a funcionar?

Não percebo para que queres a terceira linha, e na última, estás a deitar fora o primeiro elemento do resultado da recursividade.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Agora não tenho possibilidade de o fazer mas talvez tenhas razão, só experimentei com listas em ordem crescente :X

0

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