Geek asks and answers

How can I omit this case of Neil

I use scala to implement some common algorithms. When I tried to recreate the view of the bubble, I ran into this problem

Here is an implementation of the inner loop that bubbles up the upper value:

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)
}

My problem is with case Nil => Nil. I understand that I need this because I can apply Nilto this function. Is there a way to ensure that Nilit cannot be provided as an argument in a way that the compiler will satisfy, so that I can eliminate this case?

+5
source share
3 answers

The list has two subtypes: Nil and ::, therefore :: represents a list containing at least one element.

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))
}
+4
source

, , . , x x Nil. ( Coq ), , Nil, cons .

EDIT: Scala List , , . , , - , , .

+2

In this case, you can simply play with the sentence case:

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
}

The first two sentences will only match lists with one or more items. The last sentence will match elsewhere.

+2
source

More articles:


All Articles