[Перевод] Вычислительные выражения: Добавляем ленивость02.09.2024 09:30

0f53d11474b081f4051925ada5858f28.jpg

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

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

Обратите внимание, что «построитель» в контексте вычислительного выражения — это не то же самое, что и объектно-ориентированный «паттерн строитель», нужный для конструирования и валидации объектов.

Проблема

Вот код из нашего класса-построителя maybe.
Он основан на построителе trace из предыдущих постов, но без трассирующих сообщений, так что сейчас код — чистый и красивый.

type MaybeBuilder() =

    member this.Bind(m, f) =
        Option.bind f m

    member this.Return(x) =
        Some x

    member this.ReturnFrom(x) =
        x

    member this.Zero() =
        None

    member this.Combine (a,b) =
        match a with
        | Some _ -> a  // если значение a существует, пропускаем b
        | None -> b()  // если значение a не существует, запускаем b

    member this.Delay(f) =
        f

    member this.Run(f) =
        f()

// создаём экземпляр процесса
let maybe = new MaybeBuilder()

Прежде чем двигаться дальше, убедимся, что вы понимаете, как работает этот код.
Проанализировав его, мы увидим, что, если опираться на терминологию из предыдущих постов, здесь встречаются такие типы:

  • Тип-обёртка: 'a option

  • Внутренний тип: 'a option

  • Тип отложенного вычисления: unit -> 'a option

Теперь давайте проверим этот код и убедимся, что всё работает как надо.

maybe {
    printfn "Часть 1: перед return 1"
    return 1
    printfn "Часть 2: после return"
    } |> printfn "Результат Части 1, но не Части 2: %A"

// результат - вторая часть НЕ ВЫПОЛНЯЕТСЯ

maybe {
    printfn "Часть 1: перед return 1"
    return! None
    printfn "Часть 2: после None, продолжаем работать"
    } |> printfn "Результат Части 1, а затем Части 2: %A"

// результат - вторая часть ВЫПОЛНЯЕТСЯ

Но что произойдёт, если мы поместим этот код в дочерний процесс, как здесь: 

let childWorkflow =
    maybe {printfn "Дочерний процесс"}

maybe {
    printfn "Часть 1: перед return 1"
    return 1
    return! childWorkflow
    } |> printfn "Результат Части 1, но не childWorkflow: %A"

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

Итак, как избежать ненужных вычислений?

Оборачиваем внутренний тип в отложенную функцию

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

Вот наш новый тип-обёртка: 

type Maybe<'a> = Maybe of (unit -> 'a option)

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

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

// до
member this.Run(f) =
    f()

// после
member this.Run(f) =
    Maybe f

Я забыл поправить ещё один метод — вы догадались, какой? Скоро узнаете!

Ещё одно: теперь нам нужно что-то, что будет «запускать» отложенную функцию и возвращать результат.

let run (Maybe f) = f()

Давайте испытаем наш новый тип на предыдущих примерах: 

let m1 = maybe {
    printfn "Часть 1: перед return 1"
    return 1
    printfn "Часть 2: после return 1"
    }

Запуская код, мы получаем что-то такое: 

val m1 : Maybe = Maybe

Выглядит нормально; не печатает ничего ненужного.

Теперь запускаем: 

run m1 |> printfn "Результат Части 1, но не Части 2: %A"

и получаем вывод: 

Часть 1: перед return 1
Результат Части 1, но не Части 2: Some 1

Великолепно. Часть 2 не запускалась.

Но мы сталкиваемся с проблемой в следующем примере: 

let m2 = maybe {
    printfn "Часть 1: перед return None"
    return! None
    printfn "Часть 2: после None, продолжаем выполнение"
    }

Ой!
Мы забыли поправить ReturnFrom!
Как мы знаем, этот метод получает тип-обёртку, и сейчас мы должны переопределить этот тип-обёртку.

Наше исправление: 

member this.ReturnFrom(Maybe f) =
    f()

Мы собираемся откуда-то принять Maybe и сразу после этого запустить его, чтобы получить опциональное значение.

Но сейчас у нас появилась другая проблема — мы больше не можем вернуть None в явном виде в конструкции return! None, вместо этого мы должны вернуть тип Maybe.
Получится ли у нас сделать что-то подобное?

Скажем, мы могли бы написать вспомогательную функцию, которая конструирует для нас нужный объект.
Но есть и более простой ответ: мы можем создать новый объект Maybe используя выражение maybe! 

let m2 = maybe {
    return! maybe {printfn "Часть 1: перед return None"}
    printfn "Часть 2: после None, продолжаем"
    }

Вот для чего нужен метод Zero.
С помощью Zero и экземпляра построителя можно создавать экземпляры типа-обёркти, даже если они ничего не делают.

Но теперь у нас появилась ещё одна ошибка — страшное «ограничение значения».

Ограничение значения. Значения 'm2' было выведено, как имеющее общий тип.

Причина, по которой это случилось заключается в том, что оба выражения возвращают None.
Но компилятор не знает, к какому типу относится None.
Этот код использует None типа Option (предположительно из-за неявной упаковки), однако, компилятор знает, что тип может быть более общим.

Есть два способа избавиться от ошибки.
Первый — сделать тип явным: 

let m2_int: Maybe = maybe {
    return! maybe {printfn "Часть 1: перед return None"}
    printfn "Часть 2: после None, продолжаем;"
    }

Или вместо None мы можем вернуть какое-то значение: 

