[personal profile] gdsfh
У меня была необходимость разобрать записи, получаемые от реляционки (от постгреса в моём случае), в окамле, который строго типизирован.

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

type record;

(* [get_field n] возвращает нетипизированное значение
   столбца -- строку с данными *)
value get_field : int -> record -> string;

(* тип записи -- в простом случае преобразование
   идентификатора столбца в номер столбца *)
type record_type = ident -> int;


Как же разбирать данные? Классически это делают через тип, включающий в себя все варианты:

type sql_t =
  [= `Null
  |  `String of string
  |  `Int of int
  |  `Num of Decimal.t
  | ...
  ];

(* get sql_t by field index *)
value geti_t : int -> record -> sql_t;

value process_record record =
  match (geti_t 0 record, geti_t 1 record) with
  [ (`Int id, `String name) -> printf "id=%i, name=%s\n" id name
  | ...
  ];


Ну, классика: если есть значение с типом sql_t, то его можно заматчить, и не надо преобразовывать каждый раз "int_of_string (get_field 1 record)".
Но есть проблемки.
  1. это уродливо
  2. это вызывает предупреждение компилятора о том, что "вот вы заматчили `Int _, а вдруг там `Date _ какой-нибудь будет?", и компилятор фактически прав (альтернатива -- матчить "всё остальное" второй веткой, но предупреждение будет другим: "данный матчинг будет матчить всё, даже если в sql_t добавят новые конструкторы" -- подразумевается, что если работаете с вариантным типом, лучше писать так, чтобы каждое значение обрабатывалось своим match case, и чтобы при расширении типа можно было просто пробежаться по коду согласно предупреждениям компилятора и везде, где надо, добавить правильный матчинг свежедобавленного варианта)
  3. значения надо заворачивать в sql_t -- фактически, выделение памяти, которого мы избежим в качестве мелкого бонуса
  4. паттерн-матчинг для разбора sql_t не будет выпоняться для каждой строки и каждого столбца: фактически, для каждого запроса и каждого читаемого столбца будет выполняться ровно одна проверка, а дальше будут возвращаться уже конкретные значения нужных типов


Более того, нужно уметь ссылаться на столбцы по их идентификаторам:

value getn_t : ident -> record -> sql_t = fun ident record ->
  let record_type = ... in
  let index = record_type ident in
  geti_t index record;

value process_record record =
  match (getn_t "ID" record, getn_t "NAME" record) with
  [ (`Int id, `String name) -> printf "id=%i, name=%s\n" id name
  | ...
  ];


Тут наталкиваемся ещё на одну проблему: либо имена будут отображаться на индексы при каждом разборе записи, либо нужно где-то сохранять индексы, либо не нужно использовать имена и нужно откатиться до использования индексов. Тоже негламурно.

Я смутно помнил, что есть такая штуковина как "аппликативные функторы" (applicative functors). Когда увидел cmdliner (OCaml module for the declarative definition of command line interfaces), понял, что мне нужно что-то подобное. (кстати, для другой моей задачи -- для разбора урлов -- тоже пригодятся аппликативные функторы, но в будущем.)

Краткий экскурс в предмет аппликативных функторов.

Аппликативный функтор -- параметризованный тип данных f 'a, в который можно втаскивать значения функцией pure (наподобие того, как в манатки втаскивают значения через return) и применять втащенные значения одно к другому инфиксным левоассоциативным оператором <*>. Добавим ещё функцию run, не классическую, но полезную для извлечения значения из аппликативного функтора.

type f 'a;
value pure : 'a -> f 'a;
value ( <*> ) : f ('a -> 'b) -> f 'a -> f 'b;
value run : f 'a -> 'a;


Одна из замечательных структур данных, являющаяся аппликативным функтором, это стрелка с зафиксированным левым типом:

module Af
 =
  struct
    type af 'x 'a = 'x -> 'a;
    value pure a = fun _ -> a;
    value ( <*> ) fab fa = fun x -> (fab x) (fa x);
    value (run : 'x -> af 'x 'a -> 'a) a fa = fa a;
  end
;


Как это всё работает: создаётся структура из замыканий кодом вида (pure f) <*> (af_a : af 'x 'a) <*> (af_b : af 'x 'b), затем вычисления "запускаются", когда становится известен аргумент с типом 'x.

