MapM

Apr. 18th, 2011 11:20 am
[personal profile] gdsfh
Abstract:
В данной статье я расскажу вам про отображающие функции вида map, включающие в себя сайд-эффекты. Тем, кому известен хаскель, эти функции известны как mapM и подобные.
Далее, будет показано, что хаскель, будучи самым распространённым языком из тех, где используются монады (ну, кроме C#/linq и Scala), является непрактичным из-за отсутствия сайд-эффектов. Раньше мне без сайд-эффектов было всего лишь просто неудобно использовать хаскель (требовалось городить лишний код), теперь же я понимаю, что есть некоторые вещи, где с чистотой не получится клёво использовать монады в одном из их применений.
Также будет показано, что тайпклассы -- это не гибко, потому что у одного тайпкласса и у одной функции (например, "функция sequence в монаде IO") может быть только одна реализация, и будет показано, где именно это не гибко.


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

Исходные данные:
Есть хаскелевая функция
mapM : (a -> IO b) -> [a] -> IO [b]
, отображающая список аргументов действий с сайд-эффектами на сайд-эффект со списком результатов. Первый аргумент -- функция, которая содержит собственно сайд-эффект, возможно зависящий от аргумента с типом a, второй аргумент -- список исходных значений (аргументов), а результат -- список результатов, обёрнутый в манатку IO.
Но эта функция не универсальна, а я этого не люблю. (и вам рекомендую не любить неуниверсальные функции.)
Явно тут можно 1. абстрагировать монаду IO, если понять, что же на самом деле нужно от неё для реализации этого алгоритма, 2. абстрагировать разбор изначального списка (второго аргумента) и создание результирующего списка (результата выполнения функции).

Задача:
Сделать mapM, такой, чтобы от обоих сущностей (от монады IO и от штуки, делающей список) требовалось как можно меньше.

Текущее типа-решение:
На хаскеле -- сложно и не нужно. Почему -- смотрите:

Текущие требования от входных данных:
На окамле -- достаточно потребовать от монады наличия bind, return, и ещё
sequence : [IO a] -> IO [a]
, либо, в моём случае,
sequence_array : array (IO.m 'a) -> IO.m (array 'a)
От списка (который [a] в примере) мне достаточно потребовать функториальности, то есть, того, что это "функтор" в терминах теории категорий. А именно, это такая штука, которая имеет свою структуру и позволяет отображать носимые ей элементы какой-либо функцией, которая меняет сами элементы, но не меняет структуру. То есть, функтор F, носящий значения с типом F.t 'a, имеет функцию fmap : ('a -> 'b) -> (F.t 'a -> F.t 'b). Например, список удовлетворяет интерфейсу функтора: если у нас есть список целых чисел, то мы всегда можем отобразить его на список строк, каждая из которых представляет написание этого числа в виде строки, то есть, fmap для списков в окамле будет называться List.map.
Понятно, что многие другие структуры данных удовлетворяют интерфейсу функтора -- массивы (Array.map), деревья (как по ключу, так и по ассоциированным с ключом значениям), хеш-таблицы, опциональный тип (достаточно отображать None на None и Some x на Some (f x)). Кроме того, любая монада может быть функтором, где fmap реализуется как
value fmap f m = m >>= fun x -> return f x;
Конечно, функтору не обязательно быть монадой. "Быть монадой" -- это вообще весьма сильное требование, излишнее много где. А хорошее решение -- то, которое требует минимума от входных данных и даёт максимум выходных данных. Поэтому будем делать хорошее решение: mapM над монадой, умеющей вдобавок sequence_array, и над функтором, умеющим fmap.

Текущее решение:
Вы спросите -- как же можно сделать mapM, имея только fmap? Ведь для этого нужно сначала разбирать структуру данных (в классическом случае -- список), а потом собирать его заново, с новыми результатами. Либо нужно уметь взять список значений, имеющихся в структуре данных, затем отобразить их действиями с сайд-эффектами, затем "вставить" отображённые значения в структуру взад. И, действительно, без сайд-эффектов это не получится. Надо будет требовать от структуры данных больше, чем просто функториальность. Например, что-то про сборку-разборку структуры данных (foldable? zippers? не думал, поэтому что не хочу напрягать мозг там, где это не нужно.).

Итак, мы делаем таким образом. В первую очередь отображаем структуру с типом F.t 'a на структуру с типом F.t int с целыми числами в узлах с оригинальными значениями, являющимися индексами в массиве этих значений, и на массив, хранящий оригинальные значения, которые мы собираем как сайд-эффект во время выполнения fmap. То есть,
value index : F.t 'a -> (array 'a * F.t int);
Далее отображаем массив array 'a в массив действий, производящих сайд-эффекты, имеющий тип array (IO.m 'b) тупо применением Array.map (напомню, функция, выполняющая сайд-эффекты, имеет тип 'a -> IO.m 'b).
Далее через
value sequence_array : array (IO.m 'b) -> IO.m (array 'b);
отображаем массив действий на действие, содержащее массив результатов, таким образом выполняя сайд-эффекты.
Далее отображаем индексированное значение с типом F.t int на значение с типом F.t 'b, и возвращаем его как результат действий.
Да, у нас тут джва fmap'а -- сначала в целые числа, затем в тип результата, но для меня это приемлемо.

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

В чём ещё плюсы решения на окамле -- в том, что я явным образом выделил sequence, и именно эта функция решает, как будет обрабатываться массив операций ввода-вывода. Достаточно, чтобы монада удовлетворяла интерфейсу (типу модуля), содержащему return, bind, sequence_array, который я назвал IO_Sequence. Если наша IO допускает параллельное исполнение, то можно задать как последовательное, так и параллельное отображение любой структуры данных, являющейся функтором (то есть, действия в массиве могут выполняться по очереди либо могут начать выполнение одновременно и параллельно) -- для этого я всего лишь передаю разный модуль в функтор MapM -- например, вместо IO_Lwt могу явно передать IO_Lwt.Sequence_Parallel или IO_Lwt.Sequence_Sequential.
С тайпклассами этого не получится сделать легко и просто, так как там выбирается sequence, прибитая гвоздями к конкретному типу IO a, и для использования другой sequence потребуется передавать её явно, вдобавок к передаче IO-монады (у которой таки используются и return, и bind -- bind для получения результата sequence, return для возврата этого результата).

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


Кроме того, видел сегодня клёвую статью Modules Matter Most. Она тут упомянута потому, что в ней тоже необоснованно гонят на хаскель, но сама статья хорошая и правильная.
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 Jun. 27th, 2017 08:38 pm
Powered by Dreamwidth Studios