Mонады в javascript

[aa_dav]

arseniiv в сообщении #1025453 писал(а):

И теория категорий их заимствовала?

Не я именно про языки программирования. Допускаю что уже и кроме Хаскеля есть таковые где оно уместно - но даже в гугле если гуглить "монады программирование" все ссылки будут со словом Хаскель. :) Всё таки как вы и говорили оно на стыке всего что в Хаскеле присутствует - как чистое ФП, строгая типизация, так вывод типов, так синтаксис со всеми применениями, бинарными функциями и прочая. Взять даже тот пример - монадические то функции он по сути ввёл.... но они строго привязаны к одной конкретной монаде, т.к. кончаются return SimpleMonad( x ). Т.е. получается, чтобы они стали универсальными, надо еще в них надо передавать "конструктор монады", от чего еще всё раздуется в коде. А в хаскеле как я понимаю просто автовывод сработает исходя из того в каком контексте монадическая функция встретится.
В итоге игра стремительно теряет свечи, чем дальше пытаешься построить целостный пример. :)

[arseniiv]

aa_dav в сообщении #1025524 писал(а):

бинарными функциями

? Если это про операции, так переопределение их есть много где, так же как и разная степень вывода типов и возможность указывать в интерфейсе метод класса (для return). Хотя и мало где всё разом, но время-то ещё есть!

aa_dav в сообщении #1025524 писал(а):

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

Не всегда do заканчивается return что-то.

[aa_dav]

Хм, пришла идея. Конструктор можно в сам bind и запихать.
Так что проапгрейдил пример из статьи до следующего:

Используется синтаксис Javascript

// 1-p functions

function getnull( x )
{
        return null;
};

function getzero( x )
{
        return 0;
};

function add7( x )
{
        return x + 7;
};

function sub4( x )
{
        return x - 4;
};

// Monad constructors

function EmptyMonad( value )
{
        this.value = value;
        this.bind = function( func )
        {
                res = func( this.value );
                return new EmptyMonad( res );
        };
};

function MaybeMonad( value )
{
        this.value = value;
        this.bind = function( func )
        {
                if ( this.value == null )
                        res = null;
                else
                        res = func( this.value );
                return new MaybeMonad( res );
        };      
};

// tests

WScript.Echo( "EmptyMonad" );
WScript.Echo( new EmptyMonad( 10 ).value );
WScript.Echo( new EmptyMonad( 10 ).bind( getzero ).value );
WScript.Echo( new EmptyMonad( 10 ).bind( getzero ).bind( add7 ).value );
WScript.Echo( new EmptyMonad( 10 ).bind( function ( x ) { return 2 * x } ).value );

WScript.Echo( "MaybeMonad" );
WScript.Echo( new MaybeMonad( 10 ).value );
WScript.Echo( new MaybeMonad( 10 ).bind( getnull ).value );
WScript.Echo( new MaybeMonad( 10 ).bind( getnull ).bind( add7 ).value );
WScript.Echo( new MaybeMonad( 10 ).bind( getnull ).bind( add7 ).bind( sub4 ).value );
 

Чем JavaScript еще хорош - под любой виндой скопировать текст в файл с расширением *.js и щёлкнуть по нему.
Если охота видеть вывод в консоли, запускать из консоли через команду cscript file.js

Такс, но это далеко как грица не всё...

-- 10.06.2015, 20:32 --

Лёгкий апгрейд:

Используется синтаксис Javascript

// 1-p functions

function getnull( x )
{
        return null;
};

function getzero( x )
{
        return 0;
};

function add7( x )
{
        return x + 7;
};

function sub4( x )
{
        return x - 4;
};

// Monad constructors

function EmptyMonad( value )
{
        this.value = value;
        this.bind = function( func )
        {
                res = func( this.value );
                return new EmptyMonad( res );
        };
};

function MaybeMonad( value )
{
        this.value = value;
        this.bind = function( func )
        {
                if ( this.value == null )
                        res = null;
                else
                        res = func( this.value );
                return new MaybeMonad( res );
        };      
};

// tests

function test1( name, monad )
{
        WScript.Echo( name + " = " + monad.value );
        monad = monad.bind( add7 );
        WScript.Echo( "add7 = " + monad.value );
        monad = monad.bind( sub4 );
        WScript.Echo( "sub4 = " + monad.value );
        monad = monad.bind( getnull );
        WScript.Echo( "getnull = " + monad.value );
        monad = monad.bind( getzero );
        WScript.Echo( "getzero = " + monad.value );
        monad = monad.bind( function ( x ) { return x + 3 } );
        WScript.Echo( "custom+3 = " + monad.value );
};

function test2( name, monad )
{
        WScript.Echo( name + " with initial value " + monad.value + " bulk calculations: " + 
                monad.bind( add7 ).bind( sub4 ).bind( getnull ).bind( getzero ).bind( function ( x ) { return x + 3 } ).value 
        );
};

