Монады для Go-программистов

Монады используются для компоновки функции (function composition) и избавления от связанного с этим утомительного однообразия. После семи лет программирования на Go необходимость повторять if err != nil превращается в рутину. Каждый раз, когда я пишу эту строку, я благодарю Gopher’ов за читабельный язык с прекрасным инструментарием, но в то же время проклинаю за то, что чувствую себя наказанным Бартом Симпсоном.

Подозреваю, что это чувство разделяют многие, но

if err != nil {
    log.Printf("This should still be interesting to a Go programmer " +
        "considering using a functional language, despite %v.", err)
}

Монады нужны не только для того, чтобы спрятать от нас обработки ошибок, но и для списковых включений, и для согласованности, и для других задач.

Не читайте это

Эрик Мейер (Erik Meijer) в своей статье Introduction to Functional Programming Course on Edx просит больше не писать о монадах, потому что о них и так уже очень много сказано.

Помимо чтения этой статьи я рекомендую посмотреть серию видео Бартоша Милевски о теории категорий, которая завершается выступлением с лучшим объяснением монад, какое мне только встречалось.

Дальше не читайте!

Функторы

Ну ладно (вздох)… Только помните: я вас предупреждал.
До монад нужно разобраться с функторами. Функтор — это надкласс (superclass) монады, т. е. все монады — это функторы. Я буду использовать функторы в дальнейшем объяснении сути монад, так что не пропускайте этот раздел.

Функтор можно считать контейнером, содержащим один тип элементов.

Например:

• Слайс с элементами типа T: []T — контейнер, элементы в котором упорядочены в виде списка.
• Дерево type Node<T> struct { Value T; Children: []Node<T> } — контейнер, элементы которого упорядочены в виде дерева.
• Канал <-chan T — контейнер и похож на трубу, по которой течёт вода.
• Указатель *T — контейнер, который может быть пустым либо содержать один элемент.
• Функция func(A) T — контейнер наподобие сейфа, который придётся открыть ключом, чтобы увидеть хранящийся в нём элемент.
• Многочисленные возвращаемые значения func() (T, error) — контейнер, который, возможно, содержит один элемент. Ошибку можно рассматривать как часть контейнера. Здесь и далее мы будем называть (T, error) кортежем.

Программистам, владеющим не Go, а другими языками: в Go нет алгебраических типов данных или объединённых типов (union types). Это значит, что вместо возврата функцией значения или ошибки здесь возвращается значение и ошибка, и одно из них обычно — nil. Иногда мы нарушаем соглашение и возвращаем значение и ошибку, оба не nil, чтобы просто попытаться запутать друг друга. Или поразвлечься.

Самый популярный способ получить объединённые типы в Go: нужно иметь интерфейс (абстрактный класс) и переключатель типа (type switch) в типе интерфейса.

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

func fmap(f func(A) B, aContainerOfA Container<A>) Container<B>

Использование функции map в качестве слайса — классический пример, который вы могли встречать в mapreduce в Hadoop, Python, Ruby и почти любом другом языке:

func fmap(f func(A) B, as []A) []B {
    bs := make([]b, len(as))
    for i, a := range as {
        bs[i] = f(a)
    }
    return bs
}

Мы также можем реализовать fmap для дерева:

func fmap(f func(A) B, atree Node<A>) Node<B> {
    btree := Node<B>{
        Value: f(atree.Value),
        Children: make([]Node<B>, len(atree.Children)),
    }
    for i, c := range atree.Children {
        btree.Children[i] = fmap(f, c)
    }
    return btree
}

Или для канала:

func fmap(f func(A) B, in <-chan A) <-chan B {
    out := make(chan B, cap(in))
    go func() {
        for a := range in {
            b := f(a)
            out <- b
        }
        close(out)
    }()
    return out
}

Или для указателя:

func fmap(f func(A) B, a *A) *B {
    if a == nil {
        return nil
    }
    b := f(*a)
    return &b
}

Или для функции:

func fmap(f func(A) B, g func(C) A) func(C) B {
    return func(c C) B {
        a := g(c)
        return f(a)
    }
}

Или для функции, возвращающей ошибку:

func fmap(f func(A) B, g func() (*A, error)) func() (*B, error) {
    return func() (*B, error) {
        a, err := g()
        if err != nil {
            return nil, err
        }
        b := f(*a)
        return &b, nil
    }
}

