[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")


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

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

Ещё один вопрос про аппликативные функторы -- их отличие от монад в плане структурирования вычислений. Я его затрону как-нибудь потом, но сказать мне есть что.
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

If you are unable to use this captcha for any reason, please contact us by email at support@dreamwidth.org


 
Notice: This account is set to log the IP addresses of people who comment anonymously.
Links will be displayed as unclickable URLs to help prevent spam.

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 Oct. 17th, 2017 02:54 pm
Powered by Dreamwidth Studios