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

Врождённая и приобретённая иммутабельность

В мире XAML-based платформ есть концепция Freezable-объектов. У каждого из них есть необратимый метод Freeze, после вызова которого любые попытки изменения вызывают исключение. Переход в заморозку может быть заблокирован самим объектом (CanFreeze = false), если он активно занят каким-либо процессом. Разморозить объект нельзя, но его можно скопировать через Clone, и мутировать копию до нового фриза. В сумме мы получаем три состояния и 4 перехода. Два перехода мы контролируем лишь косвенно, ещё 2 напрямую, но один из них приводит к новому объекту.

Оперировать такой конструкцией местами тяжко, но она возникла по соображениям перформанса, а не удобства. Нужна она в UI для контроля за распространением изменений. Например, когда кисть фона контрола меняет цвет, контрол должен себя перерисовать. Для этого надо следить за кистью, но если она будет заморожена, то надобность в слежке пропадёт и её можно будет свернуть. Поэтому замороженные (или иммутабельные) объекты для системы обходятся дешевле. Это звучит забавно, ибо в публичном пространстве превалирует обратная точка зрения.

По меркам F# тип Freezable скомпонован крайне неудачно, так что мы не будем выносить его за пределы естественной среды обитания. Однако кейс Freezable показывает, что в процессах подчёркнуто иммутабельные объекты обходятся дешевле, и с ростом сложности эта дельта увеличивается настолько, что её необходимо делать частью системы. Правило справедливо и для нашего сознания. Нам незачем беспокоиться об объекте, если мы можем считать его константой. Поэтому в F# мы исходим из положения, что вещь должна быть иммутабельной, пока не доказано обратного. Это положение дополняется ещё одним, которое гласит, что вещь должна становиться иммутабельной, как только необходимость в мутабельности отпала. Звучит похоже на Freezable, но F# подталкивает решать задачу иначе.

Объект до заморозки и объект после заморозки должны быть разными объектами. Важно, что истинную неизменяемость мы, конечно, приветствуем, но конкретно в этом месте не требуем, особенно в свете того, что создание реального объекта может сказаться на перфомансе. Речь идёт только о синтаксической недоступности изменений, что может трактоваться как замена одного фасада (в широком смысле) на другой.

Шадовинг

Вне зависимости от того, создали мы новый объект в результате «фриза» или просто навернули поверх него иную апиху, мы рискуем столкнуться с двумя представлениями одной сущности в рамках одного скоупа. Это обычная ситуация, например, для матчинга по типам, но не в нашем случае. <name><BeforeFreeze> и <name><AfterFreeze> кажутся благоглупостью на грани вредительства. Хочется, чтобы имя было одно, а скоупа два. Этого можно добиться через манёвры из предыдущей статьи, но в языке есть готовый механизм специально под эту задачу.

Shadowing, он же (терминология не устоялась) затенение, сокрытие, перекрытие или максимально сермяжно шадовИнг (но даже с буквой «в» слово имеет тенденцию к зажёвыванию, старайтесь его гаркать) — это ещё один способ фрагментации выражений, и его суть заключается в возможности создавать множество одноимённых привязок/переменных в рамках одного скоупа. Поначалу звучит очень контрпродуктивно, так что обратимся к функции растеризации линии на квадратной сетке (за подробностями идите в Тайловые миры -> Растеризация различных фигур).

На этапе подготовки алгоритм Брезенхема «вертит» плоскостью так, чтобы точки start и goal оказались в удобном для него положении. На практике это выражается в нескольких свапах самих точек и их компонент. В алгоритме, данном в оригинальной статье, этот момент реализуется через мутабельные start и goal:

func rast_line(start:Vector2, goal:Vector2) -> PoolVector2Array:
    var res:PoolVector2Array = []
    var steep = abs(goal.y-start.y) > abs(goal.x-start.x)
    if steep:
        start = Vector2(start.y, start.x)
        goal = Vector2(goal.y, goal.x)
    var reverse = start.x > goal.x
    if reverse:
        var x = start.x
        start.x = goal.x
        goal.x = x
        
        var y = start.y
        start.y = goal.y
        goal.y = y
    var dx = goal.x - start.x
    var dy = abs(goal.y - start.y)
    var ystep = 1 if start.y < goal.y else -1
    ...

