Linguagem Funcional - Scheme

Vou mudar isto para “Outras Linguagens”. De qualquer maneira, isso tem de ser resolvido recursivamente; se você tem paciência, leia o livro “How to Design Programs”, que ensina Scheme - talvez haja até uma solução pronta para seu problema.

Tá, valeu pela dica do livro eu olhei lá, mas não tinha o que eu precisava mas eu achei um exercício feito
que talvez possa me ajudar só que eu queria entender o que foi feito nele por isso vou postar o exercício
e nas linhas eu coloco um comentário dizendo o que eu acho que faz e dai se eu tiver errado por favor me corrija.

O exercício é uma função apenas_positivos que recebe uma lista de valores e retorna a mesma lista, porém com os valores negativos ou zero removidos.

(define (apenas_positivos lista)
  (cond
    [(empty? lista) empty]   ;Verifica se a lista está vazia
                  
    [(> (first lista) 0) (cons (first lista) (apenas_positivos (rest lista)))] 
    ;Se o primeiro da lista é > 0 dai eu não entendi o que ele faz

    [else (apenas_positivos (rest lista))])) ;senão retorna o restante da lista 
(apenas_positivos (list -6 1 2 0 3 -7 4 -8 5))

Puxa vida, leia o livro então, já que você não entendeu uma das funções básicas - cons.

Ela serve para concatenar um elemento a uma lista, retornando uma lista. Por exemplo:

(cons '10 (list 1 2 3)) --> (list 10 1 2 3)

Ahhh tá, entendi agora…valeu
Só que eu revirei aquele livro e não vi nada que diga como fazer pra achar e remover elementos duplicados numa lista e é aí que eu to empacado =/

Não é para achar elementos duplicados numa lista.
Se você quer simplesmente resolver o problema, sem se preocupar com desempenho (você sabe, complexidade de algoritmos), faça o seguinte:

1. Defina uma função que diga se um elemento está presente em uma lista.
2. Defina uma função que adicione um elemento a uma lista se o elemento não for encontrado na lista. (Obviamente deve chamar a função 1) )
3. Para efetuar a união, chame a função 2) para cada elemento da primeira lista, e a seguir chame a função 2 para cada elemento da segunda lista.

Como você disse, a lista não precisa estar ordenada, então você pode usar o algoritmo acima.

Bom Dia !

Não entendi o que vc quis dizer com

" Não é para achar elementos duplicados numa lista. "

O problema que eu tenho que resolver é fazer uma função que recebe uma lista de inteiros L e retorna uma lista em que todos os elementos duplicados foram removidos.

A parte da União eu acho que sei fazer…só essa parte de remover os elementos duplicados q tá complicando
mas vou continuar tentando aqui.

Valeuu

Se não me negano esse é um dos exercicios no Little Schemer, que alias eh um livro otimo para aprender Scheme.

Ok, vou dar uma olhada… valeuu

Vc sabe me dizer pq na hora de rodar o programa aparece

(lambda (a1) …) ??

Cara, tive um semestre inteiro de Scheme no primeiro semestre da faculdade, tenho esses exercícios prontos, mas infelizmente sou contra te passar. Pensa um pouco que tu consegue, se não conseguir fala com teu professor.

Te passar os exercícios prontos vai é fazer tu rodar na cadeira.

Pois é, vc teve um semestre inteiro, eu tive 1 aula só…
é uma disciplina de Paradigmas de Programação dai é apresentada várias linguagens
dai tive q fazer projeto em Java, C, C++, Python… e agora em Scheme mas como só tive uma aula
e eu nunca tinha visto SCHEME na vida…ficou dificil entender…mandei vários emails para o professor mas ele n me retornou nenhum…alegando que tava sem tempo…dai procurei na net e não achei quase nada…e tudo que eu achava não era o que eu precisava, por isso deixei esse tópico aqui…

fajohann:

Pois é, vc teve um semestre inteiro, eu tive 1 aula só…
é uma disciplina de Paradigmas de Programação dai é apresentada várias linguagens
dai tive q fazer projeto em Java, C, C++, Python… e agora em Scheme mas como só tive uma aula
e eu nunca tinha visto SCHEME na vida…ficou dificil entender…mandei vários emails para o professor mas ele n me retornou nenhum…alegando que tava sem tempo…dai procurei na net e não achei quase nada…e tudo que eu achava não era o que eu precisava, por isso deixei esse tópico aqui…

po, que coisa…
vou te dar uma referencia boa entao…
nesse site abaixo tem toda documentacao do PLT Scheme (nao apenas nesses links)

http://docs.plt-scheme.org/guide/index.html
http://docs.plt-scheme.org/guide/Pairs__Lists__and_Scheme_Syntax.html

e os slides da aula que tive sobre listas em scheme.

De nada!

:?

Cara, valeu pelo material, não tive tempo de ver ainda mas o quanto antes vou dar uma olhada.
Desculpa não ter respondido antes mas realmente não tive mto tempo…

Valeu mesmo…
Abraço

fajohann:

Cara, valeu pelo material, não tive tempo de ver ainda mas o quanto antes vou dar uma olhada.
Desculpa não ter respondido antes mas realmente não tive mto tempo…

Valeu mesmo…
Abraço

Beleza, avisa se der certo, qualquer coisa tô por aí…

Cara, to empacado na parte de fazer a função que recebe uma lista e remove os elementos duplicados..
Lendo o seu material eu entendi que seria +/- assim..

(define (distintos lista)
    (cond 
      [(empty? lista)false]
      [(=(first lista) rest lista)
            (cons (first lista) (distintos (rest lista)))]
      [else(distintos(rest lista))]))


distintos(list 1 1 2 3 5 3 2)

mas isso não tá dando certo..se vc pudesse me dar uma ajuda no que eu to fazendo de errado..agradeço.

Valeuu

Que tipo de erro está dando?
Erro na interpretação do código ou erro lógico?
O que é para fazer o procedimento “distintos”?

fajohann,

faça uma procedure auxiliar para verificar se um determinado elemento existe na lista, se não existir, insira o elemento usando cons.

dlt:

fajohann,

faça uma procedure auxiliar para verificar se um determinado elemento existe na lista, se não existir, insira o elemento usando cons.

Desculpa, mas o que é uma procedure auxiliar ? :?

Quando eu rodo o programa aparece isso:

(lambda (a1) …)
(list 1 1 2 3 5 3 2)

A função DISTINTOS deve receber uma lista e remover todos elementos duplicados dela…
retornando uma lista sem as duplicações.

http://pt.wikipedia.org/wiki/Subrotina

É o procedimento que você acabou de escrever, traduzido com o scheme entende realmente.

É o resultado do procedimento distintos.

A função DISTINTOS deve receber uma lista e remover todos elementos duplicados dela…
retornando uma lista sem as duplicações.

Pelo que eu entendi então esse tal procedimento verifica se um elemento x pertence a lista L
passando isso pra Scheme ficaria assim então:

(define (contem? x lista) (cond [(empty? lista) false] [else (cond [(= (first lista) x) x] [else (contem? x (rest lista))])])) (contem? 1 (list 2 1))

Agora esse procedimento ‘contem?’ eu tenho que implementar dentro do outro procedimento ‘distintos’ ?

Fora do “distintos”.
Colocando o algoritmo do procedimento fora de qualquer procedimento fica mais fácil e legível…

opa…desculpa, o que eu quis dizer foi que eu teria que chamar ele dentro do distintos…não implementar ele lá…

Na hora de chamar o ‘contem?’ dentro do distintos tá dando o seguinte erro:

“cond: expected a clause with a question and answer, but found a clause with only one part”

(define (distintos lista) (cond [(empty? lista) false] [else (cond [(contem? (first lista) (rest lista))] [else (distintos(rest lista))])])) distintos(list 1 1 2 3 4 5)

quando o procedimento ‘contem?’ for chamado ele deve receber um elemento e uma lista
se eu quero que esse elemento seja o primeiro da lista L e a lista seja o restante da lista L
não é desse jeito que eu fiz ali em cima que se faz ?

Eu tava vendo aqui e vi um erro, o procedimento “contem?” devolve o elemento x encontrado, invés de devolver true:

[(= (first lista) x) x]

E o que se espera na verdade é um booleano para informar se contém ou não.

Obs.: É muito importante fazer o template para cada procedimento para não se perder, vide o slide 9 dos slides que coloquei nesse tópico.

Qual implementação do Scheme você tá usando?

;;contem? - verifica se uma lista contém um elemento 'x' 
(define (contem? x lista)
    (cond
        [(empty? lista) false]
        [else (cond
           [(= (first lista) x) true]
            [else (contem? x (rest lista))])]))
(contem?  1 (list 2 1))

;;distintos - verifica se uma lista contém elementos duplicados, removendo-os e retornando outra lista sem os elementos duplicados
(define (distintos lista)
  (cond
    [(empty? lista) false]
    [else (cond
            [(contem? (first lista) (rest lista))
             (distintos(rest lista))])]))
distintos(list 1 1 2 3 4 5)

Mudei lá pra booleano mas continua dando erro =/

Eu uso o DR. SCHEME da PLT SCHEME

"verifica se uma lista contém elementos duplicados, removendo-os e retornando outra lista sem os elementos duplicados "

tu tem que devolver uma lista, e não false.

uma lista vazia é a palavra chave empty.

o condicional (cond) da do “distintos” precisa de três testes e não dois testes:

1. Retornar uma lista vazia (empty) caso seja passada uma lista vazia.
2. Fazer o tratamento se o elemento esta na lista.
3. Fazer o tratamento se o elemento nao esta na lista.

dionat4n:

o condicional (cond) da do "distintos" precisa de três testes e não dois testes:

1. Retornar uma lista vazia (empty) caso seja passada uma lista vazia.
2. Fazer o tratamento se o elemento esta na lista.
3. Fazer o tratamento se o elemento nao esta na lista.

;;contem? - verifica se uma lista contém um elemento 'x' 
(define (contem? x lista)
    (cond
        [(empty? lista) false]
        [else (cond
           [(= (first lista) x) true]
            [else (contem? x (rest lista))])]))
