Лаборатория Математики и Программирования Сергея Бобровского: “Пример, как работает мой агент. Вот я загнал в него ценный пейпер "Rec…”

Пример, как работает мой агент. Вот я загнал в него ценный пейпер "Recursive Program Synthesis using Paramorphisms".

Как пишут рекурсию 98% программистов:

int SumPositiveNodes(Node node)
{
    if (node == null) return 0;

    int left = SumPositiveNodes(node.Left);
    int right = SumPositiveNodes(node.Right);

    int self = node.Value > 0 ? node.Value : 0;
    return self + left + right;
}

Вот как напишут 2% ребят с хорошим университетским образованием (и кто вдумчиво решал мои доп.задачки на второй части АСД :) =>

int FoldTree(Node node, Func<Node, int, int, int> f, int seed)
{
    if (node == null) return seed;
    int left = FoldTree(node.Left, f, seed);
    int right = FoldTree(node.Right, f, seed);
    return f(node, left, right);
}

int SumPositiveNodes(Node root)
{
    // чистая нерекурсивная логика
    return FoldTree(root, (n, l, r) =>
    {
        int self = n.Value > 0 ? n.Value : 0;
        return self + l + r;
    }, 0);
}

Да, но это пока классический fold (катаморфизм), когда достаточно только одного результата.

Параморфизм требуется, когда в рекурсивной ветке нам нужно также иметь доступ к самой структуре (хвосту/поддереву).

ListNode DropLast(ListNode list)
{
    if (list == null) return null;
    if (list.Next == null) return null;

    return new ListNode(list.Value, DropLast(list.Next));
}

TOut Para<TOut>(ListNode list,
                Func<int, ListNode, TOut, TOut> cons,
                TOut nil)
{
    if (list == null) return nil;
    var rec = Para(list.Next, cons, nil);
    return cons(list.Value, list.Next, rec);
}

ListNode DropLast(ListNode list)
{
    return Para(list, (head, tail, rec) =>
    {
        if (tail == null) return null;
        return new ListNode(head, rec);
    }, null);
}

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

Вот в чём сермяга: Para -- это универсальный рекурсивный каркас (порядок обхода и базовые случаи единообразны), который мы тестируем 1 раз.

Далее нам достаточно только проверять нерекурсивную логику внутри различных cons под этот паттерн в нашем проекте.

+ можем использовать Para как fold:

int SumPositive(ListNode list)
{
    return Para(list, (head, tail, rec) =>
    {
        int self = head > 0 ? head : 0;
        return self + rec;
    }, 0);
}

Где это полезно? В работе со списками и деревьями, в обработке json и подобных структур, в ETL - сокращаем кучу рекурсивного кода (возможно, вообще до одного параморфизма), а добавлять новую логику можно императивно. Но это конечно уровень больше архитектурного code review.

К весне, надеюсь, кто у меня (пере)проходит тему АСД, бета-версия агента будет периодически делать такое ревью решений через клода4.6 и жпт5.3 (бесплатно).