Однако после подготовки алгоритм Брезенхема не трогает эти переменные. У них пропадает необходимость изменяться, что триггерит второе положение (о приобретённой иммутабельности). При помощи шадовинга мы можем сначала поработать с мутабельной переменной, а потом перекрыть её иммутабельной привязкой:

let mutable start = start
start <- ...
let start = start

Однако для наших свапов mutable start будет излишним, так как мы можем просто создавать новую пару значений на каждом обмене:

let rastLine start (goal : Vector2I) =
	let delta = (goal - start).Abs()
    let steep = delta.Y > delta.X
    let start, goal = // Здесь.
        if steep 
        then start.YX, goal.YX
        else start, goal
    let reverse = start.X > goal.X
    let start, goal = // И здесь.
        if reverse then goal, start else start, goal
    let yStep = if start.Y < goal.Y then 1 else -1
	...

Алгоритм алгоритму рознь, но где-то четверть переменных при попадании в F# превращается в череду привязок. Компилятор воспринимает их как несвязанные между собой сущности, так что не надо наделять одноимённые привязки/переменные магическими свойствами. Они не обязаны принадлежать одному типу. Их переименования происходят раздельно. Компилятор волен делать с перекрытой привязкой/переменной что угодно, если это не вредит остальному коду (например, замыканиям). То есть он может экономить память, повторно используя тот же «слот памяти», или дропнуть объект из кучи, если на него пропала последняя ссылка. Завязываться на это поведение не стоит, так как гарантий в этом сценарии нет никаких, кроме правила «мы не лезем к компилятору, компилятор не лезет к нам».

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

• Речь идёт о тайлах (ну или пикселях), это ограниченная область значений. Мы стремимся подчёркивать такие вещи, так что алгоритм работает с Vector2I (целочисленный вектор), а не Vector2 (float32-вектор).

• delta (dx, dy) и steep проще вычисляются через векторные операции (как и многое другое).

• Свойство .YX определено через расширения типов в далёком модуле Utils (нейминг вдохновлён кодом шейдеров).

• if оба раза работает как тернарный оператор. При этом он инициализирует сразу две привязки. Выглядит как особый синтаксис, но на самом деле if просто возвращает кортеж из двух элементов, а let start, goal = сей кортеж матчит и распихивает по привязкам. Сплошная механика и никакой магии или особых случаев.

Рекурсия

Наши start и goal «менялись» 2 раза. Мы не знаем конкретных значений и очень может быть, что итоговые вектора идентичны исходным. Однако процедур шадовинга через let было ровно 2, и мы знаем это на этапе компиляции. Но что, если количество операций неизвестно заранее? Мы можем отказаться от шадовинга и откатиться к мутабельным переменным. А можем вывести его на качественно новый уровень, прибегнув к рекурсии.

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

Речь не об очередной призме, к которой мы прибегаем из-за предыдущей главы (хотя это, безусловно, её следствие), а о точке зрения, которая должна быть доминирующей при работе на F#. Именно в таком ключе надо рассуждать о рекурсии, циклах и т. п. «ФПшно, неФПшно» — вопрос десятый. «Реалистично, нереалистично» — тоже (комментирую специально для мальчиков-реалистов в коротеньких штанишках).

Рекурсия в F# требует ключевое слово rec в привязке:

let rec f x =

Без ключевого слова rec на f нельзя будет ссылаться в теле функции. Причина проста, нам нужно явным образом отличать шадовинг от рекурсии, не подглядывая в скоуп:

let f x = x * 2 + 1

// shadowing:
let f x y =
    f x + y * 3 

// рекурсия:
let rec f x y =
    if x > 0 && y > 0 
    then f (x - 1) (y - 1)
    else x, y

У членов класса таких проблем нет, поэтому rec им не требуется.

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

Продолжение Брезенхема может выглядеть так:

