Сравнение подходов в реализации алгоритмов на C++ и Haskell

Классический пример краткой и ясной реализации алгоритма на Haskell - это быстрая сортировка:

quickSort [] = []
quickSort (x:xs) = quickSort [ y | y <- xs, y < x ] ++ [ x ] ++
                   quickSort [ y | y <- xs, y >= x ]

Обычно рядом с этим кодом приводят какую-нибудь 20-строчную реализацию быстрой сортировки на C или C++. И конечно же сравнение идёт не в пользу C++. Откровенно говоря, здесь заключена немалая доля лукавства: как можно сравнивать высокоуровневые определители списков (list comprehensions - выражения в квадратных скобках в данном примере) с низкоуровневыми итерациями в коде C++? С другой стороны, определители списков являются встроенным механизмом Haskell, поэтому подобное сравнение всё-таки допустимо.

Ниже приводятся реализации одного алгоритма на C++ и Haskell. Алгоритм был взят из книги Ф. Меньшикова "Олимпиадные задачи по программированию". Задача формулируется следующим образом:

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

Базовый алгоритм для решения этой задачи приводится в этой же книге:

Начиная с первого элемента последовательности и заканчивая последним найти максимальную длину возрастающей подпоследовательности из предшествующих элементов, меньших данного, и прибавить к ней 1. Эта величина будет соответствовать максимальной длине возрастающей подпоследовательности, которую можно построить начиная с 1-ого элемента исходной последовательность вплоть до данного элемента. Так, для 1-ого элемента последовательности из предшествующих элементов не существует, поэтому ему соответствует длина 1. Для произвольного i-ого элемента нужно совершить обратный проход к началу последовательности, найти меньший по значению элемент с максимальным значением длины и прибавить к нему 1. После того как длины найдены (при условии, что они сохранены в некотором вспомогательном массиве), нужно в исходной последовательности найти элемент, которому соответствует  максимальное значение длины и, двигаясь к началу последовательности, находить первые элементы, для которых соответствующая длина уменьшилась на единицу. Эти элементы (вместе с исходным) и будут составлять искомую подпоследовательность наибольшей длины.

Несколько замечаний. Во-первых, существуют модификации этого алгоритма, в которых финальный проход от элемента, которому соответствует максимальная длина возрастающей подпоследовательности к началу исходной последовательности не требуется. Поскольку моей целью является не написание самого оптимального алгоритма, а качественное сравнение подобных реализаций на C++ и Haskell, то я использовал базовый алгоритм. Во-вторых, очевидно, что в базовом варианте класс этого алгоритма соответствует O(n^2), так как присутствуют вложенные итерации (обратные проходы к началу последовательности) внутри базовой итерации по всем элементам. В-третьих, могут существовать несколько подпоследовательностей максимальной длины, нам нужно выбрать любую из них.

Итак, реализация этого алгоритма на C++ выглядит следующим образом:

typedef std::vector< int >  VIn;

typedef VIn::value_type     VInElem;

typedef std::vector< int >  VCnt;

void  findLongestIncSeq( const VIn &  vIn, VIn &  vRes )
{
    VCnt                 vCnt( vIn.size() );
    VCnt::iterator       vCntIt( vCnt.begin() );
    VIn::const_iterator  vMaxIt( vIn.begin() );
    VCnt::iterator       vCntMaxIt( vCnt.begin() );
    int                  maxLen( 0 );

    for ( VIn::const_iterator  k( vIn.begin() ); k != vIn.end(); ++k, ++vCntIt )
    {
        int                           maxVal( 0 );
        VCnt::const_reverse_iterator  vCntBackIt( vCntIt );

        for ( VIn::const_reverse_iterator  l( k ); l != vIn.rend();
                                                            ++l, ++vCntBackIt )
        {
            if ( *k <= *l )
                continue;

            if ( *vCntBackIt > maxVal )
                maxVal = *vCntBackIt;
        }

        *vCntIt = maxVal + 1;
        if ( *vCntIt > maxLen )
        {
            maxLen = *vCntIt;
            vMaxIt = k;
            vCntMaxIt = vCntIt;
        }
    }

    std::cout << "Lengths:  ";
    printVec( vCnt );

    if ( vMaxIt == vIn.begin() )
        return;

    std::stack< VInElem >   reverseSeq;
    VCnt::reverse_iterator  vCntBackIt( vCntMaxIt + 1 );

    for ( VIn::const_reverse_iterator  k( vMaxIt + 1 ); k != vIn.rend();
                                                            ++k, ++vCntBackIt )
    {
        if ( *vCntBackIt == maxLen )
        {
            reverseSeq.push( *k );
            --maxLen;
        }
    }

    while ( ! reverseSeq.empty() )
    {
        vRes.push_back( reverseSeq.top() );
        reverseSeq.pop();
    }
}

