Тотальный язык на обычных задачах: 26 решений LeetCode, у 20 завершение доказано компилятором.

модуль «Две суммы»

// LeetCode 1. Two Sum.
// Дан список чисел и цель. Найти два разных элемента, дающих в сумме цель,
// и вернуть их номера. Номера — с нуля, как в условии задачи; язык нумерует
// строки с единицы, поэтому пересчёт делается один раз, в конце.
//
// Тотальная. Хеш-таблиц в языке нет, поэтому вместо словаря «значение → номер»
// работает вложенный проход: для каждой головы ищем дополнение в хвосте.
// Это O(n²) вместо O(n) — прямая цена отсутствия ассоциативного массива.

тотальная функция «Позиция значения»
  принимает элементы: список числа, нужное: число
  возвращает число
  пример «Найдено вторым»
    дано элементы равно [5, 7]
    дано нужное равно 7
    ожидается 2
  пример «Не найдено»
    дано элементы равно [5, 7]
    дано нужное равно 9
    ожидается 0
  разбор элементов
    случай пусто
      то 0
    случай голова и хвост
      если голова равен нужное
        то 1
        иначе
          пусть дальше равно «Позиция значения» от хвост и нужное
          если дальше равен 0 то 0 иначе дальше плюс 1

тотальная функция «Поиск пары с позиции»
  принимает элементы: список числа, цель: число, позиция: число
  возвращает список числа
  пример «Пара в начале»
    дано элементы равно [2, 7, 11]
    дано цель равно 9
    дано позиция равно 0
    ожидается [0, 1]
  разбор элементов
    случай пусто
      то пустой список
    случай голова и хвост
      пусть смещение равно «Позиция значения» от хвост и (цель минус голова)
      если смещение больше 0
        то [позиция, позиция плюс смещение]
        иначе «Поиск пары с позиции» от хвост и цель и (позиция плюс 1)

тотальная функция «Две суммы»
  принимает элементы: список числа, цель: число
  возвращает список числа
  пример «Пример 1 из условия»
    дано элементы равно [2, 7, 11, 15]
    дано цель равно 9
    ожидается [0, 1]
  пример «Пример 2 из условия»
    дано элементы равно [3, 2, 4]
    дано цель равно 6
    ожидается [1, 2]
  пример «Пример 3 из условия»
    дано элементы равно [3, 3]
    дано цель равно 6
    ожидается [0, 1]
  «Поиск пары с позиции» от элементы и цель и 0

модуль «Удалить повторы»

// LeetCode 26. Remove Duplicates from Sorted Array.
// Из отсортированного списка убрать повторы. В условии просят изменить массив
// на месте и вернуть число уникальных; изменяемых массивов в языке нет и быть
// не может — значения flang неизменяемы, — поэтому возвращается новый список,
// а «число уникальных» вынесено отдельной функцией.
//
// Тотальная: свёртка по списку, рекурсии нет вовсе.