let res = Array.zeroCreate (dx + 1)
let rec add index y error =
    let x = start.X + index
    res.[if reverse then res.Length - index - 1 else index] <-
        if steep then Vector2I(y, x) else Vector2I(x, y)
    if x <> goal.X then
        let factor = if error < delta.Y then 1 else 0
        add (index + 1) (y + yStep * factor) (error + delta.X * factor - delta.Y)
add 0 start.Y (delta.X / 2)
res

Это не самая оптимизированная версия, не самая лаконичная, но она хорошо читается, и в ней угадывается родовое сходство с версией из Тайловых миров. У нас 3 «переменные»: index, y и error, которые не существуют за пределами рекурсии и «меняются» только в момент перехода на следующий шаг. Сама рекурсия останавливается, когда мы достигаем последней вертикали. Всё выглядит как альтернативная запись цикла do while (если бы он у нас был).

Иммутабельные структуры данных в рекурсии

В F# рекурсии очень часто идут в связке с изменяемым окружением или объектами. Я бы мог использовать иммутабельную структуру данных для хранения точек и протаскивать её на каждой итерации, но в этом не было практического смысла. У нас только один потребитель, и его интересует только итоговая версия. Количество и порядок точек известны заранее, поэтому я позволил себе поиграть в производительность, взяв массив вместо ResizeArray. Если число потребителей увеличится, то массив можно преобразовать на этапе распространения в что-нибудь более подходящее.

Поводом для иммутабельной коллекции в самой рекурсии может послужить только:

1. Получение иммутабельной заготовки. Например, для операции продления отрезка;

2. Хранение и использование промежуточных результатов. Допустим, у нас есть политическая карта, история её изменений (дифов/событий) и нам нужен интерактивный вывод всего этого в журнал или таблицу рекордов. Задача превосходно решается на иммутабельных коллекциях без возни с Undo.

3. Нелинейный алгоритм принятия решений с разбором ситуаций «а что если».

4. Банальное удобство. Причины могут быть разными, но в основном дело касается паттерн-матчинга list, выступающего в роли стека. Ничего удобнее для разбора произвольного числа верхних элементов я пока не видел.

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

Управление состоянием

Формально любой цикл сводим к рекурсии, а любая рекурсия к циклу. Так что выбор между ними диктуется не целью алгоритма, а способом её достижения. В этом месте я потратил вялую неделю на объёмный кусок текста про их сравнение, но всё выпилил, так как циклы уводили повествование куда-то вниз и вбок. Я сконцентрируюсь на рекурсии и её преимуществах, а циклы буду упоминать по остаточному принципу (рекурсии LEFT JOIN циклы).

Выход из рекурсии

Первое преимущество рекурсии — лёгкая остановка. Если мы не вызываем следующий шаг, то его не будет. В циклах ситуация обратная. У нас нет break, по тем же причинам, по которым нет return, поэтому:

• Из for i = 0 to n do выскочить вообще нельзя.

• Из for item in items do можно выскочить только обрубив items, но для этого мы должны грамотно взломать енумератор.

• Из while condition do выскочить можно, если вы попали в условие. Если не попали, то в него надо добавлять соответствующую дырку (какой-нибудь let mutable stopped = false и && not stopped).

Укладка элемента в PriorityStack в GDScript была построена поверх прерывания (за подробностями идите в Тайловые миры -> Поиск пути):

func put(item, priority:int) -> void:
    if empty():
        items.append([item, priority])
    elif priority <= items[0][1]:
        items.insert(0, [item, priority])
    elif priority > items[-1][1]:
        items.append([item, priority])
    else:
        for i in range(len(items)):
            if priority <= items[i][1]:
                items.insert(i, [item, priority])
                break

В целях улучшения читаемости в F# поиск и добавление элемента обычно разносятся, как будет показано ниже, но при желании их можно оформить единым блоком:

member _.PutViaShortWhile priority item =
    let mutable index = 0
    let mutable found = false
    while index < items.Count && not found do
        if priority < fst ^ items.[index] then 
            found <- true
            items.Insert(index, (priority, item))
        else 
            index <- index + 1
    if not found then
        items.Add (priority, item)

