GrabDuck

Пишем свои монады на Scala на примере CSV-парсера

:

За последнее время мы очень многое узнали о монадах. Мы уже разобрались что это такое и даже знаем как их можно нарисовать, видели доклады, объясняющие их предназначение. Вот и я решил заскочить в уходящий монадный поезд и написать по этой теме, пока это окончательно не стало мейнстримом. Но я зайду с немного другой стороны: здесь не будет выкладок из теории категорий, не будет вставок на самом-лучшем-языке, и даже не будет scalaz/shapeless и библиотеки parser-combinators. Как известно, лучший способ разобраться как что-то устроено — сделать это самому. Сегодня мы с вами будем писать свою монаду.

image


Возьмем для примера банальную задачу: парсинг CSV-файла. Допустим нам требуется распарсить строки файла в case classes, чтобы потом отправить их в базу, сериализовать в json/protobuf и так далее. Забудем про escaping и кавычки, для еще большей простоты, считаем что символ разделителя в полях встречаться не может. Думаю, если кто-то решит затащить это решение в свой проект, докрутить эту фичу будет не трудно.


Допустим у нас есть следующий CSV файл:

1997;Ford;E350;ac, abs, moon;3000.00
1996; Jeep; Grand Cherokee; MUST SELL! air, moon roof, loaded; 4799.00
1999;Chevy;Venture "Extended Edition"; ; 4900.00

Нам нужно десериализовать его в набор объектов следующего типа:

case class Car(year: Int, mark: String, model: String, comment: String, price: BigDecimal)

Чтобы было с чем сравнивать, я должен привести пример из жизни, который использование монад делает нагляднее, приятнее, надежнее и т.п.

Допустим файл строкой уже загружен в переменную content:

val lines = content.split('\n')

val entities = 
  lines.map { line =>
    line.split(';').map(_.trim) match {
      case Array(year, mark, model, comment, price) =>
        Car(year.toInt, mark, model, comment, BigDecimal(price))
    }
  }.toSeq

Минусы подхода:


  • Смешивание логики конвертации типов полей и конструирования самой сущности.
  • Boilerplate case matching: при росте числа полей код будет стремительно утрачивать читаемость.
  • Нужно явно обрабатывать случаи когда число полей не соответствует ожидаемому, когда строка слишком длинная и т.п.

Плюсы:


  • Straight-forward: отсутствие дополнительных слоев абстракции.

Я предлагаю взглянуть на задачу с другой стороны.


  • Представим что в начале мы имеем один фрагмент сырых данных — в частном случае — строку из файла, хотя на самом деле нам это не важно: это может быть byte array, список слов, итератор, все что угодно, из чего мы можем получать данные.
  • Допустим что каждую запись мы парсим в несколько этапов, каждый из которых — это парсинг конкретного поля в записи. Тогда для каждого этапа мы можем зафиксировать результат: значение этого поля (далее слово) + остаток сырых данных (далее остаток), которые мы будем рассматривать на последующих этапах парсинга, извлекая из него следующие поля записи. Или не будем, если поле последнее.
    Далее, для краткости будем называть эту функцию "обработчик".
  • Тогда в итоге нам останется только совместить результаты этих этапов в конечную сущность.

image

Возвращаясь к коду, обработчик каждого этапа иметь объявление вроде:

def parse[T, Src]: Src => (T, Src)

Теперь немного о самих монадах.

В двух словах монаду можно описать как контейнер, содержащий значение + некий контекст.
Синтаксически, в случае со Скалой, это значит что монада должна иметь метод flatMap, в общем случае объявляемый как:

def flatMap[T](f: T => M[T]): M[T]

Если f — значение, хранимое в контейнере, то что же такое контекст? А вот что: хотя у f только один аргумент, но, поскольку мы можем вызывать изнутри одного flatMap'a другой flatMap, то из внутреннего flatMap нам будут доступны все значения, объявленные внутри внешнего, то есть в том числе и все предыдущие слова.

image

Обратите внимание, что реализовывать метод map от монады не требуется, но мы его все-таки определим, он пригодится нам для создания модифицированных парсеров из уже определенных.

Также нужно определить операцию заворачивания чистого значения в монаду. Это не метод класса, но это может быть вызов конструктора, либо метод apply у companion object'а, никакого строгого требования к этому нет, и я предлагаю для удобства определить метод apply.

Реализуем монаду, содержащую в себе функцию parse, такого вида как мы определили выше и посмотрим, как мы сможем с ее помощью комбинировать разные парсеры.

Итак нам нужно написать класс, инкапсулирующий парсинг поля конкретного типа, который:


  1. Реализует метод flatMap
  2. Реализует метод map
  3. Также нужно определить операцию apply у companion object'a.
  4. Нужно определить интерфейсный метод, который будет вызываться конечным клиентским кодом и не будет содержать лишних деталей в объявлении.