test1( "EmptyMonad", new EmptyMonad( 10 ) );
test2( "EmptyMonad", new EmptyMonad( 10 ) );
test1( "MaybeMonad", new MaybeMonad( 10 ) );
test2( "MaybeMonad", new MaybeMonad( 10 ) );
 

[arseniiv]

aa_dav в сообщении #1025764 писал(а):

Хм, пришла идея. Конструктор можно в сам bind и запихать.

И, если правильно им потом пользоваться, получится, что возвращается m (m a). И никак это не превратить в m a, потому что join :: m (m a) -> m a как раз через bind и выражается (и наоборот), если его не определять вместе с — но в любом случае, они должны быть согласованы.

[aa_dav]

arseniiv в сообщении #1025772 писал(а):

И, если правильно им потом пользоваться

А вот можно пример что потом по идее должно хотеться этим правильно воспользоваться?
.value написать там где надо "поднять значение наверх" тут никто не запрещает, другой синтаксис и правила в общем то.

-- 10.06.2015, 20:51 --

P.S.

Ну и да, то что в самом начале топика топикастер имитировал do-нотацию "как то странно", тут и имитировать не надо - в джаваскрипте наоборот всё именно так и обстоит, никаких проблем написать:

Используется синтаксис Javascript

function getGrandFathers( man )
{
    var maybeMan = MaybeMonad( man );
    mother = maybeMan.bind( getMother );
    gf1 = mother.bind( getFather );
    father = maybeMan.bind( getFather );
    gf2 = father.binf( getFather );
    return { gf1, gf2 };
};
 

нет. Это здесь даже естественно. Это "перевранный" другой пример из другой статьи...

[arseniiv]

aa_dav в сообщении #1025775 писал(а):

А вот можно пример что потом по идее должно хотеться этим правильно воспользоваться?

Ну вот есть монада-список

Используется синтаксис Haskell

instance Monad [] where
  // с сохранением семантики упрощено относительно реального кода
  return :: a -> [a]
  return x = [x]
  // возвращаем список из указанной альтернативы
  (>>=) :: [a] -> (a -> [b]) -> [b]
  xs >>= f = concat (map f xs)
  // применяем ко всем альтернативам функцию, возвращающую список,
  // и соединяем их в один список

example n = do
  a <- [1..n]
  b <- [1..a]
  [(a, b), (b, a)]
// example 3 = [(1,1),(1,1),(2,1),(1,2),(2,2),(2,2),(3,1),(1,3),(3,2),(2,3),(3,3),(3,3)]

Эквивалентный код примера без do:

Используется синтаксис Haskell

example n =
  [1..n] >>= (\a ->
    [1..a] >>= (\b ->
      [(a, b), (b, a)]))

Напишете аналогичное с вашими «улучшениями»?

[aa_dav]

arseniiv в сообщении #1025786 писал(а):

Из неё нельзя вытащить «единственное» значение

Ну так просто её значение это собственно список (массив в терминах JavaScript).
Весь смысл в том что делает bind - как написано собственно в комментариях он возьмёт функцию, которая должна возвращать списки, применит ко всех значением я соединим в один список.
Тут я только в примерах честно говоря теряюсь, было m a, а стало [a], не очень понятно... я до такого не доходил...

[_Ivana]

Используется синтаксис Lisp

(defn return (x) (cons x nil))
(defn bind (l f) (concat (map f l)))

(defn example (n)
    (bind (list-from-to 1 n)
          (lambda (a) (bind (list-from-to 1 a)
                            (lambda (b) (cons (cons a b) (cons (cons b a) nil)))))))
(printLn (example 3))

((1 1) (1 1) (2 1) (1 2) (2 2) (2 2) (3 1) (1 3) (3 2) (2 3) (3 3) (3 3))

На лискрипте. Имхо, весь смысл в том, как трактуется bind применительно к данным типам.

[aa_dav]

Если предыдущий пост адресовался мне - то то, что код комбинирует списки это то понятно.
Мне непонятно где в коде хаскелля возникли и как монады (убивает например генератор [1..a], ведь если я (не)правильно понимаю Monad [] заставляет [] генерировать монаду списка, а что такое генератор списка от 1 и до монады мне вообще непонятно, всё, стоп машина мозговая) чтобы попытаться их воспроизвести в синтаксисе яваскрипта.

-- 10.06.2015, 22:48 --

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

[_Ivana]

aa_dav, пост скорее просто в качестве ответа arseniiv на его вопрос (хоть и не мне). Я сам не понимаю концепцию монад, да и функторов тоже, не говоря уже о тысяче разнообразных морфизмов, и хотел бы тоже приобщиться к знанию ,почитать умных людей, разобраться. Тем более что это первая интересная мне тема на форуме за несколько месяцев.

