Fórum: Programação Multiparadigma

Prática 1

 
Picture of Artur Miguel Dias
Prática 1
by Artur Miguel Dias - quarta, 19 setembro 2012, 9:31
 

O exercicío 11 da primeira prática pede para elaborarmos um "sort" e eu resolvi-o assim:
     def sort[T <% Ordered[T]](l: List[T]): List[T] = l.sort((e1,e2) => e1 < e2)
É assim que o professor quer o método?

O que eu pretendia era uma definição recursiva normal, mas a minha pergunta talvez não estivesse clara.
Reescrevi a pergunta 11 da aula prática 1.

Picture of Miguel Carvalho Pires
Re: Prática 1
by Miguel Carvalho Pires - quinta, 20 setembro 2012, 7:33
 

Sugere-se algum algoritmo de ordenação em particular? Implementei um merge sort, mas penso que tanto um Quick Sort ou um Insertion Sort são igualmente elegantes num contexto funcional.

Picture of Artur Miguel Dias
Re: Prática 1
by Artur Miguel Dias - quinta, 20 setembro 2012, 8:03
 

Se não houver nenhum algoritmo decidido à partida, o normal é começar por assumir como ponto de partida que já se tem a cauda da lista ordenada.

Dessa forma descobre-se sem querer o algoritmo Insertion Sort.

Era essa a solução de que estava à espera (apesar de se tratar dum algoritmo com complexidade quadrática).

Picture of Artur Miguel Dias
Re: Prática 1
by Artur Miguel Dias - quinta, 20 setembro 2012, 8:10
 
Professor não estou a conseguir a fazer o union, não me deixa fazer a comparação x > y e x < y. Porque razão? A lógica por mim parece a correcta, pode ajudar-me pf? Obrigado!  
 
def union[T](f:Set[T], s:Set[T]) : Set[T] =
    (f,s) match {
    case (Nil,_) => s
    case (_,Nil) => f
    case (x::xs, y::ys) => 
      if (x > y) y::union(x::xs, ys)
      else if (x < y) x::union(xs, y::ys)
      else x::union(xs, y::ys)
  }

Você está a assumir que está a trabalhar com listas ordenadas e que o tipo T tem disponível a operação "<". Para isso ser possível, seria necessário introduzir uma restrição sobre o tipo T.

Contudo o enunciado diz explicitamente que as listas não são ordenadas e alguns dos exemplos até apresentam listas não ordenadas. A solução pretendida é mais simples do que a sua (embora não tão eficiente).