class Parser[T, Src](private val p: Src => (T, Src)) {
  def flatMap[M](f: T => Parser[M, Src]): Parser[M, Src] =
    Parser { src =>
      val (word, rest) = p(src)
      f(word).p(rest)
    }
  def map[M](f: T => M): Parser[M, Src] =
    Parser { src =>
      val (word, rest) = p(src)
      (f(word), rest)
    }
  def parse(src: Src): T = p(src)._1
}

Так что-же происходит в методе flatMap?
Мы применяем обработчик текущего парсера к входному значению, затем с помощью функции — аргумента метода добавляем его в контекст, видимый всем последующим парсерам по цепочке.

С методом map же все намного понятнее, мы просто применяем его аргумент — функцию f на текущее слово, а все остальное оставляем неизменным.

И companion object, содержащий операцию point, она же — метод apply, он же — вызов объекта с круглыми скобками:

object Parser {
  def apply[T, Src](f: Src => (T, Src)) =
    new Parser[T, Src](f)
}

И что? Какие преимущества нам предоставляет этот подход, кроме несомненного повышения вашего авторитета у незнакомых с монадами коллег? Сейчас увидим.

Используя предложенную выше абстракцию, наконец напишем наш инновационный, функциональный, типобезопасный CSV-парсер.


Пишем парсеры типов полей

Для начала реализуем парсер одного поля типа String.

def StringField =
  Parser[String, String] { str =>
    val idx = str.indexOf(separator)
    if (idx > -1)
      (str.substring(0, idx), str.substring(idx + 1))
    else
      (str, "")
  }

Ничего сложного, правда?

А теперь посмотрим, как можно на базе StringField определить парсер типа Int.
Еще проще!

def IntField = StringField.map(_.toInt)

Аналогично для всего остального:

def BigDecimalField = StringField.map(BigDecimal(_))
def IntField = StringField.map(_.toInt)
def BooleanField = StringField.map(_.toBoolean)
// все что еще вам нужно

Собираем все воедино

До сих пор мы рассмотрели только парсеры отдельных полей, но как нам собрать эти поля в единую сущность? Вот тут нам и придет на помощь тот самый контекст. Благодаря ему, мы можем использовать в нижележащих парсерах значения, полученные в вышележащих.

Итак, конструирование конечного парсер сущностей будет выглядеть так:

val parser =
  for {
    year <- IntField
    mark <- StringField
    model <- StringField
    comment <- StringField
    price <- BigDecimalField
  } yield Car(year, mark, model, comment, price)

По моему выглядит очень круто.
Если вы вдруг не полностью уверенно себя чувствуете с синтаксическим сахаром for comprehension, то вот примерно так это бы выглядело в виде цепочки flatMap'ов:

IntField.flatMap { year =>
  StringField.flatMap { mark =>
    StringField.flatMap  { model =>
      StringField.flatMap  { comment =>
        BigDecimalField.map  { price =>
          Car(year, mark, model, comment, price)
        }
      }
    }
  }
}

Выглядит, конечно, это немного хуже, зато становится очевидно о каких контекстах идет речь, это области видимости, ограниченные фигурными скобками.

Мы получили парсер parser, теперь все что нам нужно, это построчно скормить исходный файл его методу parse и получить результат. Например так:

val result = str.split('\n').map(parser.parse)

Результат:

Array(Car(1997,Ford,E350,ac, abs, moon,3000.00), Car(1996,Jeep,Grand Cherokee,MUST SELL! air, moon roof, loaded,4799.00), Car(1999,Chevy,Venture "Extended Edition",,4900.00))

Плюсы


  • Конечный парсер описывается красиво и лаконично, из его объявления легко понять типы и последовательность полей в файле, его легко изменять и тестировать.
  • Вы крутой специалист, знающий толк в ФП, могущий в монады и вообще самый модный на районе в опенспейсе.

Минусы


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

Монады и прочие категории в Скале — не что-то такое без чего нельзя жить. Более того, они практически никак не навязываются самим языком. По сути, монадность в Скале — это небольшой ad-hoc контракт, выполняя который вы получаете возможность использовать свои классы в for-comprehension. И на этом все.

Тем не менее гибкость языка и возможность довольно легко реализовывать на нем довольно хитрые конструкции — это безусловный плюс языка, развязывающий руки для экспериментов.

Насчет того, стоит ли использовать такого рода конструкции в продакшн коде: я не знаю, это выбор каждой отдельной команды. Наверное, я бы сначала постарался выделять их в отдельные библиотеки, покрывать тестами и всячески обкатывать (хотя мы конечно знаем, что у настоящих функциональщиков все работает и без тестов). А для логики, которая нужна здесь и сейчас, скорее использовал бы более straight-forward реализации.