ЗЫ а вы все усложняете. m a и [a] это в контексте монады списка одно и то же. И генерирует монаду, насколько я знаю, реализация для данного контекста двух функций: bind и return. Конечно в каждой монаде они будут значить свое, в монаде списка мы уже написали что именно. В других монадах - другое. Более того, даже монаду списка можно не единственным образом определить, как и функтор - это только наши условности, лишь бы выполнялись законы монад и функторов. И никаких тут генераторов списка от 1 до монад нет, просто обычные генераторы списка от числа до числа - смотрите мой код на лискрипте, просто к этим сгенерированным спискам применяется функция.

[arseniiv]

aa_dav в сообщении #1025794 писал(а):

Весь смысл в том что делает bind - как написано собственно в комментариях он возьмёт функцию, которая должна возвращать списки, применит ко всех значением я соединим в один список.
Тут я только в примерах честно говоря теряюсь, было m a, а стало [a], не очень понятно... я до такого не доходил...

Разумеется, тут смысл в bind, т. к. в моём примере только он и в ходу. А вот m a здесь это как раз и есть [a], что можно записать более формально (язык поддерживает) как [] a — в других языках это могло бы писаться List a, m = List. Видели параметризованные типы (а по-русски — generics) — вот монадами как раз могут быть только типы от одного параметра.

В хаскеле это, кстати, выразимо с помощью kinds — обычные типы имеют кинд *, а тип с параметром кинда k1, в результате применения которого получается тип кинда k2, имеет кинд k1 -> k2 — кинды для типов то же, что типы для значений. В некоторых языках идут дальше и определяют обобщение для всех натуральных, но хаскель ограничивается тремя уровнями. Так вот, с помощью некоторого расширения GHC можно было бы заголовок описания класса монады записать как class Monad (m :: * -> *), явно указывая кинд, хотя обычно компилятор сам догадывается, потому что в функциях встречается только m a.

[m..n], как уже сказал _Ivana, это просто выражение типа [a], если m, n :: Enum a => a, т. е. типа, значения которого можно один за другим перечислять (а также через заданный шаг, для чего есть сахар [m1,m2..n] и ещё два сахара [m..] и [m1,m2..] для бесконечных списков. Всё это синонимы вызовов некоторых методов Enum, хотя тут для нас важно, что Enum Int, и тип упомянутых выражений, соответственно, будет [Int].

Ещё вижу кое-какую путаницу в основах, так что попробую их перечислить.

aa_dav в сообщении #1025802 писал(а):

ведь если я (не)правильно понимаю Monad [] заставляет [] генерировать монаду списка, а что такое генератор списка от 1 и до монады мне вообще непонятно, всё, стоп машина мозговая

Monad, как и любой класс в хаскеле, скорее, аналогичен интерфейсам языков с ООП — он описывает протокол, которому может удовлетворять какой-то набор типов (в частном случае, который у нас здесь, и который только и был в стандарте Haskell98, один тип; недавно в GHC появилось расширение, позволяющее нульарные классы, которым тоже находится применение). Чтобы указать, как и какой ещё набор удовлетворяет классу, пишется инстанс — в данном случае Monad [] с определениями методов (не обязательно всех, т. к. могут быть определения по умолчанию, что сближает классы не просто с интерфейсами из ООП, а с примесями (mixins); так себя ведут интерфейсы Ceylon, например).

Имея на руках класс и набор инстансов из подключенных модулей, компилятор может заменить метод класса типа Monad m => t m конкретным методом типа t [] или там t Maybe {здесь, кстати, t не просто сокращение какого-то неизвестного выражения, но ещё и :: (* -> *) -> *, но это уже можно счесть издевательством с моей стороны, так что скобки фигурные, и могли бы и не читать их} — во время ли выполнения или, при удаче (если программист достаточное количество конкретных типов прописал в других местах, обычно описывающих конкретные вещи), на этапе компиляции. Так что Monad [] не «заставляет [] генерировать монаду списка», тело инстанса Monad [] описывает, как понимать список как монаду.

Некоторые люди считают всё-таки [a] смущающим вариантом List a (хотя я не соглашусь — если все смущающие совпадения удалить, получится непривычный мне вариант языка, так что невзвешенная оценка вполне уместна). В их варианте было бы

Используется синтаксис Haskell

instance Monad List
  return :: a -> List a
  (>>=) :: List a -> (a -> List b) -> List b

и не было бы путаницы скобок с уровня значений со скобками с уровня типов (или нашлось бы что-то ещё не устраивающее).

А, и ещё: штучки вида Class params или (C1 ps1, C2 ps2, …) называются ограничениями (constraints) и могут пониматься как истинностные значения, знания о которых к нам приходят из и только из инстансов — либо в виде конкретных, в терминологии Пролога, фактов C ps, либо в виде более изощрённых выводимостей (C1 ps1, C2 ps2, …) => Cn psn, позволяющих в лучшем случае генерировать инстансы автоматически (а в худшем позволяющих компилятору завернуть ваш код, потому что это галиматья, и даже с расширениями иногда всё равно галиматья ). Соответственно, тип Constraints => t состоит из тех же значений, что и t, но только тех, для которых верны Constraints. (КО приглашён на случай, если я переоценил чьи-то знания.)

-- Чт июн 11, 2015 00:34:47 --

(Надеюсь, это что-то кому-то пояснило, а то я не уверен, что методически корректен.)

[aa_dav]

Такс, да, догнал в чём тут подвох. Параметры то это параметры, вон оно чё Михалыч, это не эквивалентно тому что я писал с a = monad.bind... a это не монада же получается, а её параметр. Вон оно чё. Хитро получается. Дейсвительно так сразу и не соображу как это разумно перевести в яваскрипт. Надо всё в лямбды заворачивать до потрохов... И bind неоткуда и некуда приткнуть.
Да, тут имитация .bind лажает на корню.
Ладно, на сегодня хватит. :)

-- 10.06.2015, 23:50 --

arseniiv в сообщении #1025833 писал(а):

Некоторые люди считают всё-таки [a] смущающим вариантом List a

Я слаб в хаскелле, поэтому любая непривычно встреченная закорючка сразу же обрубает наглухо понимание.
В принципе достаточно было здесь только это и сказать - что [a] это извращенная форма List a.
И что генератор - тоже функция. :)

[arseniiv]

Генератор как раз не функция, а выражение. Функции — это четыре сестрицы enumFrom[Then][To], которые в Enum и определяются (и [m..n] ≡ enumFromTo m n). Не хотел их явно называть, чтобы не запутывать ещё дальше. Так вот, в синтаксисе do слева от <- стоит переменная или другой шаблон (ага!) типа a, а справа — выражение типа m a, либо всю строку занимает выражение типа m a, либо там стоит let v = expr, где выражение уже типа a как и переменная — это чтобы не писать v <- return expr попусту.

aa_dav в сообщении #1025837 писал(а):

Ладно, на сегодня хватит. :)

Короче, непрочь буду увидеть, что как-нибудь у вас получится со списками. Просто, видимо, в следующем заходе вернитесь к «не улучшенной» версии из статьи про Python.

-- Чт июн 11, 2015 01:26:22 --

(Оффтоп)

arseniiv в сообщении #1025858 писал(а):

непрочь буду увидеть

(И коварно предложу ещё какую монаду пострашнее! )

[aa_dav]

Аааааа... Мда.... Получилось в рамках "улучшенного" подхода, когда глубже проняло в чём подвох.
АДСКИ, АДСКИ вышло. :)))))

Если вкратце, то:

Используется синтаксис Javascript

function genarray( high )
{
        low = 1;
        var res = [];
        var i;
        for ( i = low; i <= high; i++ )
                res.push( i );
        return res;
};

function ListMonad( value )
{
        this.value = value;
        this.bind = function( func )
        {
                var res = [];
                var i, j;
                for ( i = 0; i < value.length; i++ )
                {
                        var suba = func( value[ i ] );
                        for ( j = 0; j < suba.length; j++ )
                        {
                                res.push( suba[ j ] );
                        };
                };
                return new ListMonad( res );
        };      
};

function example2( n )
{
        return new ListMonad( genarray( n ) ).bind( function ( a ) { return new ListMonad( genarray( a ) ).bind( function ( b ) { return [[a,b], [b,a]] } ).value } ).value;
};

x = example2( 3 );
WScript.Echo( "x: " + x );
for ( i = 0; i < x.length; i++ )
{
        WScript.Echo( "x[" + i + "] = " + x[i] );
};
 

вывод:

x[0] = 1,1
x[1] = 1,1
x[2] = 2,1
x[3] = 1,2
x[4] = 2,2
x[5] = 2,2
x[6] = 3,1
x[7] = 1,3
x[8] = 3,2
x[9] = 2,3
x[10] = 3,3
x[11] = 3,3

Но это конечно ни в борщ ни в красную армию. Смысла, конечно, никакого...

[arseniiv]

(Пока писал, вы уже выложили свой вариант, но оставлю как reference implementation. )

Эх, если бы в JS были бы макросы, была бы возможность и что-то do-подобное устроить. А так оно будет громоздкущим:

Используется синтаксис Javascript

// все имена условны
// range(1, n) = [1, …, n]
// предполагается, что bind и не используемый здесь return добавили в Array.prototype
function example(n) {
  return range(1, n).bind(function(a) {
    return range(1, a).bind(function(b) {
      return [[a, b], [b, a]];
    }
  }
}