Забавы с C#

Изучение нового языка может помочь разработчикам получить уникальную информацию и освоить новые подходы к написанию кода на других языках а-ля C#. Лично я предпочитаю здесь F#, поскольку теперь стал MVP в F#. Хотя я вкратце затрагивал функциональное программирование в одном из выпусков своей рубрики (bit.ly/1lPaLNr), сегодня я хочу повнимательнее посмотреть на этот язык.

Вполне вероятно, что в конечном счете код понадобится писать на C# (я сделаю это в следующем выпуске рубрики). Но кодирование на F# все равно может оказаться полезным по трем причинам:

1. F# иногда позволяет решать такие задачи проще, чем на C#;
2. думая о задаче на другом языке, часто помогает прояснить решение, прежде чем писать его на C#;
3. F# — .NET-язык, как и C#. Поэтому вполне допустимо решить задачу на F#, затем скомпилировать код в .NET-сборку и просто вызывать ее из кода на C#. (В зависимости от сложности вычислений или алгоритма это может быть более здравое решение.)

Рассматриваем задачу

Возьмем простую задачу для этого типа решения. Вообразите, что вы работаете над Speedy, приложением для управления личными финансами. В нем нужно «сверять» онлайновые транзакции с теми, которые пользователь вводит в приложение. Здесь цель заключается в том, чтобы проработать два списка по большей части идентичных данных и найти совпадения идентичных элементов. Что вы будете делать с несовпадающими элементами, вопрос пока открытый, но вы должны захватывать их.

Много лет назад я работал по контракту на одну из компаний, участвуя в создании программы, которая впоследствии стала самым популярным приложением для управления банковскими операциями с ПК. Тогда мне пришлось иметь дело с трудной задачей. Она относилась к представлению, откуда можно было проверить журнал счетов после скачивания транзакций пользователя, известных банку. Мне пришлось сверять эти онлайновые транзакции с теми, которые пользователь уже ввел в приложение, а затем спрашивать пользователя, что делать с расхождением в транзакциях, если таковое было.

Каждая транзакция состоит из суммы, даты транзакции и описательного «комментария». Загвоздка вот в чем: даты не всегда совпадали, равно как и комментарии.

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

Пишем решение на F#

Есть несколько принципов в функциональных языках, в большой мере определяющих то, насколько «функционально» вы мыслите. В данном случае один из первых принципов в том, что рекурсия предпочтительнее итерации. Другими словами, если традиционно обученный программист немедленно захочет выстроить пару вложенных циклов for, то функциональный программист использует рекурсию.

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

type Transaction =  
  {
    amount : float32;
    date : System.DateTime;
    comment : string
  }
type Register =
  | RegEntry of Transaction * Transaction

Один из типов — запись (record), и на самом деле это объект без некоторых признаков традиционной нотации объектов. Второй является типом размеченного объединения (discriminated union type), который на самом деле представляет собой скрытый граф объектов/классов. Я не стану здесь углубляться в глубины синтаксиса F#. Есть масса других ресурсов по этой теме, в том числе моя книга «Professional F# 2.0» (Wrox, 2010).

Достаточно сказать, что это входные и выходные типы соответственно. Причина, по которой я выбрал размеченное объединение для результата, вскоре прояснится. Располагая этими двумя определениями типов, довольно легко определить внешний скелет следующей функции:

let reconcile (local : Transaction list) (remote : Transaction list) : Register list = []

Помните, что в терминологии F# дескрипторы типов следуют за именем. Поэтому данное выражение объявляет функцию, которая принимает два списка Transaction и возвращает список Register. В том виде, в каком написано это объявление, пустой список просто не возвращается («[]»). Это хорошо, потому что теперь я могу заглушить несколько функций при тестировании — в стиле TDD (Test-Driven Development) — в обычном консольном приложении на F#.

Теперь я могу и должен написать это в инфраструктуре модульного тестирования, но того же самого можно добиться, используя System.Diagnostics.Debug.Assert и локально вложенные функции в main. Другие могут предпочесть работу с F# REPL — либо в Visual Studio, либо в командной строке, как показано на рис. 1.

Рис. 1. Создание консольного алгоритма с помощью F# REPL

[<EntryPoint>]
let main argv =
  let test1 =
    let local = [ { amount = 20.00f;
                    date = System.DateTime.Now;
                    comment = "ATM Withdrawal" } ]
    let remote = [ { amount = 20.00f;
                     date = System.DateTime.Now;
                     comment = "ATM Withdrawal" } ]
    let register = reconcile local remote
    Debug.Assert(register.Length = 1,
      "Matches should have come back with one item")
  let test2 =
    let local = [ { amount = 20.00f;
                    date = System.DateTime.Now;
                    comment = "ATM Withdrawal" };
                  { amount = 40.00f;
                    date = System.DateTime.Now;
                    comment = "ATM Withdrawal" } ]
    let remote = [ { amount = 20.00f;
                     date = System.DateTime.Now;
                     comment = "ATM Withdrawal" } ]
    let register = reconcile local remote
    Debug.Assert(register.Length = 1,
      "Register should have come back with one item")
  0 // возвращаем целочисленный код завершения

При условии, что у меня есть scaffold базового теста, я попробую рекурсивное решение, которое вы видите на рис. 2.

Рис. 2. Использование сравнения с шаблоном в F# для рекурсивного решения

let reconcile (local : Transaction list)
  (remote : Transaction list) : Register list =
  let rec reconcileInternal outputSoFar local remote =
    match (local, remote) with
    | [], _ -> outputSoFar
    | _, [] -> outputSoFar
    | loc :: locTail, rem :: remTail ->
      match (loc.amount, rem.amount) with
      | (locAmt, remAmt) when locAmt = remAmt ->
         reconcileInternal (RegEntry(loc, rem) :: outputSoFar) locTail remTail
      | (locAmt, remAmt) when locAmt < remAmt ->
         reconcileInternal outputSoFar locTail remTail
      | (locAmt, remAmt) when remAmt > locAmt ->
         reconcileInternal outputSoFar locTail remTail
      | (_, _) ->
         failwith("How is this possible?")
  reconcileInternal [] local remote

Как видите, здесь весьма интенсивно используется сравнение с шаблоном в F# (F# pattern matching). Оно концептуально похоже на блок switch в C# (точно так же, как кошечка концептуальна похожа на саблезубого тигра). Сначала я определяю локальную рекурсивную функцию (rec), которая в основном имеет ту же сигнатуру, что и внешняя функция. Пока что есть дополнительный параметр для переноса результатов совпадения.

Первый match анализирует оба списка — локальный и удаленный. Первый в match блок clause ( [],_) заявляет: если локальный список пуст, мне безразлично, каков удаленный список (знак подчеркивания является символом подстановки), поскольку я свою работу закончил. Поэтому просто возвращаются результаты, полученные на данном этапе. То же самое относится ко второму в match блоку ( _, []).

Суть всего этого проявляется в последнем в match блоке. Он извлекает первый элемент локального списка и связывает его с переменной loc, помещает остальной список в locTail, делает то же самое с удаленным списком (rem и remTail), а затем снова сравнивает их. На этот раз я извлекаю поля amount из каждого из двух элементов, выдернутых из списков, и связываю их с локальными переменными locAmt и remAmt.

В каждом из этих блоков в match я рекурсивно вызываю reconcileInternal. Ключевое отличие в том, что я делаю со списком outputSoFar перед рекурсией. Если locAmt и remAmt одинаковы, это совпадение, и тогда я добавляю к началу новый RegEntry в список outputSoFar перед рекурсией. В любом другом случае я просто игнорирую их и выполняю рекурсию. Результатом будет список элементов RegEntry, и именно он возвращается вызвавшему.

Расширяем идею

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

Рис. 3. Добавление новых элементов в Register

type Register =
  | RegEntry of Transaction * Transaction
  | MissingRemote of Transaction
  | MissingLocal of Transaction
let reconcile (local : Transaction list)
 (remote : Transaction list) : Register list =
  let rec reconcileInternal outputSoFar local remote =
    match (local, remote) with
    | [], _
    | _, [] -> outputSoFar
    | loc :: locTail, rem :: remTail ->
      match (loc.amount, rem.amount) with
      | (locAmt, remAmt) when locAmt = remAmt ->
         reconcileInternal (RegEntry(loc, rem) :: outputSoFar) locTail remTail
      | (locAmt, remAmt) when locAmt < remAmt ->
         reconcileInternal (MissingRemote(loc) :: outputSoFar) locTail remote
      | (locAmt, remAmt) when locAmt > remAmt ->
         reconcileInternal (MissingLocal(rem) :: outputSoFar) local remTail
      | _ ->
         failwith "How is this possible?"
  reconcileInternal [] local remote

Теперь результатом будет полный список с элементами MissingLocal или MissingRemote для каждого Transaction, не имеющего соответствующей пары. В действительности это не совсем так. Если два списка не совпадают по длине, как ранее мой test2, оставшиеся элементы не будут считаться недостающими (missing).

Принимая F# как язык для создания концепции вместо C# и используя принципы функционального программирования, решение находится довольно быстро. F# интенсивно использует логическое распознавание типов, поэтому во многих случаях, детализируя код, мне не приходится преждевременно определять реальные типы для параметров и возвращаемого значения. Рекурсивные функции в F# будут часто требовать аннотации типа, чтобы определить тип возвращаемого значения. Здесь я обошелся без этого, потому что тип возвращаемого значения можно логически распознать по внешней (обрамляющей) функции.

В некоторых случаях я мог бы просто скомпилировать все это в сборку и передать разработчикам на C#. Однако в большинстве случаев такой фокус не пройдет. Поэтому в следующий раз я конвертирую код под C#. Начальник никогда не узнает, что этот код на самом деле начал свою жизнь в F#.