Все эти контейнеры с соответствующими реализациями fmap — функторы.

Компоновка функций (Function Composition)

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

Монада — это просто «украшенный» тип. Хм, полагаю, понятнее не стало, слишком абстрактно. Это типичная проблема всех объяснений сути монад. Это как попытка растолковать, что такое побочный эффект: описание будет слишком общим. Так что давайте лучше разберёмся с причиной абстрактности монады. Причина в том, чтобы компоновать функции, которые возвращают эти украшенные типы.

Начнём с обычной компоновки функций, без украшенных типов. В этом примере мы скомпонуем функции f и g и вернём функцию, берущую входные данные, которые ожидаются f, и возвращающую выходные данные из g:

func compose(f func(A) B, g func(B) C) func(A) C {
    return func(a A) C {
        b := f(a)
        c := g(b)
        return c
    }
}

Очевидно, что это будет работать только в том случае, если результирующий тип f соответствует входному типу g.

Другая версия: компоновка функций, возвращающих ошибки.

func compose(
    f func(*A) (*B, error), 
    g func(*B) (*C, error),
) func(*A) (*C, error) {
    return func(a *A) (*C, error) {
        b, err := f(a)
        if err != nil {
            return nil, err
        }
        c, err := g(b)
        return c, err
    }
}

Теперь попробуем абстрагировать эту ошибку в виде украшения (embellishment) M и посмотреть, что останется:

func compose(f func(A) M<B>, g func(B) M<C>) func(A) M<C> {
    return func(a A) M<C> {
        mb := f(a)
        // ...
        return mc
    }
}

Нам нужно вернуть функцию, берущую A в качестве входного параметра, так что начнём с объявления возвращающей функции. Раз у нас есть A, мы можем вызвать f и получить значение mb типа M<b>, но что дальше?

Мы не достигли цели, поскольку получилось слишком абстрактно. Я хочу сказать, что у нас есть mb, только что с ним делать?

Когда мы знали, что это ошибка, то могли проверить её, а теперь не можем, потому что она слишком абстрактна.

Но… если мы знаем, что наше украшение M — также функтор, то можем применить к нему fmap:

type fmap = func(func(A) B, M<A>) M<B>

Функция g, к которой мы хотим применить fmap, не возвращает простой тип вроде C, она возвращает M<C>. К счастью, для fmap это не проблема, но зато меняется сигнатура типа:

type fmap = func(func(B) M<C>, M<B>) M<M<C>>

Теперь у нас есть значение mmc типа M<M<C>>:

func compose(f func(A) M<B>, g func(B) M<C>) func(A) M<C> {
    return func(a A) M<C> {
        mb := f(a)
        mmc := fmap(g, mb)
        // ...
        return mc
    }
}

Мы хотим перейти от M<M<C>> к M<C>.

Для этого нужно, чтобы наше украшение M не просто было функтором, а имело и другое свойство. Это свойство — функция join, которая определена для каждой монады, как fmap была определена для каждого функтора.

type join = func(M<M<C>>) M<C>

Теперь мы можем написать:

func compose(f func(A) M<B>, g func(B) M<C>) func(A) M<C> {
    return func(a A) M<C> {
        mb := f(a)
        mmc := fmap(g, mb)
        mc := join(mmc)
        return mc
    }
}

Это означает, что если при украшении определены fmap и join, то мы можем скомпоновать две функции, возвращающие украшенные типы. Иными словами, необходимо определить эти две функции, чтобы тип был монадой.

Join

Монады — это функторы, так что нам не нужно опять определять для них fmap. Нужно определить лишь join.

type join = func(M<M<C>>) M<C>

Теперь определим join:

• для списков, что позволит создать списковые выражения (list comprehensions);
• для ошибок, что позволит обрабатывать монадные ошибки (monadic error);
• и для каналов, что позволит создать согласованный конвейер (concurrency pipeline).

Списковые выражения

Простейший способ начать — применить join к слайсам. Эта функция просто конкатенирует все слайсы.

func join(ss [][]T) []T {
    s := []T{}
    for i := range ss {
        s = append(s, ss[i]...)
    }
    return s
}