let m2 = maybe {
    return! maybe {printfn "Часть 1: перед return None"}
    printfn "Часть 2: после None, продолжаем;"
    return 1
    }

Оба решения позволяют избавиться от проблемы.

Теперь, если мы запустим пример, мы получим тот результат, который и ожидали.
Вторая часть продолжает выполняться.

run m2 |> printfn "Результат Части 1 и последующей Части 2: %A"

Трассирующий вывод: 

Часть 1: перед return None
Часть 2: после None, продолжаем;
Результат Части 1 и последующей Части  2: Some 1

Наконец, снова попытаемся запустить примеры с дочерними процессами: 

let childWorkflow =
    maybe {printfn "Дочерний процесс"}

let m3 = maybe {
    printfn "Часть 1: перед return 1"
    return 1
    return! childWorkflow
    }

run m3 |> printfn "Результат Части 1, но без childWorkflow: %A"

И теперь дочерний процесс не выполняется, как мы и хотели.

А если нам надо, чтобы дочерний процесс выполнился, запустим его так: 

let m4 = maybe {
    return! maybe {printfn "Часть 1: перед return None"}
    return! childWorkflow
    }

run m4 |> printfn "Результат Части 1 и последующего дочернего процесса: %A"

Обзор класса-построителя

Давайте снова взглянем на код класса-построителя целиком: 

type Maybe<'a> = Maybe of (unit -> 'a option)

type MaybeBuilder() =

    member this.Bind(m, f) =
        Option.bind f m

    member this.Return(x) =
        Some x

    member this.ReturnFrom(Maybe f) =
        f()

    member this.Zero() =
        None

    member this.Combine (a,b) =
        match a with
        | Some _' -> a    // Если есть значение a, опускаем значение b
        | None -> b()     // Если нет значения a, запускаем b

    member this.Delay(f) =
        f

    member this.Run(f) =
        Maybe f

// создаём экземпляр процесса
let maybe = new MaybeBuilder()

let run (Maybe f) = f()

Проанализировав его, мы увидим, что, если опираться на терминологию из предыдущих постов, здесь встречаются такие типы:

  • Тип-обёртка: Maybe<'a>

  • Внутренний тип: 'a option

  • Тип отложенного вычисления: unit -> 'a option

Заметьте, что в данном случае удобно использовать в качестве внутреннего типа стандартный 'a option, поскольку в этом случае нам не нужно модифицировать ни Bind, ни Return.

Альтернативный подход заключается в том, чтобы использовать в качестве внутреннего типа Maybe<'a>. Это сделает код более согласованным, но, в то же время, более сложным для понимания.

Истинная ленивость

Вот последний пример с небольшими правками: 

let child_twice: Maybe = maybe {
    let workflow = maybe {printfn "Дочерний процесс"}

    return! maybe {printfn "Часть 1: перед return None"}
    return! workflow
    return! workflow
    }

run child_twice |> printfn "Результат двойного childWorkflow: %A"

Что должно произойти?
Сколько раз выполниться дочерний процесс?

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

В некоторых случаях вам важно, чтобы процесс гарантированно запускался по меньшей мере один раз с последующим кешированием результата (мемоизацией).
Это достаточно просто сделать, используя тип Lazy, который встроен в F#.

Изменения, которые нам нужно будет сделать:

  • Maybe будет оборачивать Lazy вместо отложенной функции

  • ReturnFrom и run будут форсировать вычисление ленивого значения

  • Run будет заворачивать вызов отложенной функции в lazy

Вот новый класс с указанными изменениями: 

type Maybe<'a> = Maybe of Lazy<'a option>

type MaybeBuilder() =

    member this.Bind(m, f) =
        Option.bind f m

    member this.Return(x) =
        Some x

    member this.ReturnFrom(Maybe f) =
        f.Force()

    member this.Zero() =
        None

    member this.Combine (a,b) =
        match a with
        | Some _' -> a    // Если есть значение a, опускаем значение b
        | None -> b()     // Если нет значения a, запускаем b

    member this.Delay(f) =
        f

    member this.Run(f) =
        Maybe (lazy f())

// создаём экземпляр процесса
let maybe = new MaybeBuilder()

let run (Maybe f) = f.Force()

И, если мы запустим код с двойным дочерним процессом, мы получим: 

Часть 1: перед return None
Дочерний процесс
Результат двойного childWorkflow:

откуда понятно, что дочерний процесс был запущен только один раз.

Итого: немедленные, отложенные и ленивые вычисления

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

Так… какой же подход использовать?

На этот вопрос нет единственного «правильного ответа».
Ваш выбор зависит от нескольких вещей:

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

  • Является ли код дорогим с точки зрения ресурсов, может ли результат отличаться при последующих запусках (т.е. является код недетерминированным), или содержит существенные побочные эффекты? Если да, используйте вторую — отложенную — версию. Именно так устроено большинство процессов, особенно, относящихся к вводу и выводу (таких как async).

  • F# не пытается быть чистым функциональным языком, так что почти весь код на F# попадёт в одну из этих двух категорий. Но, если вам нужен код, в котором гарантированно нет побочных эффектов или вы хотите быть уверены, что дорогой с точки зрения ресурсов код выполняется не больше одного раза, используйте третий — ленивый — вариант.

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

Это всё, что касается отложенных и ленивых вычислений. Теперь вернёмся к методам построителя и познакомимся с теми, которые нам пока не встречались.

Habrahabr.ru прочитано 9208 раз