Scala списки и раскалывание

Question

У меня есть домашнее задание, в котором мы используем список и разделяем его на две части, причем элементы в первой части не больше p, а элементы во второй части больше p. так что это похоже на быстрый вид, за исключением того, что мы не можем использовать какую-либо сортировку. Мне действительно нужно несколько советов о том, как это сделать. я знаю, что я использую случаи, но я не знаком с тем, как класс списка работает в scala. ниже - то, что у меня есть до сих пор, но не уверен, как идти о разбиении 2 списков.

использованием

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

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

Answer 1

Во-первых, вы хотите split вернуть пару списков, поэтому тип возвращаемого значения должен быть (List[Int], List[Int]). Однако работа с парами и списками может часто означать частое разложение возвращаемых значений. Возможно, вам понадобится вспомогательная функция для тяжелого подъема.

Например, вашей вспомогательной функции могут быть предоставлены два списка, изначально пустые, и создавать содержимое до тех пор, пока первый список не станет пустым. Тогда результатом будет пара списков.

Следующее, что вам нужно решить в своем рекурсивном дизайне функций, - «Каково главное решение?». В вашем случае это значение «не больше, чем p». Это приводит к следующему коду:

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

Шаг реверсирования не является абсолютно необходимым, но, вероятно, является наименее удивительным. Аналогичным образом, второй защитный предикат делает явным путь, который делается.

Однако существует гораздо более простой способ: использовать встроенную функциональность.

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

filter извлекает только те предметы, которые соответствуют критерию. Это решение просматривает список дважды, но поскольку у вас есть шаг reverse в предыдущем решении, вы все равно это делаете.