Давайте посмотрим, зачем нам снова понадобилась join, но в этот раз сосредоточимся на слайсах. Вот функция compose для них:

func compose(f func(A) []B, g func(B) []C) func(A) []C {
    return func(a A) []C {
        bs := f(a)
        css := fmap(g, bs)
        cs := join(css)
        return cs
    }
}

Если передать a в f, то получим bs типа []B.

Теперь можем применить fmap к []B с g, что даст нам значение типа [][]C, а не []C:

func fmap(g func(B) []C, bs []B) [][]C {
    css := make([][]C, len(bs))
    for i, b := range bs {
        css[i] = g(b)
    }
    return css
}

Вот для чего нам нужна join. Мы переходим от css к cs, или от [][]C к []C.

Давайте рассмотрим более конкретный пример.

Если мы заменяем типы:

• A на int,
• B на int64,
• C на string.

Тогда наша функция становится:

func compose(f func(int) []int64, g func(int64) []string) 
    func(int) []string
func fmap(g func(int64) []string, bs []int64) [][]string
func join(css [][]string) []string

Теперь можем использовать их в нашем примере:

func upto(n int) []int64 { 
    nums := make([]int64, n)
    for i := range nums {
        nums[i] = int64(i+1)
    }
    return nums
}

func pair(x int64) []string {
    return []string{strconv.FormatInt(x, 10), strconv.FormatInt(-1*x, 10)}
}

c := compose(upto, pair)
c(3)
// "1","-1","2","-2","3","-3"

Получается слайс нашей первой монады.

Любопытно, что именно так работают списковые выражения в Haskell:

[ y | x <- [1..3], y <- [show x, show (-1 * x)] ]

Но вы могли узнать их на примере Python:

def pair (x):
  return [str(x), str(-1*x)]

[y for x in range(1,4) for y in pair(x) ]

Обработка монадных ошибок (Monadic Error)

Мы также можем определить join для функций, возвращающих значение и ошибку. Для этого сначала нужно опять вернуться к функции fmap из-за некоторой идиосинкразии в Go:

type fmap = func(f func(B) C, g func(A) (B, error)) func(A) (C, error)

Мы знаем, что наша функция компоновки собирается вызвать fmap с функцией f, которая тоже возвращает ошибку. В результате сигнатура fmap выглядит так:

type fmap = func(
    f func(B) (C, error), 
    g func(A) (B, error),
) func(A) ((C, error), error)

К сожалению, кортежи в Go не относятся к объектам первого уровня, поэтому мы не можем просто написать:

((C, error), error)

Есть несколько путей обхода этого затруднения. Я предпочитаю функцию, потому что функции, которые возвращают кортежи, — это объекты первого уровня:

(func() (C, error), error)

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

func fmap(
    f func(B) (C, error), 
    g func(A) (B, error),
) func(A) (func() (C, error), error) {
    return func(a A) (func() (C, error), error) {
        b, err := g(a)
        if err != nil {
            return nil, err
        }
        c, err := f(b)
        return func() (C, error) {
            return c, err
        }, nil
    }
}

Это возвращает нас к основному пункту: функции join применительно к (func() (C, error), error). Решение простое и выполняет для нас одну из проверок ошибки.

func join(f func() (C, error), err error) (C, error) {
    if err != nil {
        return nil, err
    }
    return f()
}

Теперь можем использовать функцию compose, поскольку уже определили join и fmap:

func unmarshal(data []byte) (s string, err error) {
    err = json.Unmarshal(data, &s)
    return
}

getnum := compose(
    unmarshal, 
    strconv.Atoi,
)
getnum(`"1"`)
// 1, nil

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

Вот ещё один пример, когда я чувствую себя Бартом Симпсоном:

func upgradeUser(endpoint, username string) error {
    getEndpoint := fmt.Sprintf("%s/oldusers/%s", endpoint, username)
    postEndpoint := fmt.Sprintf("%s/newusers/%s", endpoint, username)

    req, err := http.Get(genEndpoint)
    if err != nil {
        return err
    }
    data, err := ioutil.ReadAll(req.Body)
    if err != nil {
        return err
    }
    olduser, err := user.NewFromJson(data)
    if err != nil {
        return err
    }
    newuser, err := user.NewUserFromUser(olduser),
    if err != nil {
        return err
    }
    buf, err := json.Marshal(newuser)
    if err != nil {
        return err
    }
    _, err = http.Post(
        postEndpoint, 
        "application/json", 
        bytes.NewBuffer(buf),
    )
    return err
}

