Древовидная свертка списка (foldt)

Главная Форумы Программирование Язык Пифагор Примеры Древовидная свертка списка (foldt)

Помечено: , ,

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 2 нед., 6 дн. назад.

  • Автор
    Сообщения
  • #4171

    Сверткой списка (x1, x2, … xn) с функцией op является операция, результат которой формируется по правилу
    x1 <op> x2 <op> ... <op> xn

    В зависимости от порядка выполнения операций (слева или справа), во многих языках программирования существуют функции foldr и foldl. Однако, для ряда операций (например – сложение, умножение) порядок вычисления не важен и свертка может выполняться параллельно с помощью древовидной структуры. Реализация древовидной свертки на языке Пифагор:

    // древовидная свертка списка
    // ((x1,x2,...,xn), op):foldt -> x1 <op> x2 <op> ... <op> xn
    foldt << funcdef X {
      A << X:1;
      Operation << X:2;
      
      Len << A:|;
      [((Len,2):[<,=,>]):?]^    
      ( 
        {A:[]},
        {A:Operation},
        {
          block {
            OddVec << A:[(1,Len,2):..];
            EvenVec << A:[(2,Len,2):..];
            ([(OddVec, Operation),(EvenVec, Operation)]:foldt):Operation >> break
          }
        } 
      ):. >> return;
    }

    Если на вход подан список (A), длина которого (Len) меньше двух — соответствующий возвращается параллельный список (либо пустой список, либо — значение единственного элемента). Если же список A содержит ровно два элемента — над ними выполняется заданная операция (Operation), а полученный результат возвращается. Наконец, если длина списка больше двух — список A разделяется на две части (OddVec и EvenVec), содержащие, соответственно, элементы с четными и нечетными индексами. В результате рекурсивной обработки каждой из частей будет получено два значения — результата, над которыми также выполняется Operation для получения окончательного ответа.

    С помощью foldt может, в частности, реализовано эффективное, паралллельное вычисление суммы элементов списка:

    // сумма элементов списка
    sum_list << funcdef X {
      (X, +):foldt >> return;
    }

    Для тестирования (см. функцию equals) свертки использовался следующий код:

    test_foldt << funcdef {
      Cases << [
        ("sum_odd_length", ( ((1,2,3,4,5,6,7,8),+):foldt, 36):equals),
        ("mul_even_length", ( ((1,2,4),*):foldt, 8):equals)
      ];
      return << Cases;
    }

Для ответа в этой теме необходимо авторизоваться.