member _.PutViaShortRec priority item =
    let rec tryFind index =
        if index = items.Count then 
            items.Add (priority, item)
        elif priority < fst ^ items.[index] then
            items.Insert(index, (priority, item))
        else 
            tryFind (index + 1)
    tryFind 0

Второе преимущество рекурсии — лёгкая выдача результата. Если подумать, то циклам это вообще не положено, ибо каждый цикл — это выражение типа unit. Если оно вдруг начнёт возвращать что-то иное, то нам потребуется аналог ветки else. Я б на такое глянул с большИм интересом, но не без опасений. В большинстве языков такое прокатывает только из-за особенностей синтаксиса, где return вытаскивает значение из любой точки метода и ему без разницы, вызвали его в цикле или нет. Конкретно в этом месте подход «жги всех, компилятор узнает своих» нам недоступен, поэтому нам надо сохранить результат в какой-то заранее подготовленный слот, а потом имитировать break из предыдущего пункта:

member _.PutViaWhile priority item =
    let mutable index = 0
    let mutable found = false
    while index < items.Count && not found do
        if priority < fst ^ items.[index]
        then found <- true
        else index <- index + 1
    if found
    then items.Insert(index, (priority, item))
    else items.Add (priority, item)

Тело рекурсии является выражением произвольного типа. В PutViaShortRec оно возвращало (). Напоминаю, что неполную конструкцию if ... then компилятор неявно «дополняет «веткой else (). Но вместо unit может быть любой другой тип и тогда компилятор начнёт агрессивно требовать от нас результат в каждой ветке. Если вы не можете выдать его напрямую в данной итерации, то вы можете дать компилятору новый вызов рекурсии, который с точки зрения сигнатуры даёт результат нужного типа. Компилятор слабо понимает устройство рекурсии, но он зудит достаточно сильно, чтобы выбор между результатом и следующей итерацией был почти принудительным:

member _.PutViaRec priority item =
    let rec tryFind index =
        if index = items.Count then None 
        elif priority < fst ^ items.[index] then Some index 
        else tryFind (index + 1)
    match tryFind 0 with
    | Some index -> items.Insert(index, (priority, item))
    | None -> items.Add (priority, item)

Вход в рекурсию

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

type Item = { Id : ItemId; Priority : int option }

let tryMinByPriorityViaFor (items : Item seq) =
    let mutable least = None

    for item in items do
        match least, item.Priority with
        | None, Some value ->
            least <- Some (item, value)
        | Some (_, leastPriority), Some value when leastPriority > value ->
            least <- Some (item, value)
        | _, _ ->
            ()

    least

Наибольшее раздражение здесь вызывает переменная least. Мы на каждой итерации вынуждены проверять её наличие, а потом сравнивать сохранённый приоритет с тем, что есть в новом элементе. Однако если обратиться к сути вещей, то станет ясно, что least после первой инициализации не может откатиться в None. Он имеет линию развития, не нуждающуюся в таком количестве проверок на существование. По-хорошему, нам если и нужна проверка, то только одна, в момент перехода.

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

1. Для небытия, когда несуществующая сущность вообще отсутствует в коде;

2. Для бытия, когда сущность принадлежит типу 'entity, а не 'entity option.

Ни циклы, ни рекурсии сами по себе не могут представить их в такой форме. Однако там, где не справляется один цикл, справятся два. Нам нужно при достижении инициализации 'entity выдать его наружу, остановить цикл и запустить новый с твёрдым знанием о существовании объекта. Всё это надо сделать с учётом вероятности, что 'entity вообще не будет инициализирован.

Как мы видели, циклы плохо приспособлены к остановке и выдаче результата. Но зато у рекурсий таких проблем нет. Первая рекурсия может вернуть какой-нибудь:

type FirstResult =
    | FinalResult of 'final
    | EntityCreated of 'entity

Тогда мы его проматчим, и запустим вторую рекурсию для кейса EntityCreated, после чего она вычислит 'final с опорой на 'entity. Однако если всё действительно обстоит так прямолинейно, то лучше сразу перейти из одной рекурсии в другую:

let tryMinByPriorityViaRec (items : Item seq) =
    let en = items.GetEnumerator()

    let rec waitNext least leastPriority =
        match en.TryNext() with // `TryNext` - type extension
        | None ->
            Some least
        | Some ({ Priority = Some priority } as item) when priority < leastPriority ->
            waitNext item priority
        | _ ->
            waitNext least leastPriority
    
    let rec waitFirst () =
        match en.TryNext() with
        | None ->
            // FinalResult.Final None
            None
        | Some ({ Priority = Some priority } as item) ->
            // Переход в другую рекурсию.
            // FinalResult.EntityCreated (item, priority)
            waitNext item priority
        | Some item -> waitFirst ()

    waitFirst ()

waitNext является продолжением waitFirst, но задекларирована она первой. Если тип передаваемого 'entity окажется нетривиальным, например, анонимным рекордом или дженериком с кучей непримитивных параметров, то нам придётся типизировать руками. Это утомительно и вредно, так как создаёт ложно самостоятельный источник информации. Для таких случаев есть особый rec ... and-синтаксис:

let tryMinByPriorityViaRec (items : Item seq) =
    let en = items.GetEnumerator()
    
    let rec waitFirst () =
        match en.TryNext() with
        | None ->
            None
        | Some ({ Priority = Some priority } as item) ->
            waitNext item priority
        | Some item ->
            waitFirst ()
    and waitNext least leastPriority =
        match en.TryNext() with
        | None ->
            Some least
        | Some ({ Priority = Some priority } as item) when priority < leastPriority ->
            waitNext item priority
        | _ ->
            waitNext least leastPriority

    waitFirst ()

Строго говоря, rec ... and предназначался не совсем для этого. Дело в том, что без него невозможно вменяемо выразить взаимно рекурсивные функции, так как при последовательном определении какая-то из них будет ссылаться на ещё неопределённую. Обратный переход в waitFirst доступен синтаксически, но в силу устройства алгоритма его у нас нет, поэтому наши функции не взаимно рекурсивные. Однако компилятор этот произвол терпит. Мы прибегаем к rec ... and из-за того, что нам надо выстроить определения функции в порядке их вызова. Компилятор учитывает все «взаимно рекурсивные» определения разом, но, как и до этого, он будет двигаться «сверху вниз, слева направо», так что теперь функция waitNext будет находиться ниже функции waitFirst. Ниже значит позже, а значит типизация waitNext будет подчинена контексту использования, например:

• waitFirst в первом кейсе возвращает None, а во втором — waitNext. Из-за этого результат waitNext будет обозначен как 'a option (для конкретизации 'a информации недостаточно);

• При первом вызове waitNext в него передаются экземпляры Item и int, из чего можно заключить, что именно такие типы имеют его параметры.

С точки зрения внешней оценки эффективности разработки грамотное верчение вызовами — очень неочевидный навык с неочевидной полезностью, поэтому в новичковой среде ему практически не уделяют внимания. Сложностей здесь радикально меньше, чем в классических ФП-темах, но, если вы не задаёте вопросы вида: «почему список идёт до List.map?» или «почему процедура инициализации в свёртках, переменных и т. д. описывается раньше, чем использование инициализированного значения?», то вы на них не отвечаете.

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

let res = Array.zeroCreate (delta.X + 1)
let rec build () =
    add 0 start.Y (delta.X / 2)
and add index y error =
    let x = start.X + index
    res.[if reverse then res.Length - index - 1 else index] <-
        if steep then Vector2I(y, x) else Vector2I(x, y)
    if x <> goal.X then
        let factor = if error < delta.Y then 1 else 0
        add (index + 1) (y + yStep * factor) (error + delta.X * factor - delta.Y)
build ()
res

Метод build «анонсирует» параметры на основе существующих в скоупе значений. В первую очередь это провоцирует компилятор на точную типизацию, но и нам такой код читать проще, так как мы сразу понимаем, с чего начнётся процесс.