(contem?  1 (list 2 1))

;;distintos - verifica se uma lista contém elementos duplicados, removendo-os e retornando outra lista sem os elementos duplicados
(define (distintos lista)
  (cond
    [(empty? lista) empty] ;retorna uma lista vazia(empty) caso seja passada uma lista vazia.
    [else (cond
            [(contem? (first lista) (rest lista)) ;se o elemento está na lista
             (distintos(rest lista))]
            [else (distintos(first lista))])]))   ;se elemento não está na lista 
             
distintos(list 1 1 2 3 4 5)

Tentei fazer do jeito que vc falou..mas continua dando o mesmo erro..
Não sei o que faço de errado na hora de tratar o elemento se ele está na lista

(define (distintos lista)   
  (cond   
    [(empty? lista)
         empty]
    [(contem? (first lista) (rest lista))   
         (distintos(rest lista))]     //Aqui deve-se retornar uma lista construída sem o elemento x
    [else
         (distintos(first lista))]))   //Aqui deve-se retornar uma lista construída com o elemento x

“Distintos” deve retornar uma lista sempre, em qualquer cláusula. Em cada chamada da recursão vai sendo construída a nova lista sem elementos repetidos, entendeu? Tenta estudar um pouco de recursão para entender melhor esse exercício.

Recursão:
[google]recursao[/google]

Para escolher a implementação do scheme que você quer usar no DrScheme, basta clicar no canto inferior esquerdo do editor e ir em “escolher linguagem”, dê preferência pra uma linguagem que seja R5RS, que é um padrão de implementação da linguagem… seu código tem chances de ser mais portável assim… a implementação que é usada no Teach Yourself Scheme… é a mzscheme.

Agora quanto ao seu problema, vou te dar umas dicas de como eu cheguei a resolução, mas tenha em mente que este não é o melhor jeito de resolver, foi mais uma implementação-de-cinco-minutos, mas que serve pra ilustrar a lógica principal do algorítmo.

Criei uma procedure que recebe uma lista como parâmetro e usa uma lista auxiliar para armazenar os elementos distintos.
Usei um named let pra percorrer por cada elemento da lista que foi recebida como parametro e utilizo sua procedure contem? para verificar se o elemento está contido na minha lista auxiliar de elementos distintos. Se o elemento já está contido na lista eu prossigo no named let, apenas passando como parametro o cdr (que no seu caso seria a função rest) da lista e a lista auxiliar, caso contrário passo o cdr da lista e a lista auxiliar + o elemento que ainda não foi inserido. Algo mais ou menos assim:

(if (contem? (car lst) lst-aux) (loop (cdr lst) lst-aux))
(else (loop (cdr lst) (cons (car lst) lst-aux))))))

Quebra a cabeça pra resolver isso aí, no ínicio o scheme é meio esquisitão mesmo…

(if (contem? (car lst) lst-aux) (loop (cdr lst) lst-aux))
(else (loop (cdr lst) (cons (car lst) lst-aux))))))

Loop em linguagem funcional?

Que feio, logo em scheme…

A maneira recursiva que eu encontrei pra resolver esse problema seria uma função com duas listas como parâmetro, algo mais ou menos assim:

O que não seria o caso do nosso colega, que queria algo como (distintos lst)

Como eu disse, existem outras maneiras de resolver isso, você poderia nos mostrar como solucionaria essa questão sem o named let?

Eu?

Com recursão ué…

É simples, vai construindo a lista recursivamente:

(distintos (L))
(distintos (1 2 2 3))
->
‘1’ não contém no resto da lista, então retorna (cons ‘1’ (distintos (2 2 3))
->
‘2’ contém no resto da lista, então retorna (distintos (2 3)
->
‘2’ não contém no resto da lista, então retorna (cons ‘2’ (distintos (3))
->
‘3’ não contém no resto da lista, então retorna (cons ‘3’ (distintos (empty))
->
lista vazia, retorna empty.
<- empty
<- (cons 3 empty)
<- (cons 2 (cons 3 empty))
<- (cons 2 (cons 3 empty))
<- (cons1 (cons 2 (cons 3 empty)))

Resposta final: (cons 1 (cons 2 (cons 3 empty)))

Tem que utilizar “cons” para construir uma lista que vai ser o retorno, de acordo com o que tem nos slides que eu coloquei aqui antes.

Eu não queria ter dado a resposta, queria que o amigo dali de cima descobrisse, mas foi.

Baaa pessoal, valeu pela ajuda, valeu mesmo, mas eu não consegui entregar a tempo…e peguei exame.
Hoje é a prova…e é escrita heheheh mas valeu mesmo
Abraço !

Afinal, funcionou ou não?

Funcionou !!!
Mas como eu resolvi depois da data de entrega não consegui escapar do exame…
Mas na prova tirei 7.0 e dai passei na disciplina…
Valeu a todos pela ajuda…
Abração !

Maravilha!

Foi boa a nossa conversa sobre o exercício!

Abraços!