Вспомогательная функция printVec() реализуется так:

template  < typename  VElem >
struct  PrintVec
{
    void  operator()( VElem  value )
    {
        std::cout << value << " ";
    }
};

template  < typename  Vec >
void  printVec( Vec  v )
{
    std::for_each( v.begin(), v.end(), PrintVec< typename Vec::value_type >() );
    std::cout << std::endl;
}

В функцию findLongestIncSeq() передаются ссылки на исходную последовательность vIn и последовательность vRes, которую нужно заполнить. Внутри функции создаем вспомогательный массив целых чисел vCnt, в котором будем хранить длины максимальной возрастающей последовательности до i-ого элемента включительно. Внутри первого цикла for происходит основная итерация, в которой заполняется массив vCnt, кроме того попутно вычисляются максимальная длина возрастающей подпоследовательности maxLen и соответствующие ей элементы в vIn и vCnt: vMaxIt и vCntMaxIt - они будут нужны для определения элемента, с которого нужно начать финальный проход по исходной последовательности вниз к первому элементу. Этот финальный проход осуществляется в последнем цикле for функции findLongestIncSeq(), в котором заполняется вспомогательный стек reverseSeq. Теперь, чтобы заполнить искомую последовательность vRes, нужно опустошить reverseSeq и сложить его элементы в vRes, что и происходит в последнем цикле while.

Я не буду приводить функцию main() - это детали. Укажу только, что для тестовой последовательности [67 5 34 89 65 12 90 75 8 9 3] выводится следующий результат:

Original: 67 5 34 89 65 12 90 75 8 9 3 
Lengths:  1 1 2 3 3 2 4 4 2 3 1 
Sequence: 5 34 65 90

В строке Original выводится исходная последовательность, в строке Lengths - вспомогательная последовательность длин возрастающих подпоследовательностей, а в строке Sequence - результирующая возрастающая подпоследовательность максимальной длины.

А теперь внимание. Подобный алгоритм написанный на Haskell (я привожу весь код вместе с тестовой частью, так что его можно сразу скомпилировать):

{-find longest increasing subsequence-}

getPrevLength [] = 0
getPrevLength x  = maximum $ doGetLengths x

doGetLengths []     = []
doGetLengths (x:xs) = getPrevLength [ y | y <- xs, y < x ] + 1 : doGetLengths xs

getLengths = reverse . doGetLengths . reverse

doCutTail [] _                                          = []
doCutTail a@(x:xs) maxLen
    | getPrevLength [ y | y <- xs, y < x ] + 1 < maxLen = doCutTail xs maxLen
    | otherwise                                         = a

cutTail [] = []
cutTail x  = reverse $ doCutTail ( reverse x ) ( maximum $ getLengths x )

doFindLongestIncSec' [] _   = []
doFindLongestIncSec' (x:xs) maxLen
    | maxLen - prevLen == 1 = x : doFindLongestIncSec' xs prevLen
    | otherwise             = doFindLongestIncSec' xs maxLen
        where prevLen = getPrevLength [ y | y <- xs, y < x ] + 1

doFindLongestIncSec [] = []
doFindLongestIncSec x  =
    doFindLongestIncSec' ( reverse x ) ( maximum ( getLengths x ) + 1 )

findLongestIncSec = reverse . doFindLongestIncSec . cutTail

{-do some testing-}