Технически compose может взять в качестве параметров более двух функций. Поэтому соберём все вышеупомянутые функции в один вызов и перепишем наш пример:

func upgradeUser(endpoint, username string) error {
    getEndpoint := fmt.Sprintf("%s/oldusers/%s", endpoint, username)
    postEndpoint := fmt.Sprintf("%s/newusers/%s", endpoint, username)

    _, err := compose(
        http.Get,
        func(req *http.Response) ([]byte, error) {
            return ioutil.ReadAll(req.Body)
        },
        newUserFromJson,
        newUserFromUser,
        json.Marshal,
        func(buf []byte) (*http.Response, error) {
            return http.Post(
                postEndpoint,
                "application/json",
                bytes.NewBuffer(buf),
            )
        },
    )(getEndpoint)
    return err
}

Существует много других монад. Представьте две функции, возвращающие один и тот же тип украшения, которые вы хотите скомпоновать. Разберём ещё один пример.

Согласованные конвейеры (Concurrent Pipelines)

Можно определить join для каналов.

func join(in <-chan <-chan T) <-chan T {
    out := make(chan T)
    go func() {
        wait := sync.WaitGroup{}
        for c := range in {
            wait.Add(1)
            go func(inner <-chan T) {
                for t := range inner {
                    out <- t
                }
                wait.Done()
            }(c)
        }
        wait.Wait()
        close(out)
    }()
    return out
}

Здесь у нас канал in, который снабжает нас каналами типа T. Сначала создадим канал out, запустим горутину для обслуживания канала, а затем вернём её. Внутри горутины запустим новые горутины для каждого из каналов, читающих из in. Эти горутины шлют в out свои входящие события, объединяя входные данные в один поток. Наконец, с помощью группы ожидания (wait group) удостоверимся в закрытии канала out, получив все входные данные.

Иными словами, мы читаем все каналы T из in и передаём их в канал out.

Для программистов не на Go: мне нужно передать c в качестве параметра во внутреннюю горутину, потому что c — единственная переменная, берущая значение каждого элемента в канале. Это значит, что если вместо создания копии значения посредством передачи его в качестве параметра мы просто используем его внутри замыкания, то, вероятно, сможем читать только из самого свежего канала. Это распространённая среди Go-программистов ошибка.

Мы можем определить функцию compose применительно к функции, возвращающей каналы.

func compose(f func(A) <-chan B, g func(B) <-chan C) func(A) <-chan C {
    return func(a A) <-chan C {
        chanOfB := f(a)
        return join(fmap(g, chanOfB))
    }
}

А из-за способа реализации join мы получаем согласованность почти даром.

func toChan(lines []string) <-chan string {
    c := make(chan string)
    go func() {
        for _, line := range lines {
            c <- line
        }
        close(c)
    }()
    return c
}

func wordsize(line string) <-chan int {
    removePunc := strings.NewReplacer(
        ",", "", 
        "'", "",
        "!", "", 
        ".", "", 
        "(", "", 
        ")", "", 
        ":", "",
    )
    c := make(chan int)
    go func() {
        words := strings.Split(line, " ")
        for _, word := range words {
            c <- len(removePunc.Replace(word))
        }
        close(c)
    }()
    return c
}

sizes := compose(
    toChan([]string{
        "Bart: Eat my monads!",
        "Monads: I don't think that's a very good idea.",
        "Lisa: If anyone wants monads, I'll be in my room.",
        "Homer: Mmm monads",
        "Maggie: (Pacifier Suck)",
    }), 
    wordsize,
)
total := 0
for _, size := range sizes {
    if size == 6 {
        total += 1
    }
}
// total == 6

Меньше жестикуляции

Это объяснение монад сделано практически на пальцах, и, чтобы воспринималось легче, я намеренно опустил многие вещи. Но есть ещё кое-что, о чём я хочу рассказать.

Технически наша функция компоновки, определённая в предыдущей главе, называется Kleisli Arrow.

type kleisliArrow = func(func(A) M<B>, func(B) M<C>) func(A) M<C>

