Как выглядит flatMap с двойной общей структурой данных?

У меня следующая (простая) структура данных:

struct Work<Input, Output> {
    let work: Input -> Output
}

Этот тип представляет работу, которая может занять Input и превратиться в желаемый Output. Я пытаюсь понять, соответствует ли эта структура данных некоторым функциональным концепциям, таким как функтор или монада.

Функтор

extension Work {
    func map<MoreOutput>(transform: Output -> MoreOutput) -> Work<Input, MoreOutput> {
        return Work<Input, MoreOutput> {
            return transform(self.work($0))
        }
    }
}

Насколько мне известно, это кажется правильным. Я могу написать функцию карты, которая может превращать Work<Input, Output> в Work<Input, MoreOutput>

Монада

Мне сложно придумать определение функции flatMap (или fold) для Work. Единственное, что я могу придумать, это следующее:

extension Work {
    func flatMap<MoreOutput>(transform: Work<Output, MoreOutput>) -> Work<Input, MoreOutput> {
        return Work<Input, MoreOutput> { input in
            return transform.work(self.work(input))
        }
    }
}

Если вы быстро посмотрите определение flatMap для Array, оно будет выглядеть так (упрощенно):

func flatMap(transform: (Element) -> T?) -> [T]

Это функция, аргументом которой является функция, которая преобразует Element в T и возвращает Array. Я не могу придумать способ абстрагировать это до типа Work.

В другой функциональной книге я нашел следующее общее определение flatMap (для объекта F типа хранения A):

func flatMap<B>(f: A -> F<B>) -> F<B>

которое, похоже, реализует flatMap, отличное от Array.

Может кто-нибудь объяснить мне эту разницу? И возможно ли вообще определить «правильную» flatMap функцию на Work? Или Work не удовлетворяет свойствам монады?

** Изменить

Спасибо phg за столько полезной информации. Я пробовал дать определение Profunctor:

Делаем Work a Profunctor:

extension Work {
    func diMap<A, B>(fa: A -> Input, fb: Output -> B) -> Work<A, B> {
        return Work<A, B> { arg in
            let input = fa(arg)
            let output = self.work(input)
            return fb(output)
        }
    }
}

Вам это кажется правильным?


swift flatmap functional-programming monads
person Robin van Dijke    schedule 15.01.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Этот:

func flatMap<B>(f: A -> F<B>) -> F<B>

это то, как вы хотите, чтобы flatMap выглядел; это обычная для монады операция связывания монады. Специализированная для функций по второму аргументу, вы получаете так называемую монаду чтения:

extension Work {
    func flatMap<MoreOutput>(g: Output -> Work<Input, MoreOutput>) -> Work<Input, MoreOutput> {
        // (Reader f) >>= g = Reader $ \x -> runReader (g (f x)) x
        return Work<Input, MoreOutput> {
            g(self.work($0)).work($0)
        }
    }
}

Примечание: я на самом деле не говорю на Swift, этот код был просто предположением - отсюда и включенный оригинал Haskell. Не стесняйтесь редактировать в исправленной версии.

Теперь к другому определению:

func flatMap(transform: (Element) -> T?) -> [T]

Я полагаю, T? означает что-то вроде «необязательный T» или «допускающий значение NULL T». Это не то, что мы обычно понимаем под монадической функцией, но это связано. Действительно, был вопрос о таком " обобщенные карты ". Ответ таков: если две монады совместимы, т.е. существует морфизм монад F<A> -> G<A>, сохраняющий монадическую структуру, имеет смысл определить

func wrappedFlatMap<B>(f: A -> F<B>) -> G<B>

что, вероятно, именно то, что здесь происходит для "типа опции" и типа списка, где морфизм логически просто

Just x ~> [x]
Nothing ~> []
person phipsgabler    schedule 15.01.2016
comment
О, и пока вы это делаете, вы можете сделать Work a профунктор! - person phipsgabler; 15.01.2016
comment
Отлично, много полезной информации! Отредактировал свой ответ, чтобы добавить мою первую попытку профунктора на Work. - person Robin van Dijke; 15.01.2016