тотальная функция «Без повторов»
  принимает элементы: список числа
  возвращает список числа
  пример «Пример 1 из условия»
    дано элементы равно [1, 1, 2]
    ожидается [1, 2]
  пример «Пример 2 из условия»
    дано элементы равно [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
    ожидается [0, 1, 2, 3, 4]
  свёртка элементы начиная с пустой список как акк и эл
    если акк содержит эл то акк иначе добавить эл к акк

тотальная функция «Сколько уникальных»
  принимает элементы: список числа
  возвращает число
  пример «Пример 1 из условия»
    дано элементы равно [1, 1, 2]
    ожидается 2
  пример «Пустой список»
    дано элементы равно пустой список
    ожидается 0
  длина («Без повторов» от элементы)

модуль «Место вставки»

// LeetCode 35. Search Insert Position.
// В отсортированном списке найти номер цели, а если её нет — номер, куда её
// следовало бы вставить. Номера с нуля, как в условии.
//
// Тотальная. Условие требует O(log n), здесь же один линейный проход:
// двоичный поиск в тотальном классе требует особого приёма (см. 704), а
// линейная свёртка доказывается сама. Ответ тот же, сложность хуже —
// и это честная цена, а не недосмотр.

тотальная функция «Место вставки»
  принимает элементы: список числа, цель: число
  возвращает число
  пример «Пример 1 из условия»
    дано элементы равно [1, 3, 5, 6]
    дано цель равно 5
    ожидается 2
  пример «Пример 2 из условия»
    дано элементы равно [1, 3, 5, 6]
    дано цель равно 2
    ожидается 1
  пример «Пример 3 из условия»
    дано элементы равно [1, 3, 5, 6]
    дано цель равно 7
    ожидается 4
  свёртка элементы начиная с 0 как акк и эл → если эл меньше цель то акк плюс 1 иначе акк

модуль «Группировка анаграмм»

// LeetCode 49. Group Anagrams.
// Разложить слова по группам: в одной группе — слова из одних и тех же букв.
//
// Тотальная. Каноническое решение — словарь «подпись → список слов», а
// ассоциативных массивов в языке нет. Замена: список записей «Группа» и
// линейный поиск по ключу. Подпись слова тоже строится без обхода символов —
// свёрткой по алфавиту с подсчётом через «разделить» (тот же приём, что в
// задаче 242). Порядок групп — порядок первого появления.
//
// Цена отсутствия словаря: O(слов × групп × 26) вместо O(суммарной длины).

объект «Группа»
  ключ является строкой
  слова является список строки

тотальная функция «Счёт буквы»
  принимает текст: строка, буква: строка
  возвращает число
  пример «Две буквы a»
    дано текст равно "abac"
    дано буква равно "a"
    ожидается 2
  (длина (разделить текст по буква)) минус 1

тотальная функция «Подпись»
  принимает слово: строка
  возвращает строка
  пример «Анаграммы дают одну подпись»
    дано слово равно "eat"
    ожидается "1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,"
  пример «Другое слово — другая подпись»
    дано слово равно "bat"
    ожидается "1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,"
  свёртка ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"] начиная с "" как акк и буква
    соединить (соединить акк с (к строке («Счёт буквы» от слово и буква))) с ","

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

тотальная функция «Добавить слово»
  принимает группы: список «Группа», ключ: строка, слово: строка
  возвращает список «Группа»
  если «Есть группа» от группы и ключ
    то
      отобразить группы как группа
        если группа.ключ равен ключ
          то запись «Группа» с ключ равным ключ и слова равным (добавить слово к группа.слова)
          иначе группа
    иначе добавить (запись «Группа» с ключ равным ключ и слова равным [слово]) к группы

тотальная функция «Группировать анаграммы»
  принимает слова: список строки
  возвращает список список строки
  пример «Пример 1 из условия»
    дано слова равно ["eat", "tea", "tan", "ate", "nat", "bat"]
    ожидается [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
  пример «Пример 2 из условия»
    дано слова равно [""]
    ожидается [[""]]
  пример «Пример 3 из условия»
    дано слова равно ["a"]
    ожидается [["a"]]
  пусть группы равно свёртка слова начиная с пустой список как акк и слово
    «Добавить слово» от акк и («Подпись» от слово) и слово
  отобразить группы как группа → группа.слова

модуль «Максимальная подпоследовательность»

// LeetCode 53. Maximum Subarray.
// Найти наибольшую сумму непрерывного куска списка (алгоритм Кадане).
//
// Тотальная. Это самая «динамическая» из задач, которые язык принимает без
// сопротивления: состояние Кадане — два числа, а два числа складываются в
// запись, и запись отлично живёт накопителем свёртки. Настоящая динамика
// с таблицей (Coin Change, Edit Distance) так не переносится — там нужен
// массив с произвольным доступом по индексу, которого в языке нет.

объект «Состояние Кадане»
  текущая является числом
  лучшая является числом

тотальная функция «Наибольшая сумма куска»
  принимает элементы: список числа
  возвращает число
  пример «Пример 1 из условия»
    дано элементы равно [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    ожидается 6
  пример «Пример 2 из условия»
    дано элементы равно [1]
    ожидается 1
  пример «Пример 3 из условия»
    дано элементы равно [5, 4, -1, 7, 8]
    ожидается 23
  пример «Пустой список»
    дано элементы равно пустой список
    ожидается 0
  разбор элементов
    случай пусто
      то 0
    случай голова и хвост
      пусть начальное равно запись «Состояние Кадане» с текущая равным голова и лучшая равным голова
      пусть итог равно свёртка хвост начиная с начальное как акк и эл
        пусть продолженная равно акк.текущая плюс эл
        пусть текущая равно если продолженная больше эл то продолженная иначе эл
        пусть лучшая равно если текущая больше акк.лучшая то текущая иначе акк.лучшая
        запись «Состояние Кадане» с текущая равным текущая и лучшая равным лучшая
      итог.лучшая

модуль «Прибавить единицу»

// LeetCode 66. Plus One.
// Список цифр — большое число. Прибавить к нему единицу.
//
// Тотальная. Перенос идёт справа налево, а свёртка идёт слева направо,
// поэтому список сначала обращается, потом сворачивается, потом обращается
// обратно. Обращение выражается свёрткой, а не встроенной формой: приписать
// элемент в начало списка встроенным «добавить … к …» нельзя — оно
// дописывает в конец.

объект «Перенос»
  перенос является числом
  цифры является список числа

тотальная функция «Приписать в начало»
  принимает первый: число, элементы: список числа
  возвращает список числа
  пример «В непустой»
    дано первый равно 1
    дано элементы равно [2]
    ожидается [1, 2]
  свёртка элементы начиная с [первый] как акк и эл → добавить эл к акк

тотальная функция «Обратить»
  принимает элементы: список числа
  возвращает список числа
  пример «Три элемента»
    дано элементы равно [1, 2, 3]
    ожидается [3, 2, 1]
  свёртка элементы начиная с пустой список как акк и эл → «Приписать в начало» от эл и акк

тотальная функция «Прибавить единицу»
  принимает цифры: список числа
  возвращает список числа
  пример «Пример 1 из условия»
    дано цифры равно [1, 2, 3]
    ожидается [1, 2, 4]
  пример «Пример 2 из условия»
    дано цифры равно [4, 3, 2, 1]
    ожидается [4, 3, 2, 2]
  пример «Пример 3 из условия»
    дано цифры равно [9]
    ожидается [1, 0]
  пример «Сплошные девятки»
    дано цифры равно [9, 9, 9]
    ожидается [1, 0, 0, 0]
  пусть начальное равно запись «Перенос» с перенос равным 1 и цифры равным пустой список
  пусть итог равно свёртка («Обратить» от цифры) начиная с начальное как акк и цифра
    пусть сумма равно цифра плюс акк.перенос
    пусть новая равно сумма остаток от 10
    пусть дальше равно если сумма не меньше 10 то 1 иначе 0
    запись «Перенос» с перенос равным дальше и цифры равным (добавить новая к акк.цифры)
  пусть результат равно «Обратить» от итог.цифры
  если итог.перенос равен 1
    то «Приписать в начало» от 1 и результат
    иначе результат

модуль «Слияние отсортированных»

// LeetCode 88. Merge Sorted Array.
// Слить два отсортированных списка в один отсортированный.
//
// Тотальная — но не тем алгоритмом, каким её пишут обычно. Классическое
// слияние рекурсирует то по первому списку, то по второму, и анализ
// завершаемости такой цикл отвергает: он требует ОДНУ позицию аргумента,
// убывающую на каждом рекурсивном вызове (totality.mjs, контрпример в шапке
// файла). Слияние даёт две разные позиции и получает FLANG_NOT_TOTAL.
//
// Поэтому здесь слияние вставками: «Вставить по порядку» рекурсирует ровно
// по хвосту второго аргумента, а внешний проход — свёртка. Результат тот же,
// сложность O(n·m) вместо O(n+m).

тотальная функция «Приписать в начало»
  принимает первый: число, элементы: список числа
  возвращает список числа
  пример «В непустой»
    дано первый равно 1
    дано элементы равно [2]
    ожидается [1, 2]
  свёртка элементы начиная с [первый] как акк и эл → добавить эл к акк

тотальная функция «Вставить по порядку»
  принимает значение: число, элементы: список числа
  возвращает список числа
  пример «В середину»
    дано значение равно 2
    дано элементы равно [1, 3]
    ожидается [1, 2, 3]
  пример «В пустой»
    дано значение равно 2
    дано элементы равно пустой список
    ожидается [2]
  разбор элементов
    случай пусто
      то [значение]
    случай голова и хвост
      если значение не больше голова
        то «Приписать в начало» от значение и элементы
        иначе «Приписать в начало» от голова и («Вставить по порядку» от значение и хвост)

тотальная функция «Слить отсортированные»
  принимает первый: список числа, второй: список числа
  возвращает список числа
  пример «Пример 1 из условия»
    дано первый равно [1, 2, 3]
    дано второй равно [2, 5, 6]
    ожидается [1, 2, 2, 3, 5, 6]
  пример «Пример 2 из условия»
    дано первый равно [1]
    дано второй равно пустой список
    ожидается [1]
  пример «Пример 3 из условия»
    дано первый равно пустой список
    дано второй равно [1]
    ожидается [1]
  свёртка второй начиная с первый как акк и эл → «Вставить по порядку» от эл и акк

модуль «Глубина дерева»

// LeetCode 104. Maximum Depth of Binary Tree.
// Найти длину самого длинного пути от корня до листа.
//
// Тотальная. Дерево — сумма типов, а поле варианта анализ завершаемости
// считает частью значения, поэтому рекурсия по поддеревьям доказывается
// сразу и без ухищрений. Деревья язык принимает лучше, чем строки и числа.
//
// Дерево в примерах строится из списка: значение варианта нельзя записать
// в «дано» (парсер теряет имя конструктора), поэтому вход задаётся списком,
// а «Дерево из списка» превращает его в дерево поиска.

тип «Дерево»
  вариант Лист
  вариант Узел содержит значение: число, левое: «Дерево», правое: «Дерево»

тотальная функция «Вставить в дерево»
  принимает дерево: «Дерево», число: число
  возвращает «Дерево»
  разбор дерева
    случай Лист
      то Узел с значение равным число и левое равным вариант Лист и правое равным вариант Лист
    случай вариант Узел с значение как зн и левое как л и правое как п
      если число меньше зн
        то
          пусть новое равно «Вставить в дерево» от л и число
          Узел с значение равным зн и левое равным новое и правое равным п
        иначе
          пусть новое равно «Вставить в дерево» от п и число
          Узел с значение равным зн и левое равным л и правое равным новое

тотальная функция «Дерево из списка»
  принимает элементы: список числа
  возвращает «Дерево»
  свёртка элементы начиная с вариант Лист как акк и эл → «Вставить в дерево» от акк и эл

тотальная функция «Глубина»
  принимает дерево: «Дерево»
  возвращает число
  разбор дерева
    случай Лист
      то 0
    случай вариант Узел с левое как л и правое как п
      пусть слева равно «Глубина» от л
      пусть справа равно «Глубина» от п
      1 плюс (если слева больше справа то слева иначе справа)

тотальная функция «Глубина из списка»
  принимает элементы: список числа
  возвращает число
  пример «Сбалансированное дерево»
    дано элементы равно [2, 1, 3]
    ожидается 2
  пример «Цепочка»
    дано элементы равно [1, 2, 3, 4]
    ожидается 4
  пример «Пустое дерево»
    дано элементы равно пустой список
    ожидается 0
  «Глубина» от («Дерево из списка» от элементы)

модуль «Сбалансированное дерево»

// LeetCode 110. Balanced Binary Tree.
// Проверить, что для каждого узла глубины поддеревьев отличаются не более
// чем на единицу.
//
// Тотальная. Логических «и» и «или» в языке нет (SPEC перечисляет только
// арифметику и сравнения), поэтому конъюнкция трёх условий записана
// вложенными «если» — читается длиннее, но означает ровно то же.

тип «Дерево»
  вариант Лист
  вариант Узел содержит значение: число, левое: «Дерево», правое: «Дерево»

тотальная функция «Вставить в дерево»
  принимает дерево: «Дерево», число: число
  возвращает «Дерево»
  разбор дерева
    случай Лист
      то Узел с значение равным число и левое равным вариант Лист и правое равным вариант Лист
    случай вариант Узел с значение как зн и левое как л и правое как п
      если число меньше зн
        то
          пусть новое равно «Вставить в дерево» от л и число
          Узел с значение равным зн и левое равным новое и правое равным п
        иначе
          пусть новое равно «Вставить в дерево» от п и число
          Узел с значение равным зн и левое равным л и правое равным новое

тотальная функция «Дерево из списка»
  принимает элементы: список числа
  возвращает «Дерево»
  свёртка элементы начиная с вариант Лист как акк и эл → «Вставить в дерево» от акк и эл

тотальная функция «Глубина»
  принимает дерево: «Дерево»
  возвращает число
  разбор дерева
    случай Лист
      то 0
    случай вариант Узел с левое как л и правое как п
      пусть слева равно «Глубина» от л
      пусть справа равно «Глубина» от п
      1 плюс (если слева больше справа то слева иначе справа)

тотальная функция «Сбалансировано»
  принимает дерево: «Дерево»
  возвращает признак
  разбор дерева
    случай Лист
      то да
    случай вариант Узел с левое как л и правое как п
      если («Сбалансировано» от л) равен нет
        то нет
        иначе
          если («Сбалансировано» от п) равен нет
            то нет
            иначе
              пусть разница равно («Глубина» от л) минус («Глубина» от п)
              если разница меньше 0
                то (0 минус разница) не больше 1
                иначе разница не больше 1

тотальная функция «Сбалансировано для списка»
  принимает элементы: список числа
  возвращает признак
  пример «Сбалансированное дерево»
    дано элементы равно [2, 1, 3]
    ожидается да
  пример «Цепочка не сбалансирована»
    дано элементы равно [1, 2, 3, 4]
    ожидается нет
  пример «Пустое дерево сбалансировано»
    дано элементы равно пустой список
    ожидается да
  «Сбалансировано» от («Дерево из списка» от элементы)

модуль «Лучшая сделка»

// LeetCode 121. Best Time to Buy and Sell Stock.
// По списку цен по дням найти наибольшую прибыль от одной покупки и одной
// последующей продажи. Если прибыли нет — ноль.
//
// Тотальная: один проход свёрткой, состояние — запись из двух чисел
// (минимальная цена и лучшая прибыль).

объект «Сделка»
  минимум является числом
  прибыль является числом

тотальная функция «Лучшая прибыль»
  принимает цены: список числа
  возвращает число
  пример «Пример 1 из условия»
    дано цены равно [7, 1, 5, 3, 6, 4]
    ожидается 5
  пример «Пример 2 из условия»
    дано цены равно [7, 6, 4, 3, 1]
    ожидается 0
  пример «Пустой список»
    дано цены равно пустой список
    ожидается 0
  разбор цены
    случай пусто
      то 0
    случай голова и хвост
      пусть начальное равно запись «Сделка» с минимум равным голова и прибыль равным 0
      пусть итог равно свёртка хвост начиная с начальное как акк и цена
        пусть минимум равно если цена меньше акк.минимум то цена иначе акк.минимум
        пусть сегодня равно цена минус акк.минимум
        пусть прибыль равно если сегодня больше акк.прибыль то сегодня иначе акк.прибыль
        запись «Сделка» с минимум равным минимум и прибыль равным прибыль
      итог.прибыль

модуль «Одиночное число»

// LeetCode 136. Single Number.
// В списке каждое число встречается дважды, кроме одного. Найти его.
//
// Тотальная. Канонического решения «сложить всё исключающим ИЛИ» здесь нет:
// побитовых операций в языке нет вообще (SPEC, раздел 4 перечисляет только
// арифметику и сравнения). Поэтому — подсчёт вхождений, O(n²) вместо O(n).

тотальная функция «Считать вхождения»
  принимает элементы: список числа, значение: число
  возвращает число
  пример «Два вхождения»
    дано элементы равно [4, 1, 4]
    дано значение равно 4
    ожидается 2
  свёртка элементы начиная с 0 как акк и эл → если эл равен значение то акк плюс 1 иначе акк

тотальная функция «Одиночное число»
  принимает элементы: список числа
  возвращает число
  пример «Пример 1 из условия»
    дано элементы равно [2, 2, 1]
    ожидается 1
  пример «Пример 2 из условия»
    дано элементы равно [4, 1, 2, 1, 2]
    ожидается 4
  пример «Пример 3 из условия»
    дано элементы равно [1]
    ожидается 1
  пусть одиночные равно отфильтровать элементы где эл → («Считать вхождения» от элементы и эл) равен 1
  разбор одиночные
    случай пусто
      то 0
    случай голова и хвост
      голова

модуль «Мажоритарный элемент»

// LeetCode 169. Majority Element.
// Найти элемент, встречающийся более чем в половине позиций списка.
//
// Тотальная. Алгоритм Бойера — Мура здесь не нужен: без изменяемых счётчиков
// он всё равно свёлся бы к свёртке с записью-состоянием, а прямой подсчёт
// вхождений короче и очевидно верен. Цена — O(n²).

тотальная функция «Считать вхождения»
  принимает элементы: список числа, значение: число
  возвращает число
  пример «Три тройки»
    дано элементы равно [3, 3, 3, 1]
    дано значение равно 3
    ожидается 3
  свёртка элементы начиная с 0 как акк и эл → если эл равен значение то акк плюс 1 иначе акк

тотальная функция «Мажоритарный элемент»
  принимает элементы: список числа
  возвращает число
  пример «Пример 1 из условия»
    дано элементы равно [3, 2, 3]
    ожидается 3
  пример «Пример 2 из условия»
    дано элементы равно [2, 2, 1, 1, 1, 2, 2]
    ожидается 2
  пусть половина равно (длина элементы) делить на 2
  пусть частые равно отфильтровать элементы где эл → («Считать вхождения» от элементы и эл) больше половина
  разбор частые
    случай пусто
      то 0
    случай голова и хвост
      голова

модуль «Есть повторы»

// LeetCode 217. Contains Duplicate.
// Есть ли в списке хотя бы одно значение, встречающееся дважды.
//
// Тотальная: рекурсия строго по хвосту списка. Множества в языке нет,
// поэтому проверка «голова встречается дальше» — линейный поиск,
// и всё решение получается O(n²).

тотальная функция «Есть повторы»
  принимает элементы: список числа
  возвращает признак
  пример «Пример 1 из условия»
    дано элементы равно [1, 2, 3, 1]
    ожидается да
  пример «Пример 2 из условия»
    дано элементы равно [1, 2, 3, 4]
    ожидается нет
  пример «Пример 3 из условия»
    дано элементы равно [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
    ожидается да
  разбор элементов
    случай пусто
      то нет
    случай голова и хвост
      если хвост содержит голова то да иначе «Есть повторы» от хвоста

модуль «Развернуть дерево»

// LeetCode 226. Invert Binary Tree.
// Поменять местами левое и правое поддерево у каждого узла.
//
// Тотальная. Само «Развернуть» примера иметь не может: оно возвращает
// вариант, а значение варианта в «ожидается» не записывается — парсер
// разворачивает конструктор в запись из его полей и теряет имя варианта.
// Поэтому проверяется наблюдаемое следствие: обход по возрастанию до и после
// разворота. У дерева поиска обход по порядку отсортирован, у развёрнутого —
// отсортирован в обратную сторону.

тип «Дерево»
  вариант Лист
  вариант Узел содержит значение: число, левое: «Дерево», правое: «Дерево»

тотальная функция «Соединить списки»
  принимает первый: список числа, второй: список числа
  возвращает список числа
  пример «Склейка»
    дано первый равно [1]
    дано второй равно [2, 3]
    ожидается [1, 2, 3]
  свёртка второй начиная с первый как акк и эл → добавить эл к акк

тотальная функция «Вставить в дерево»
  принимает дерево: «Дерево», число: число
  возвращает «Дерево»
  разбор дерева
    случай Лист
      то Узел с значение равным число и левое равным вариант Лист и правое равным вариант Лист
    случай вариант Узел с значение как зн и левое как л и правое как п
      если число меньше зн
        то
          пусть новое равно «Вставить в дерево» от л и число
          Узел с значение равным зн и левое равным новое и правое равным п
        иначе
          пусть новое равно «Вставить в дерево» от п и число
          Узел с значение равным зн и левое равным л и правое равным новое

тотальная функция «Дерево из списка»
  принимает элементы: список числа
  возвращает «Дерево»
  свёртка элементы начиная с вариант Лист как акк и эл → «Вставить в дерево» от акк и эл

тотальная функция «Развернуть»
  принимает дерево: «Дерево»
  возвращает «Дерево»
  разбор дерева
    случай Лист
      то вариант Лист
    случай вариант Узел с значение как зн и левое как л и правое как п
      пусть слева равно «Развернуть» от п
      пусть справа равно «Развернуть» от л
      Узел с значение равным зн и левое равным слева и правое равным справа

тотальная функция «Обход по порядку»
  принимает дерево: «Дерево»
  возвращает список числа
  разбор дерева
    случай Лист
      то пустой список
    случай вариант Узел с значение как зн и левое как л и правое как п
      пусть слева равно «Обход по порядку» от л
      пусть справа равно «Обход по порядку» от п
      «Соединить списки» от (добавить зн к слева) и справа

тотальная функция «Обход дерева из списка»
  принимает элементы: список числа
  возвращает список числа
  пример «Дерево поиска обходится по возрастанию»
    дано элементы равно [4, 2, 7, 1, 3, 6, 9]
    ожидается [1, 2, 3, 4, 6, 7, 9]
  «Обход по порядку» от («Дерево из списка» от элементы)

тотальная функция «Обход после разворота»
  принимает элементы: список числа
  возвращает список числа
  пример «Пример 1 из условия»
    дано элементы равно [4, 2, 7, 1, 3, 6, 9]
    ожидается [9, 7, 6, 4, 3, 2, 1]
  пример «Пример 2 из условия»
    дано элементы равно [2, 1, 3]
    ожидается [3, 2, 1]
  пример «Пустое дерево»
    дано элементы равно пустой список
    ожидается пустой список
  «Обход по порядку» от («Развернуть» от («Дерево из списка» от элементы))

модуль «Анаграмма»

// LeetCode 242. Valid Anagram.
// Проверить, что второе слово — перестановка первого. По условию буквы
// только строчные латинские.
//
// Тотальная — и это неожиданно, потому что задача про строки. Приём:
// считать буквы не обходом строки, а встроенной «разделить». Число вхождений
// буквы равно числу частей минус один, а перебирать надо не символы слова,
// а заранее известный алфавит из 26 букв — конечный список, записанный
// литералом. Свёртка по литеральному списку тотальна всегда.

тотальная функция «Счёт буквы»
  принимает текст: строка, буква: строка
  возвращает число
  пример «Две буквы a»
    дано текст равно "abac"
    дано буква равно "a"
    ожидается 2
  пример «Буквы нет»
    дано текст равно "bbb"
    дано буква равно "a"
    ожидается 0
  (длина (разделить текст по буква)) минус 1

тотальная функция «Анаграмма»
  принимает первое: строка, второе: строка
  возвращает признак
  пример «Пример 1 из условия»
    дано первое равно "anagram"
    дано второе равно "nagaram"
    ожидается да
  пример «Пример 2 из условия»
    дано первое равно "rat"
    дано второе равно "car"
    ожидается нет
  пример «Разная длина»
    дано первое равно "a"
    дано второе равно "ab"
    ожидается нет
  если (длина первое) не равен (длина второе)
    то нет
    иначе
      свёртка ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"] начиная с да как акк и буква
        если акк равен нет
          то нет
          иначе («Счёт буквы» от первое и буква) равен («Счёт буквы» от второе и буква)

модуль «Пропущенное число»

// LeetCode 268. Missing Number.
// В списке лежат все числа от 0 до n, кроме одного. Найти пропущенное.
//
// Тотальная и без рекурсии: сумма арифметической прогрессии минус сумма
// списка. Здесь язык не мешает вовсе — вся задача выражается двумя свёртками
// и арифметикой.

тотальная функция «Сумма»
  принимает элементы: список числа
  возвращает число
  пример «Сумма трёх»
    дано элементы равно [1, 2, 3]
    ожидается 6
  свёртка элементы начиная с 0 как акк и эл → акк плюс эл

тотальная функция «Пропущенное число»
  принимает элементы: список числа
  возвращает число
  пример «Пример 1 из условия»
    дано элементы равно [3, 0, 1]
    ожидается 2
  пример «Пример 2 из условия»
    дано элементы равно [0, 1]
    ожидается 2
  пример «Пример 3 из условия»
    дано элементы равно [9, 6, 4, 2, 3, 5, 7, 0, 1]
    ожидается 8
  пусть предел равно длина элементы
  пусть полная равно (предел умножить на (предел плюс 1)) делить на 2
  полная минус («Сумма» от элементы)

модуль «Сдвинуть нули»

// LeetCode 283. Move Zeroes.
// Перенести все нули в конец, сохранив порядок остальных.
//
// Тотальная и без единой рекурсии: два фильтра и склейка. В условии просят
// работать «на месте», но изменяемых массивов в языке нет — возвращается
// новый список того же содержания.

тотальная функция «Соединить списки»
  принимает первый: список числа, второй: список числа
  возвращает список числа
  пример «Склейка»
    дано первый равно [1]
    дано второй равно [0, 0]
    ожидается [1, 0, 0]
  свёртка второй начиная с первый как акк и эл → добавить эл к акк

тотальная функция «Сдвинуть нули»
  принимает элементы: список числа
  возвращает список числа
  пример «Пример 1 из условия»
    дано элементы равно [0, 1, 0, 3, 12]
    ожидается [1, 3, 12, 0, 0]
  пример «Пример 2 из условия»
    дано элементы равно [0]
    ожидается [0]
  пусть ненулевые равно отфильтровать элементы где эл → эл не равен 0
  пусть нули равно отфильтровать элементы где эл → эл равен 0
  «Соединить списки» от ненулевые и нули

модуль «Обратить строку»

// LeetCode 344. Reverse String.
// Условие даёт массив символов и просит обратить его на месте. Массив
// символов — это список строки, и здесь это удача: список flang разбирается
// структурно, а строка нет. Поэтому задача остаётся тотальной, тогда как
// та же операция над строкой (модуль stdlib/strings.flang) тотальной быть
// не может — по строке нельзя рекурсировать с доказательством убывания.
//
// Изменения на месте нет и не будет: значения flang неизменяемы.

тотальная функция «Приписать строку в начало»
  принимает первая: строка, элементы: список строки
  возвращает список строки
  пример «В непустой»
    дано первая равно "а"
    дано элементы равно ["б"]
    ожидается ["а", "б"]
  свёртка элементы начиная с [первая] как акк и эл → добавить эл к акк

тотальная функция «Обратить символы»
  принимает символы: список строки
  возвращает список строки
  пример «Пример 1 из условия»
    дано символы равно ["h", "e", "l", "l", "o"]
    ожидается ["o", "l", "l", "e", "h"]
  пример «Пример 2 из условия»
    дано символы равно ["H", "a", "n", "n", "a", "h"]
    ожидается ["h", "a", "n", "n", "a", "H"]
  пример «Пустой список»
    дано символы равно пустой список
    ожидается пустой список
  свёртка символы начиная с пустой список как акк и буква → «Приписать строку в начало» от буква и акк

тотальная функция «Строка из символов»
  принимает символы: список строки
  возвращает строка
  пример «Склейка»
    дано символы равно ["o", "l", "l", "e", "h"]
    ожидается "olleh"
  свёртка символы начиная с "" как акк и буква → соединить акк с буква

модуль «Пересечение списков»

// LeetCode 349. Intersection of Two Arrays.
// Вернуть уникальные значения, встречающиеся в обоих списках.
//
// Тотальная: два прохода свёрткой и фильтром, рекурсии нет.
// Множеств в языке нет, «уникальность» строится вручную через «содержит».

тотальная функция «Уникальные»
  принимает элементы: список числа
  возвращает список числа
  пример «С повторами»
    дано элементы равно [1, 1, 2]
    ожидается [1, 2]
  свёртка элементы начиная с пустой список как акк и эл
    если акк содержит эл то акк иначе добавить эл к акк

тотальная функция «Пересечение»
  принимает первый: список числа, второй: список числа
  возвращает список числа
  пример «Пример 1 из условия»
    дано первый равно [1, 2, 2, 1]
    дано второй равно [2, 2]
    ожидается [2]
  пример «Пример 2 из условия»
    дано первый равно [4, 9, 5]
    дано второй равно [9, 4, 9, 8, 4]
    ожидается [4, 9]
  отфильтровать («Уникальные» от первый) где эл → второй содержит эл

модуль «Двоичный поиск»

// LeetCode 704. Binary Search.
// В отсортированном списке найти номер цели (с нуля) или −1.
//
// Тотальная — но приёмом, который стоит запомнить, потому что он показывает
// границу анализа завершаемости. Двоичный поиск сужает пару чисел «низ» и
// «верх», а убывание по числам totality.mjs не признаёт: «середина плюс 1» —
// результат арифметики, а не часть значения. Прямая запись даёт
// FLANG_NOT_TOTAL.
//
// Обход: рядом с настоящими аргументами едет «топливо» — список, у которого
// на каждом шаге берётся хвост. Топливо убывает структурно, значит цикл
// доказуемо конечен; а поскольку топливом служит сам список, шагов заведомо
// хватает (их нужно log₂n, а есть n). Приём честный, но это именно приём:
// в языке не хватает убывания по мере.

тотальная функция «Элемент»
  принимает элементы: список числа, номер: число
  возвращает число
  пример «Второй элемент»
    дано элементы равно [10, 20, 30]
    дано номер равно 2
    ожидается 20
  разбор элементов
    случай пусто
      то 0
    случай голова и хвост
      если номер не больше 1
        то голова
        иначе «Элемент» от хвост и (номер минус 1)

тотальная функция «Поиск в диапазоне»
  принимает топливо: список числа, элементы: список числа, цель: число, низ: число, верх: число
  возвращает число
  пример «Нашли середину»
    дано топливо равно [1, 2, 3]
    дано элементы равно [1, 2, 3]
    дано цель равно 2
    дано низ равно 1
    дано верх равно 3
    ожидается 1
  разбор топливо
    случай пусто
      то -1
    случай голова и хвост
      если низ больше верх
        то -1
        иначе
          пусть сумма равно низ плюс верх
          пусть середина равно (сумма минус (сумма остаток от 2)) делить на 2
          пусть значение равно «Элемент» от элементы и середина
          если значение равен цель
            то середина минус 1
            иначе
              если значение меньше цель
                то «Поиск в диапазоне» от хвост и элементы и цель и (середина плюс 1) и верх
                иначе «Поиск в диапазоне» от хвост и элементы и цель и низ и (середина минус 1)

тотальная функция «Двоичный поиск»
  принимает элементы: список числа, цель: число
  возвращает число
  пример «Пример 1 из условия»
    дано элементы равно [-1, 0, 3, 5, 9, 12]
    дано цель равно 9
    ожидается 4
  пример «Пример 2 из условия»
    дано элементы равно [-1, 0, 3, 5, 9, 12]
    дано цель равно 2
    ожидается -1
  пример «Один элемент»
    дано элементы равно [5]
    дано цель равно 5
    ожидается 0
  «Поиск в диапазоне» от элементы и элементы и цель и 1 и (длина элементы)