Когда люди говорят о монадах, они редко упоминают Kleisli Arrow, а для меня это стало ключом к пониманию сути монад. Если повезёт, то вам будут объяснять суть с помощью fmap и join, но если вы невезучие, как я, то вам объяснят с помощью функции bind.

type bind = func(M<B>, func(B) M<C>) M<C>

Почему?

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

Повторим нашу реализацию функции compose:

func compose(f func(A) M<B>, g func(B) M<C>) func(A) M<C> {
    return func(a A) M<C> {
        mb := f(a)
        mmc := fmap(g, mb)
        mc := join(mmc)
        return mc
    }
}

Если бы была реализована функция bind, то мы могли бы просто вызвать её вместо fmap и join.

func compose(f func(A) M<B>, g func(B) M<C>) func(A) M<C> {
    return func(a A) M<C> {
        mb := f(a)
        mc := bind(mb, g)
        return mc
    }
}

Это означает, что bind(mb, g) = join(fmap(g, mb)).

Роль функции bind для списков будут выполнять в зависимости от языка concatMap или flatMap.

func concatMap([]A, func(A) []B) []B

Внимательный взгляд

Я обнаружил, что в Go для меня стало стираться различие между bind и Kleisli Arrow. Go возвращает ошибку в кортеже, но кортеж — не объект первого уровня. Например, этот код не будет скомпилирован, потому что вы не можете посредством инлайнинга передавать результаты f в g:

func f() (int, error) {
    return 1, nil
}

func g(i int, err error, j int) int {
    if err != nil {
        return 0
    }
    return i + j
}

func main() {
    i := g(f(), 1)
    println(i)
}

Придётся написать так:

func main() {
    i, err := f()
    j := g(i, err, 1)
    println(j)
}

Или сделать так, чтобы g принимал функцию в качестве входных данных, потому что функции – это объекты первого уровня.

func f() (int, error) {
    return 1, nil
}

func g(ff func() (int, error), j int) int {
    i, err := ff()
    if err != nil {
        return 0
    }
    return i + j
}

func main() {
    i := g(f, 1)
    println(i)
}

Но это означает, что нашу функцию bind:

type bind = func(M<B>, func(B) M<C>) M<C>

определённую для ошибок:

type bind = func(b B, err error, g func(B) (C, error)) (C, error)

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

type bind = func(f func() (B, error), g func(B) (C, error)) (C, error)

Если присмотреться внимательно, то можно увидеть, что наш возвращаемый кортеж — тоже функция:

type bind = func(f func() (B, error), g func(B) (C, error)) func() (C, error)

И если присмотреться ещё раз, то окажется, что это наша функция compose, в которой f просто получает нулевые параметры:

type compose = func(f func(A) (B, error), g func(B) (C, error)) func(A) (C, error)

Тадам! Мы получили свою Kleisli Arrow, просто несколько раз внимательно присмотревшись.

type compose = func(f func(A) M<B>, g func(B) M<C>) func(A) M<C>

Заключение

Монады с помощью украшенных типов скрывают от нас рутинную логику компоновки функций, чтобы мы могли чувствовать себя не наказанным Бартом Симпсоном, а катающимся на скейте и метко кидающим мячик.

Если хотите попробовать в Go монады и другие концепции функционального программирования, можете делать это с помощью моего генератора кода GoDerive.

Предупреждение. Одна из ключевых концепций функционального программирования — неизменяемость. Это не только упрощает работу программ, но и позволяет оптимизировать компиляцию. В Go для эмуляции неизменяемости вам придётся копировать много структур, что снизит производительность. Функциональным языкам это сходит с рук, потому что они могут полагаться на неизменяемость и всегда ссылаются на старые значения, а не копируют их снова.

Если вы действительно хотите заняться функциональным программированием, то обратите внимание на Elm. Это статически типизированный функциональный язык программирования для фронтенд-разработки. Для функционального языка он прост в изучении, как Go прост для императивного. Я за день написал руководство и тем же вечером смог начать продуктивно работать. Создатель языка постарался сделать его изучение простым, даже исключив необходимость разбираться с монадами. Лично мне нравится писать фронтенд на Elm в сочетании с бэкендом на Go. А если оба языка уже вам наскучили — то не переживайте, впереди ещё много интересного, вас ждёт Haskell.

Автор: Макс

Источник