Шаг за шагом к решению задач 8–11 из 99 упражнений в обобщенном виде
В этом руководстве представлены решения для решения задач 8–11 знаменитых 99 упражнений на Прологе (автор Вернер Хетт). Имея список целых чисел, мы рассмотрим различные методы обработки последовательных дубликатов. Сначала мы начнем с фрагмента кода для задачи № 8, а затем постепенно опишем более общий алгоритм, использующий функции более высокого порядка для решения этих четырех проблем на Scala.
Я использую следующий целочисленный список, содержащий несколько последовательных дубликатов, в качестве основы для тестирования.
val listdup = List (1,1,1,1,2,2,4,4,5,3,4,4,4,3,3)Давайте начнем с первой проблемы, где мы представляем два примера кода: жестко закодированный подход и гибкий функциональный метод, обеспечивающий возможность повторного использования.
Проблема № 8: Удалите последовательные дубликаты в списке
*Жестко запрограммированный подход
Учитывая приведенный выше список, удалите повторяющиеся копии каждого последовательного целого числа, сохраняя при этом последовательность нетронутой.
def removeDup(lst : List[Int]) : List[Int] = {
lst match {
case head::tail => {
val (duplst,remainlst) = lst.span(_ == head)
duplst.head :: removeDup(remainlst) }
case Nil => List()
}
}
scala> removeDup(listdup)
res: List[Int] = List(1, 2, 4, 5, 3, 4, 3)В приведенной выше функции список разбивается на два подсписка с помощью оператора span. Выбирается заголовок первого списка, который содержит дубликаты, а второй список (который содержит оставшиеся элементы) передается рекурсивно с использованием той же функции. Рекурсия завершается, когда в оставшемся списке больше нет элементов, которые нужно удалить.
* Использование функционального подхода
Приведенные выше фрагменты кода прямолинейны, а устранение дубликатов жестко закодировано в рекурсивной функции. Чтобы сделать код более пригодным для повторного использования, мы можем использовать внешнюю функцию, которая берет список повторяющихся целых чисел и очищает их до одного. Затем мы передаем функцию очистки в качестве параметра функции более высокого порядка reduceDup, которая вызывает рекурсивный алгоритм iter. Вот код для трех функций:
def reduceDup(ls : List[Int], reduce: List[Int] => List[Int]) : List[Int] = {
def iter (lst : List[Int]): List[Int] ={
lst match {
case head::tail => {
val (duplst,remainlst) = lst.span(_ == head)
reduce(duplst) ::: iter(remainlst) }
case Nil => List()
}
}
iter(ls)
}
def purge(ls : List[Int]) : List[Int] = {
ls.toSet.toList
}
scala> reduceDup(listdup,purge)
res: List[Int] = List(1, 2, 4, 5, 3, 4, 3)Без внутренней функции iter вы не можете рекурсивно перемещаться по списку. Это обычная техника, используемая в Scala для таких случаев, и язык позволяет программистам определять вложенные функции, в которых параметры внешней функции входят в область действия внутренней функции. Кроме того, в reduceDup мы объединяем два списка с помощью оператора :::, а в removeDup мы добавляем только один элемент в начало списка с помощью оператора ::.
Проблема № 10: Кодирование длин серий
Проблема: подсчет данных длин серий
Повторно используя код задачи № 8, мы можем очень легко реализовать простой подсчет данных, широко известный как кодирование длин серий. Последовательные дубликаты элементов объединяются, и их количество регистрируется в списке. Таким образом, все, что нам нужно, — это определить новую внешнюю функцию, которая выполняет операцию, а затем передает ее в качестве параметра рекурсивной функции reduceDup, установленной выше.
def length(ls : List[Int]) : List[Int] ={
List(ls.size)
}
scala> reduceDup(listdup,length)
res: List[Int] = List(4, 2, 2, 1, 1, 3, 2)Это довольно просто, и мы можем видеть здесь красоту функционального программирования и повторного использования кода, когда функции могут передаваться в качестве параметров функциям более высокого порядка.
Проблема № 10: Кодирование длин серий — простое сжатие данных
Аналогично результату предыдущей задачи, мы можем реализовать Задачу №10 — так называемый метод сжатия данных с кодированием длин серий. В этой задаче последовательные дубликаты данных кодируются как кортеж (N,D), где N — количество дубликатов элемента данных D.
Например, учитывая наш список данных, нам нужно создать следующий список кортежей:
val listdup = List (1,1,1,1,2,2,4,4,5,3,4,4,4,3,3)
res: List( (4,1), (2,2), (2,4), (1,5), (1,3), (3,4), (2,3) )Если мы попытаемся использовать функцию reduceDup, определенную выше, с новой функцией, которую мы назовем runLength, мы зайдем в тупик. Поскольку параметр сокращения (который принимает функцию в reduceDup) является отображением из List[Int] в List[Int], в то время как здесь мы берем список целых чисел, но генерируем кортеж в форме List[(Int,Int)]. Чтобы преодолеть эту проблему, мы переопределяем наш набор рекурсивных функций, используя универсальный тип T. Код для этого выглядит следующим образом.
// generic version
def processDup[T](ls : List[Int], reduce: List[Int] => List[T]) : List[T] = {
def iter (lst : List[Int]): List[T] ={
lst match {
case head::tail => {
val (duplst,remainlst) = lst.span(_ == head)
reduce(duplst) ::: iter(remainlst) }
case Nil => List[T]()
}
}
iter(ls)
}Тип T был абстрагирован и назначен в возвращаемых типах как внешней, так и внутренней функций; в результате мы получаем большую гибкость при передаче различных видов внешних функций в качестве параметров для выполнения различных операций. Например, приведенную ниже функцию runLength можно использовать для решения задачи № 10 и возврата списка кортежей вместо списка целых чисел.
def runLength(ls : List[Int]) : List[(Int, Int)] ={
List((ls.size,ls.head))
}
scala> processDup(listdup,runLength)
res: List[(Int, Int)] = List((4,1), (2,2), (2,4), (1,5), (1,3), (3,4), (2,3))Проблема № 8: Повторное посещение
Мы также можем использовать параметризованную универсальную версию для решения Задачи № 8, не написав ни одной строки кода. Простой вызов processDup вместо reduceDup и использование функции очистки сделают эту работу.
def purge(ls : List[Int]) : List[Int] = {
ls.toSet.toList
}
scala> processDup(listdup,purge)
res: List[Int] = List(1, 2, 4, 5, 3, 4, 3)Проблема № 9: упаковать последовательные дубликаты списка в подсписки
В Задаче №9 нам нужно сгруппировать повторяющиеся элементы в отдельные подсписки. Учитывая нашу универсальную функцию processDup выше, решение удивительно простое:
val listdup = List (1,1,1,1,2,2,4,4,5,3,4,4,4,3,3)
def group(ls : List[Int]) : List[List[Int]] = {
List(ls)
}
scala> processDup(listdup,group)
res: List[List[Int]] = List(List(1, 1, 1, 1), List(2, 2), List(4, 4), List(5), List(3), List(4, 4, 4), List(3, 3))Проблема № 11: Модифицированное кодирование длин серий — простое сжатие данных
В этой задаче мы модифицируем результат задачи № 10 таким образом, что если элемент не имеет дубликатов, он просто копируется в список результатов. Только элементы с дубликатами передаются как кортеж (N,D). Например, учитывая наш список данных, нам нужно создать следующий список данных/кортежей:
val listdup = List (1,1,1,1,2,2,4,4,5,3,4,4,4,3,3)
res: List( (4,1), (2,2), (2,4), 5, 3, (3,4), (2,3) )Используя результат Задачи № 10, мы сопоставляем каждый элемент в списке кортежей в соответствии с тем, равно ли N 1 или отличается от него. Фрагмент кода для выполнения преобразования:
scala> processDup(listdup, runLength).map{ case (len,e) => { if (len==1) e else (len,e) } }Заключительные замечания
В этих фрагментах кода мы продемонстрировали, что решение нескольких задач унифицированным способом не очень сложно. При правильном подходе и использовании абстракций, параметризованных типов и функций более высокого порядка вы можете писать на Scala очень лаконичный и пригодный для повторного использования код. Пожалуйста, не торопитесь, чтобы поэкспериментировать с этими примерами в качестве первого шага к изучению идиоматического подхода к функциональному программированию.
Наконец, в качестве бонусного упражнения вы можете попробовать изменить приведенную выше функцию processDup, чтобы она работала с другим параметризованным типом данных, например со строками. Изменив обработанный список как List[A] вместо List[Int], вы можете создать более общую рекурсивную функцию, которую можно использовать без изменения какой-либо из 4 представленных внешних функций.
Вот ссылка на историю на github:
https://github.com/abbas-taher/scala-processing-duplicates-in-a-list-the-functional-way
