2012-09-30 25 views
5

Estoy haciendo tonterías con scala implementando algunos algoritmos comunes. Al intentar volver a crear una especie de burbuja me encontré con este problema¿Cómo puedo omitir este caso Nil

Aquí es una implementación de un bucle interno que burbujea el valor de la parte superior:

def pass(xs:List[Int]):List[Int] = xs match { 
    case Nil => Nil 
    case x::Nil => x::Nil 
    case l::r::xs if(l>r) => r::pass(l::xs) 
    case l::r::xs => l::pass(r::xs) 
} 

Mi problema es con el caso Nil => Nil. Entiendo que necesito esto porque podría aplicar Nil a esta función. ¿Hay alguna forma de garantizar que Nil no se pueda proporcionar como argumento de manera que satisfaga al compilador para que pueda eliminar este caso?

Respuesta

4

La lista tiene dos subtipos, Nil y ::, entonces :: representa una lista que tiene al menos un elemento.

def pass(xs: ::[Int]):List[Int] = xs match { 
    case x::Nil => x::Nil 
    case l::r::xs if(l>r) => r::pass(new ::(l,xs)) 
    case l::r::xs => l::pass(new ::(r, xs)) 
} 
+1

Ah, bueno, no estaba al tanto de esto, ya que no conozco Scala :-) –

+1

Tenga en cuenta que esto significa que no podrá aplicar esta función a valores 'List [Int]' en general, porque el compilador usualmente no está al tanto de si una 'Lista [Int]' determinada estará vacía o no en el tiempo de ejecución (para hacerlo, en general, se requiere resolver el Problema de Detención). La coincidencia de patrones es el mecanismo por el cual un valor general desconocido de 'List [Int] 'puede bajar dos ramas diferentes según si es' Nil' o ':: [Int]'.Eso significa que si está pasando listas como 'Lista [Int]', generalmente tendría que coincidir con el patrón cada vez que llame a 'pass'. – Ben

+0

Y ni siquiera se puede llamar como 'pase (1 :: 2 :: Cero)' ... –

2

Esto correspondería más o menos a un refinamiento del tipo original, donde escribiría un tipo cuyos miembros eran un subconjunto del tipo inicial. A continuación, mostraría que, para cada entrada x a su función, esa x no era Nil. Como esto requiere una buena cantidad de pruebas (puede implementar esto en Coq con tipos dependientes usando un tipo de subconjunto ), lo mejor que puede hacer en esta situación podría ser introducir un nuevo tipo, que era una lista que no tiene Nil constructor , solo un constructor de contras y un solo elemento.

EDITAR: Como Scala le permite usar el subtipado sobre el tipo de lista para imponer esto, puede probarlo en el sistema de tipos de manera decidible utilizando ese subtipo. Esto es todavía una prueba, en el sentido de que cualquier verificación de tipo corresponde a una prueba de que el programa efectivamente habita de algún tipo, es algo que el compilador puede probar completamente.

+0

¿por qué el voto a favor? No veo nada malo con esta respuesta? ¿Puedes señalar algo técnicamente incorrecto en él? Si es así, lo cambiaré o eliminaré. –

+0

Porque puede utilizar el truco propuesto por Kim Stebel sin recurrir a ningún tipo de prueba compleja ... – paradigmatic

+0

@paradigmatic mal, todavía corresponde a una prueba en el sistema de tipo, la prueba es a través de subtipificación, por lo que todavía hay una prueba, es solo en una lógica decidida. Todavía una prueba, pero edité mi respuesta para anotar la tuya. –

2

En ese caso, puede simplemente jugar con las cláusulas case orden:

def pass(xs:List[Int]):List[Int] = xs match { 
    case l::r::xs if(l>r) => r::pass(l::xs) 
    case l::r::xs => l::pass(r::xs) 
    case xs => xs 
} 

Las primeras dos cláusulas sólo igualará listas con uno o más elementos. La última cláusula coincidirá en otro lugar.

+1

no veo cómo esto se opone a Cero que se pasa. El compilador todavía no puede cumplir esa Ninguna pasar como una argumento dado el reordenamiento. –

+0

no se opone a ella, sino que permite a "ommit el caso Cero" como se indica en el título de la pregunta. – paradigmatic

+1

Quizás esté de acuerdo con el título, pero no está de acuerdo con la afirmación de que el OP quiere "garantizar que Nil no pueda proporcionarse como argumento de manera que satisfaga al compilador para que pueda eliminar este caso" –

Cuestiones relacionadas