doTest x = do
    putStrLn $ "Original: " ++ show x
    putStrLn $ "Lengths:  " ++ ( show $ getLengths x )
    putStrLn $ "Trimmed:  " ++ ( show $ cutTail x )
    putStrLn $ "Sequence: " ++ ( show $ findLongestIncSec x )

main = mapM_ doTest [ [ 10, 5, 89, 16, 78, 67, 56, 34, 12, 10 ],
                      [ 67, 5, 34, 89, 65, 12, 90, 75, 8, 9, 3 ] ]

Я назвал этот алгоритм подобным, поскольку его невозможно реализовать тем же самым способом, что и в C++ (во всяком случае без использования монад). В Haskell отсутствуют итерации и состояния (то бишь переменные), и это означает, что создать вспомогательный массив длин подпоследовательностей и использовать его на том же уровне программного потока не удастся. По той же причине невозможно сначала запомнить индекс элемента с максимальным значением возрастающей подпоследовательности, а затем использовать его по своему усмотрению в параллельной последовательности вызовов функций. В Haskell возможность параллельной последовательности вызовов функций появляется только с использованием монад (см. реализацию doTest выше), а в общем случае вызовы функций могут быть только вложены друг в друга. Это означает, что обычно решение любой задачи в Haskell представляет собой вызов единственной функции, которая в свою очередь вызывает единственную функцию и т.д. Это создает впечатление решения одним махом. В самом деле, в приведенном коде всё решение заключается в вызове единственной функции findLongestIncSeq x. Параллельные вызовы getLengths и cutTail, организованные в doTest нужны только для демонстрации промежуточных состояний исходной последовательности и никоим образом не влияют на результат финального вызова findLongestIncSeq.

Приведенные выше особенности программирования на Haskell требуют более частого использования рекурсивных вызовов, чем в C++, где рекурсия чаще всего заменяется итерацией. Так, функция getPrevLength, которая используется в программе для поиска длины максимальной подпоследовательности, является косвенно рекурсивной благодаря вызову doGetLengths, которая в свою очередь является рекурсивной и косвенно, и явно. Функция cutTail возвращает подпоследовательность исходной последовательности от начала до последнего элемента, которому соответствует максимальная длина возрастающей подпоследовательности. Основная функция findLongestIncSeq является композицией функций reverse, doFindLongestIncSeq и cutTail - это отражено в ее определении.

Нельзя не заметить, что в коде часто употребляется обращение последовательности с помощью reverse. Если учесть, что скорость reverse должна соответствовать O(n), это должно настораживать. Проблема в том, что семантика конструктора списков Haskell предполагает добавление элементов в начало, а не в конец списка, а в нашем алгоритме чаще всего приходится выделять последний элемент подпоследовательности и проходить вниз к началу списка. Таким образом, от reverse можно избавиться, видоизменив исходный алгоритм. Однако проблема обращения списка не такая уж серьезная, как кажется сначала. Дело в том, что reverse не вызывается рекурсивно, а только счётное количество раз, соответственно общая скорость алгоритма остается прежней - O(n^2).

Еще одно важное замечание. Что если мы захотим изменить тип элементов последовательности? Например, захотим искать максимальную подпоследовательность вещественных чисел или строк. В коде на C++ такой вариант предусмотрен с помощью объявления типов VIn и VInElem - стоит поменять тип элемента вектора и всё должно заработать. В коде на Haskell вообще ничего менять не нужно! И это не потому, что в Haskell нет статической проверки типов данных, она там есть, причем более сильная, чем в C++. Просто в данном случае работает параметрический полиморфизм, реализованный в Haskell.
Осталось привести вывод программы на Haskell:

Original: [10,5,89,16,78,67,56,34,12,10]
Lengths:  [1,1,2,2,3,3,3,3,2,2]
Trimmed:  [10,5,89,16,78,67,56,34]
Sequence: [5,16,34]
Original: [67,5,34,89,65,12,90,75,8,9,3]
Lengths:  [1,1,2,3,3,2,4,4,2,3,1]
Trimmed:  [67,5,34,89,65,12,90,75]
Sequence: [5,34,65,75]

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