На всякий случай уточню, что тип параметров в такой записи подчиняется тем же правилам, что и переменные. Например, если переменная myNode была создана как new Button(), то она принадлежит типу Button. Если нам надо закидывать в неё обычный Node, то нам надо явно указать её тип в момент декларации. К параметрам предъявляются те же требования:

let myNode = // : Button
    ...

let rec getVBoxAncestor () =
    // : Node - подсказка для интерпретации.
    // :> Node - upcast.
    // Конкретно здесь результат одинаков.
    getNext (myNode : Node)
and getNext node =
    match node with
    | :? VBoxContainer as res -> res
    | node ->
        node.GetParent()
        |> getNext // Эта строка рухнет без `: Node`, так как будет ожидаться `Button`.

Переход внутри рекурсии

Четвёртое преимущество рекурсии — ручной переход к следующей итерации. Под переходом я имею ввиду не выбор направления движения, а само движение по выбранному маршруту. До этого оно было вне сферы нашего внимания. По большей части из-за того, что в циклах мы его тоже почти не видим, так как они встроены слишком глубоко в язык. Мы понимаем, как они работают, но переход между итерациями нами не ощущается. Лишь мизерная доля разрабов хоть как-то опишет его, когда будет ковырять в билдерах методы For и While.

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

add (index + 1) (y + yStep * factor) (error + delta.X * factor - delta.Y)

Мы не стремимся интерпретировать рекурсию буквально, чтобы не уйти в условно бесконечный цикл вычислений, так как его очень сложно воспринять. Медицина может меня поправить, но мне кажется, что не существует людей, которые глядя на отрезок в 30 точек скажут: «Для простоты давайте материализуем рекурсию в виде выражения на 150+ строк и 30 табов.». Конкретно здесь компилятор поступит умно и за счёт хвостовой рекурсии преобразует add в цикл. Тоже самое мы мысленно сделаем сами. Однако с точки зрения выражений никакого цикла нет, есть бесконечно проваливающиеся друг в друга вызовы. Эти вызовы можно сделать явными, чтобы подчинить их воле внешней силы. Тогда общим исполнением всей рекурсии можно будет управлять, не прибегая к правке алгоритма.

Когда мы переписали tryMinByPriority на рекурсию, кода стало больше. Это связано с тем, что нам надо было вручную проверять возможность текущей итерации, и по факту мы обменяли проверку состояния на проверку элемента. Для столь примитивных сценариев размен получается не очень выгодным, но ситуация меняется, когда «движение» наряду с «направлением» становится важной частью алгоритма. Суть идеи проста, если мы делаем движение явным и выносим его в некий внешний раннер, то нам остаётся только выдавать ему направление движения.

В tryMinByPriority проверкой текущей итерации займётся раннер, но теперь ему надо знать свои действия для двух сценариев, что возвращать, если коллекция закончилась, и что делать с новым элементом, если коллекция продолжается. Для них нам бы подошёл обычный кортеж из двух функций, но их невозможно скормить компилятору, так как они требуют невозможную конфигурацию типов. Первый сценарий тривиально выражается функцией unit -> Item option, а вот сигнатура второго уходит в бесконечность при попытке выразить результат функции Item -> _:

(unit -> Item option) * (Item -> ((unit -> Item option) * (Item -> ((unit -> Item option) * (Item -> <памагитте...>)))))

Тут мы «внезапно» сталкиваемся с тем, что для раскрытого описания рекурсии нам надо рекурсивно сослаться на описание рекурсии. Из контекста компилятор такое вывести не может, а для выражения такой сигнатуры руками у нас нет языковых средств. Потенциально здесь мог бы сработать алиас:

type RecDirection = (unit -> Item option) * (Item -> RecDirection)

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

type RecDirection = {
    OnNil : unit -> Item option
    OnCons : Item -> RecDirection
}

Служебные рекурсивные типы для неявного выражения рекурсивных вычислений — это каноничная практика. Она поддерживается на уровне языка и не ломает хвостовую рекурсию, так что её можно встретить во многих крутых штуках. Например, Hopac.Stream построен поверх DU Hopac.Stream.Cons, кейсы которого зеркально отражают наш RecDirection. Такие типы всегда выглядят неочевидно, но они определяют предельные возможности библиотеки. Если итерирующий механизм при необходимости спокойно переписывается и заменяется, то с отсутствием данных в базовом типе уже ничего не сделаешь.

