Как соотносятся бесплатная монада и реактивные расширения?

14

Я пришел из C #, где LINQ эволюционировал в Rx.NET, но всегда интересовался FP. После некоторого введения в монады и некоторых побочных проектов в F # я был готов попытаться перейти на следующий уровень.

Теперь, после нескольких разговоров о бесплатной монаде от людей из Scala и нескольких рецензий на Haskell или F #, я обнаружил, что грамматики с интерпретаторами для понимания очень похожи на IObservableцепочки.

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

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

MLProgrammer-CiM
источник
2
Вот интересный способ думать о проблеме ... FRP можно рассматривать как монаду, даже если она обычно не формулируется таким образом . Большинство (хотя и не все) монады изоморфны свободной монаде . Поскольку Contединственная монада, которую я видел, предполагала, что не может быть выражена через свободную монаду, можно предположить, что FRP может быть. Как и почти все остальное .
Жюль
2
По словам Эрика Мейера, разработчика LINQ и Rx.NET, IObservableон является примером монады продолжения.
Йорг Миттаг
1
У меня нет времени, чтобы проработать детали прямо сейчас, но я предполагаю, что и расширения RX, и подход свободной монады достигают очень похожих целей, но могут иметь несколько иные структуры. Вполне возможно, что RX Observables являются самими монадами, и тогда вы можете сопоставить вычисление свободной монады с вычислением, используя observables - это очень приблизительно означает, что означает "free" в "free monad". Или, может быть, отношения не такие прямые, и вы просто понимаете, как они используются для подобных целей.
Тихон Джелвис

Ответы:

6

Монады

Монада состоит из

  • Endofunctor . В нашем мире разработки программного обеспечения мы можем сказать, что это соответствует типу данных с одним параметром неограниченного типа. В C # это будет что-то вроде:

    class M<T> { ... }
    
  • Две операции, определенные для этого типа данных:

    • return/ pureпринимает «чистое» значение (т. е. Tзначение) и «оборачивает» его в монаду (т. е. производит M<T>значение). Поскольку returnэто зарезервированное ключевое слово в C #, pureтеперь я буду ссылаться на эту операцию. В C # pureбудет метод с подписью, как:

      M<T> pure(T v);
      
    • bind/ flatmapпринимает монадическое значение ( M<A>) и функцию f. fпринимает чистое значение и возвращает монадическое значение ( M<B>). Из них bindвыдает новое монадическое значение ( M<B>). bindимеет следующую подпись C #:

      M<B> bind(M<A> mv, Func<A, M<B>> f);
      

Кроме того, чтобы быть монадой, pureи bindобязаны соблюдать три монадических закона.

Теперь одним из способов моделирования монад в C # было бы создание интерфейса:

interface Monad<M> {
  M<T> pure(T v);
  M<B> bind(M<A> mv, Func<A, M<B>> f);
}

(Примечание. Для краткости и выразительности я буду использовать некоторые возможности кода в этом ответе.)

Теперь мы можем реализовать монады для конкретных типов данных путем реализации конкретных реализаций Monad<M>. Например, мы могли бы реализовать следующую монаду для IEnumerable:

class IEnumerableM implements Monad<IEnumerable> {
  IEnumerable<T> pure(T v) {
    return (new List<T>(){v}).AsReadOnly();
  }

  IEnumerable<B> bind(IEnumerable<A> mv, Func<A, IEnumerable<B>> f) {
    ;; equivalent to mv.SelectMany(f)
    return (from a in mv
            from b in f(a)
            select b);
  }
}

(Я целенаправленно использую синтаксис LINQ, чтобы вызвать связь между синтаксисом LINQ и монадами. Но учтите, что мы могли бы заменить запрос LINQ вызовом SelectMany.)

Теперь мы можем определить монаду для IObservable? Казалось бы, так:

class IObservableM implements Monad<IObservable> {
  IObservable<T> pure(T v){
    Observable.Return(v);
  }

  IObservable<B> bind(IObservable<A> mv, Func<A, IObservable<B>> f){
    mv.SelectMany(f);
  }
}

Чтобы убедиться, что у нас есть монада, нам нужно доказать законы монады. Это может быть нетривиально (и я не достаточно знаком с Rx.NET, чтобы знать, можно ли их доказать даже из одной спецификации), но это многообещающее начало. Чтобы облегчить оставшуюся часть этого обсуждения, давайте просто предположим, что в этом случае действуют законы монады.

Бесплатные монады

Не существует единственной «свободной монады». Скорее, свободные монады - это класс монад, которые построены из функторов. То есть, учитывая функтор F, мы можем автоматически получить монаду F(то есть свободную монаду F).

ФУНКТОРЫ

Как и монады, функторы могут быть определены следующими тремя элементами:

  • Тип данных, параметризованный над одной переменной неограниченного типа.
  • Две операции:

    • pureоборачивает чистое значение в функтор. Это аналогично pureдля монады. Фактически, для функторов, которые также являются монадами, они должны быть идентичными.
    • fmapсопоставляет значения на входе с новыми значениями на выходе с помощью данной функции. Это подпись:

      F<B> fmap(Func<A, B> f, F<A> fv)
      

Как и монады, функторы обязаны подчиняться законам функторов.

Подобно монадам, мы можем моделировать функторы через следующий интерфейс:

interface Functor<F> {
  F<T> pure(T v);
  F<B> fmap(Func<A, B> f, F<A> fv);
}

Теперь, поскольку монады являются подклассом функторов, мы могли бы также Monadнемного изменить рефакторинг :

interface Monad<M> extends Functor<M> {
  M<T> join(M<M<T>> mmv) {
    Func<T, T> identity = (x => x);
    return mmv.bind(x => x); // identity function
  }

  M<B> bind(M<A> mv, Func<A, M<B>> f) {
    join(fmap(f, mv));
  }
}

Здесь я добавил дополнительный метод joinи предоставил реализации по умолчанию для обоих joinи bind. Обратите внимание, однако, что это круговые определения. Таким образом, вам придется переопределить хотя бы один или другой. Также обратите внимание, что pureтеперь наследуется от Functor.

IObservable и бесплатные монады

Теперь, поскольку мы определили монаду для IObservableи поскольку монады являются подклассом функторов, из этого следует, что мы должны быть в состоянии определить экземпляр функтора для IObservable. Вот одно определение:

class IObservableF implements Functor<IObservable> {
  IObservable<T> pure(T v) {
    return Observable.Return(v);
  }

  IObservable<B> fmap(Func<A, B> f, IObservable<A> fv){
    return fv.Select(f);
  }
}

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

Натан Дэвис
источник
Проницательное понимание теории категорий! Я был о чем-то, что говорило не о том, как они создаются, а о различиях при построении функциональной архитектуры и создании эффектов моделирования с любым из них. FreeMonad можно использовать для создания DSL для операций с расширенными функциями, тогда как IObservables больше ориентированы на дискретные значения с течением времени.
MLProgrammer-CiM
1
@ MLProgrammer-CiM, я посмотрю, смогу ли я рассказать об этом в ближайшие пару дней.
Натан Дэвис,
Мне бы очень понравился практический пример свободных монад
l --''''''--------- '' '' '' '' '' ''