Какой тип будет выведен/приемлем для f? Если его оборачивают в pure, а потом применяют значение с типом af 'x 'a, то pure f должен иметь тип af ('a -> 'z), но так как потом применяют ещё и af 'x 'b, то pure f должен иметь тип af ('a -> 'b -> 'z), и соответственно f должно иметь тип 'a -> 'b -> 'z. Вот так мы "эмулировали" переменное количество разнотипных аргументов.

Представим, что у нас написаны функции, берущие "строку", "число" и прочие типы данных, по номеру столбца:

value geti_string : int -> record -> string;
value geti_int : int -> record -> int;


Представим их в виде аппликативных функторов -- просто заметив, что record -> 'a можно записать как af record 'a, и введём новый тип:

(* applicative functor over database records: *)
type afr 'a = af record 'a;
value geti_string : int -> afr string;
value geti_int : int -> afr int;


Теперь мы сможем записать код с печатью id и name так:

value process_record record =
  run record & pure f <*> (geti_int 0) <*> (geti_string 1)
  where f id name =
    printf "id=%i, name=%s\n" id name
;


Если бы не индексы, решение было бы идеальным. Если же "в лоб" записать функции, берущие идентификаторы столбцов, то от проблемы не уйдём -- придётся для каждой записи делать ненужные поиски индекса столбца по его идентификатору. Мну груфняво :(((99999

Посмотрим на природу таких аппликативных функторов, составленных из стрелки. Все элементы образуют структуру, и при передаче конкретной записи они её используют для определения конкретных значений чисел и строк, содержащихся там. (кроме элемента, засунутого в pure -- его аргумент кушается функцией pure молча.) А ведь можно завернуть этот аппликативный функтор в другой, который будет кушать "тип записи" и "резолвить" идентификаторы! Так, что для данного типа записи "резолвинг" будет выполняться один раз, и дальше будет работа с индексами, но скрытая от глаз, ибо скучная.

Тип мне кое-чем ещё полезен, поэтому поименую его.

module Af2
 =
  struct
    type af2 'x 'y 'a = 'x -> 'y -> 'a;
    value (pure1 : af 'y 'a -> af2 'x 'y 'a) a = fun _ -> a;
    value (pure2 : 'a -> af2 'x 'y 'a) a = fun _ -> fun _ -> a;
    value ( ( <**> ) :
      af2 'x 'y ('a -> 'b) -> af2 'x 'y 'a -> af2 'x 'y 'b
      ) =
      fun ffab ffa ->
        fun x ->
          let fab = ffab x
          and fa = ffa x in
          fun y ->
            (fab y) (fa y)
    ;

    (*
    value bad1_ap ffab ffa x y = (ffab x y) (ffa x y);
    value bad2_ap ffab ffa = fun x y -> (ffab x y) (ffa x y);
    *)

    value (run1 : 'x -> af2 'x 'y 'a -> af 'y 'a) x ffa = ffa x;
    value (run2 : 'x -> 'y -> af2 'x 'y 'a -> 'a) x y ffa = ffa x y;

  end
;


Замечу, что закомментированные варианты -- плохие, негодные, хотя с точки зрения семантики эквивалентны правильному. Модель вычислений в окамле такова, что при вычислении "(fun a b -> E) x" замыкание так и будет висеть, храня функцию и при применении "y" вычисляясь: "(fun a b -> E) x y" -> "E [a := x, b := y]". Если же запишем "(fun a -> fun b -> E) x", то это выражение вычислится сразу, вернув "(fun b -> E [a := x])". Если же выражение имеет вид "(fun a -> let aa = ... in fun b -> E)", то "aa" вычислится при применении первого же аргумента, в отличие от "(fun a b -> let aa = ... in E)", где оно будет вычисляться каждый раз. Окамл даёт программисту много способов проконтролировать использование ресурсов (процессора, памяти), я это ценю.

И вот, имея "geti_string : int -> af record string", напишем комбинатор, берущий подобные функции и возвращающий функции, предварительно "резолвящие" столбец на основании переданного типа записи:

type aft 'a = af2 record_type record 'a;
value (i_of_n : (int -> afr 'a) -> (ident -> aft 'a)) geti =
  fun ident ->
    fun (record_type : ident -> int) ->
      let index = record_type ident
        (* index вычисляется только при применении аргумента record_type *)
      in
      fun record ->
        geti index record
;

value getn_string = i_of_n geti_string
  (* этот код мономорфный, приведён только для демонстрации,
     на самом деле надо чуть по-другому -- ask me how. *)
;


Представим, что нужно пробежаться по куче записей, и напишем функцию iter:

value (iter : dataset -> aft unit -> unit) dataset aft =
  let record_type = record_type_of_dataset dataset in
  let afr = Af2.run1 record_type aft in
  for i = 0 to (nrecords dataset) - 1 do
    let record = record_of_dataset dataset i in
    Af.run record afr
;


Обратите внимание, что резолвинг идёт только один раз, и значение afr содержит только взятия по индексам.

Более того, взятие по индексам и взятие по именам можно комбинировать:

(pure2 (fun i s -> printf "first column: %i, name: %s\n" i s))
  <**> (pure1 & geti_int 0)
  <**> (getn_string "NAME")


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

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

Ещё один вопрос про аппликативные функторы -- их отличие от монад в плане структурирования вычислений. Я его затрону как-нибудь потом, но сказать мне есть что.

Profile

gdsfh

August 2013

S M T W T F S
    123
45678910
111213 14151617
18192021222324
25262728293031

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Mar. 24th, 2017 12:02 pm
Powered by Dreamwidth Studios