Scala lists and splitting

Question

I have a homework assignment that's having us use a list and splitting it into two parts with the elements in the first part are no greater than p, and the elements in the second part are greater than p. so it's like a quick sort, except we can't use any sorting. I really need some tips on how to go about this. I know I'm using cases, but I'm not familiar with how the list class works in scala. below is what I have so far, but in not sure how to go about the splitting of the 2 lists.

using

 def split(p:Int, xs:List[Int]): List[Int] = {

 xs match {
   case Nil => (Nil, Nil)
   case head :: tail =>
 }

If you want to do it recursively, then within your function introduce a helper function of signature splitHelper(p: Int, input:List, greater:List, noGreater: List): (List, List). Obviously List[Int] everywhere. The helper function can only call itself or return a result. Implement your main function by calling: splitHelper(p, xs, Nil, Nil) — ponythewhite
– ponythewhite, Commented Nov 15, 2014 at 13:19

Bob Dalgleish · Accepted Answer · 2014-11-15 13:20:54Z

2

First off, you want split to return a pair of lists, so the return type needs to be (List[Int], List[Int]). However, working with pairs and lists together can often mean decomposing return values frequently. You may want to have an auxiliary function do the heavy lifting for you.

For instance, your auxiliary function might be given two lists, initially empty, and build up the contents until the first list is empty. The result would then be the pair of lists.

The next thing you have to decide in your recursive function design is, "What is the key decision?" In your case, it is "value no greater than p". That leads to the following code:

def split(p:Int, xs: List[Int]): (List[Int], List[Int]) = {
  def splitAux(r: List[Int], ngt: List[Int], gt: List[Int]): (List[Int], List[Int]) =
    r match {
      case Nil => (ngt, gt)
      case head :: rest if head <= p =>
        splitAux(rest, head :: ngt, gt)
      case head :: rest if head > p =>
        splitAux(rest, ngt, head :: gt)
    }
  val (ngt, gt) = splitAux(xs, List(), List())
  (ngt.reverse, gt.reverse)
}

The reversing step isn't strictly necessary, but probably is least surprising. Similarly, the second guard predicate makes explicit the path being taken.

However, there is a much simpler way: use builtin functionality.

def split(p:Int, xs: List[Int]): (List[Int], List[Int]) = {
  (xs.filter(_ <= p), xs.filter(_ > p))
}

filter extracts only those items meeting the criterion. This solution walks the list twice, but since you have the reverse step in the previous solution, you are doing that anyway.

answered Nov 15, 2014 at 13:20

Bob Dalgleish

8,2604 gold badges35 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ponythewhite Over a year ago

Why give solution instead of helping to come up with it?

The Archetypal Paul Over a year ago

If builtin functionality is permitted, there's an even simpler way - use xs.partition(_ <= p)

Collectives™ on Stack Overflow

Scala lists and splitting

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related