В нашем случае итератор для коллекции сведётся к обычной свёртке:

let runViaFor direction items =
    let mutable direction = direction
    for item in items do
        direction <- direction.OnCons item
    direction.OnNil ()

let runViaFold direction items =
    (direction, items)
    ||> Seq.fold ^ fun p -> p.OnCons
    |> fun p -> p.OnNil()

А функции waitFirst и waitNext станут фабриками:

let rec waitFirst () = {
    OnNil = fun () -> None
    OnCons = fun item ->
        match item.Priority with
        | None -> waitFirst ()
        | Some priority -> waitNext item priority
}
and waitNext least leastPriority = {
    OnNil = fun () -> Some least
    OnCons = fun item ->
        match item.Priority with
        | Some priority when priority < leastPriority ->
            waitNext item priority
        | _ ->
            waitNext least leastPriority
}

runViaFor (waitFirst ()) items

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

let rec waitFirst () = {
    OnNil = fun () -> None
    OnCons = fun item ->
        match item.Priority with
        | None -> Remain // Оставляем предыдущее поведение.
        | Some priority -> Become ^ waitNext item priority
}
and waitNext least leastPriority = {
    OnNil = fun () -> Some least
    OnCons = fun item ->
        match item.Priority with
        | Some priority when priority < leastPriority ->
            Become ^ waitNext item priority
        | _ -> 
            Remain // Оставляем предыдущее поведение.
}

А если его очень долго дорабатывать, то можно прийти к чему-нибудь такому:

let rec empty () = ...
and loading started = ...
and failed error = ...
and loaded data =
    // Все обработчики будут опираться
    // на точно существующий `data`
    become [
        leftMouseButton => fun () -> ...
        rightMouseButton => fun () -> ...
        quit => fun () -> ...
    ]

Система типов, лежащая в основе данного примера, затрагивает моменты, чрезвычайно далекие от нашего повествования. Но для нас важна не система, а происхождение данных, с которыми она работает. Когда итератор принадлежит нам, мы можем приостанавливать и продолжать рекурсию в произвольный момент времени. Благодаря этому раннер может быть прикручен к _Process, Event, сигналам, ECS и т. д., что превратит рекурсию в стейт-машину или актор произвольной сложности, который можно запустить из любой точки кода.

Быстрорастворимый спавн актора — это не причуда и не просто хелпер типа i++. Это превосходная возможность передать актору произвольные элементы скоупа чисто по месту требования. Он будет использовать их ровно такими, какими они созданы, при этом не требуя их декларации в каком-нибудь контракте. Никаких следов, никаких транзакций, никаких манифестаций. Чистое действие.

Промежуточное заключение

Судя по тестовым прогонам, последний параграф очень сильно довлеет над общим повествованием, что немножечко не соответствует моим изначальным намерениям. Действительно, связка из рекурсии и раннера позволяет творить чудовищные вещи. Мне даже иногда кажется, что самые могущественные вещи, которые можно написать на F#, пилятся только при участии этой связки. Однако следует понимать ограниченность её распространения.

Во-первых, в языке есть ещё много средств, которые разбираются с какими-то частными случаями более простым образом. Во-вторых, связка часто не присутствует в коде в явном виде. Она управляет ядром, а всё внешнее взаимодействие с подконтрольными сущностями организуется через более привычное API. В-третьих, даже если она видна снаружи и вообще никак не спрятана, необходимость в ней может отсутствовать по причине исчерпывающего покрытия библиотечными функциями. Так происходит с Hopac.Stream, где ручной осмотр Stream.Cons нужен либо для написания ещё нескольких библиотечных функций, либо для сверхоптимизаций.

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

Что касается рекурсии в вульгарном понимании как элемента «обычных» алгоритмов, то она широко распространена. Хотя бы потому, что она отражает семантику while гораздо лучше, чем сам while.

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

Автор статьи @kleidemos

---

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS