понедельник, 30 мая 2011 г.

CERN ROOT и надписи на русском языке

Как это ни странно, но проблема поддержки кириллицы в CERN ROOT действительно существует. Я не буду утверждать, что такая проблема присутствует в версии ROOT для Windows, но в Linux она актуальна. Однако, если учесть как эта поддержка реализована в нативной графической подсистеме ROOT, а также то, насколько глючно реализован Qt бекэнд, который поддерживает более широкий набор шрифтов, чем нативный вариант, такая проблема должна существовать и в Windows.

В качестве примера возьмем простой скрипт, с помощью которого можно создать следующее изображение:


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

void  createHisto( void )
{
    TCanvas *  c1 = new TCanvas();
    TH1 *      histo = new TH1F( "h1", "DCS vs. Energy", 10, 400., 600. );
    Double_t   content[] = { 0.0, 0.115, 0.145, 0.158, 0.170, 0.182, 0.180,
                             0.172, 0.154, 0.140, 0.132, 0.0 };
    Double_t   errors[] = { 0.0, 0.0015, 0.0012, 0.0008, 0.0016, 0.0023, 0.0018,
                            0.0013, 0.0014, 0.0006, 0.0002, 0.0 };
    histo->SetContent( content );
    histo->SetError( errors );
    histo->GetXaxis()->SetTitle( "E_{cm}, MeV" );
    histo->GetYaxis()->SetTitle( "d#sigma/d#Omega, mb/sr" );
    histo->SetStats( kFALSE );          // do not draw stats box
    histo->Draw();
    c1->SaveAs( "c1.eps" );
}

void histoTest( void )
{
    gROOT->SetStyle( "Plain" );
    gStyle->SetTitleBorderSize( 0 );    // do not draw frames around title
    gStyle->SetTitleOffset( 1.2, "xy" );// do not let axes' titles overlap ticks
    createHisto();
    if ( gROOT->IsBatch() )
        exit( 0 );
}
Обратите внимание, что в подписях к осям гистограммы используется вариант Latex для ROOT, стиль gStyle установлен в Plain, а рамка вокруг титула удалена. Отсутствие рамки вокруг титула упрощает решение задачи в первом и третьем подходах (см. ниже).

Для сохранения картинки наверху в файле c1.eps нужно создать скрипт histoTest.C с указанным содержимым и запустить root в пакетном режиме:
root -b histoTest.C
Пусть нашей задачей будет замена титула изображения на ДСР в зависимости от энергии и меток mb/sr, MeV и cm на мб/ср, МэВ и цм соответственно.

Наивная подстановка русских надписей в скрипт histoTest.C приведет к выводу в изображение c1.eps "кракозябр". Что же не так с ROOT? Нативный графический бэкенд ROOT не поддерживает кириллицу. Точка. Для решения проблемы ниже представлены три подхода, которые приводятся в порядке улучшения качества решения и полноты, хотя ни один из них не является идеальным. Идеи второго и третьего подходов взяты из обсуждений здесь и здесь.
  1. Наиболее простое решение - сохранить исходное изображение в векторном формате svg и отредактировать его в каком-нибудь векторном редакторе, например в inkscape. Минусы здесь очевидны. Редактировать придется вручную. Кроме изменения текста придется изменять обрамляющие его элементы, например компоненты рамки вокруг титула (которую мы предусмотрительно убрали в исходном скрипте).
  2. Использование Qt бэкенда (Qt layer) . Это был бы идеальный вариант, если бы не невообразимая глючность данного бэкенда. Из основных глюков стоит упомянуть: полупрозрачный или полностью прозрачный фон и шрифт абсолютно всех меню, невозможность использовать диалог сохранения файлов (!), невозможность сохранить валидное изображение в форматах eps и pdf (!). В данном подходе пришлось сохранять изображение как Save -> c1.png. Для использования Qt бэкенда нужно записать в файл ~/.rootrc следующие строки:
    Gui.Backend:                $(ROOTGUI)
    Gui.Factory:                $(ROOTGUI)
    Gui.DefaultFont:            -*-helvetica-medium-r-*-*-12-*-*-*-*-*-iso8859-5
    Gui.MenuFont:               -*-helvetica-medium-r-*-*-12-*-*-*-*-*-iso8859-5
    Gui.MenuHiFont:             -*-helvetica-bold-r-*-*-12-*-*-*-*-*-iso8859-5
    Gui.DocFixedFont:           -*-courier-medium-r-*-*-12-*-*-*-*-*-iso8859-5
    Gui.DocPropFont:            -*-helvetica-medium-r-*-*-12-*-*-*-*-*-iso8859-5
    Gui.IconFont:               -*-helvetica-medium-r-*-*-10-*-*-*-*-*-iso8859-5
    Gui.StatusFont:             -*-helvetica-medium-r-*-*-10-*-*-*-*-*-iso8859-5
    
    Использование переменной среды ROOTGUI позволяет сохранить нативный бэкенд по умолчанию (однако придется добавить строку
    export ROOTGUI=native
    
    в ~/.bash_profile). Для того, чтобы запустить root с Qt бэкендом нужно ввести
    ROOTGUI=qt root histoTest_qt.C
    
    Скрипт histoTest_qt.C выглядит так:
    void  createHisto( void )
    {
        //TCanvas *  c1 = new TCanvas();
        TH1 *      histo = new TH1F( "h1", "´ÁÀ Ò ×ÐÒØáØÜÞáâØ Þâ íÝÕàÓØØ",
                                     10, 400., 600. );
        Double_t   content[] = { 0.0, 0.115, 0.145, 0.158, 0.170, 0.182, 0.180,
                                 0.172, 0.154, 0.140, 0.132, 0.0 };
        Double_t   errors[] = { 0.0, 0.0015, 0.0012, 0.0008, 0.0016, 0.0023, 0.0018,
                                0.0013, 0.0014, 0.0006, 0.0002, 0.0 };
        histo->SetContent( content );
        histo->SetError( errors );
        histo->GetXaxis()->SetTitle( "E_{æÜ}, ¼í²" );
        histo->GetYaxis()->SetTitle( "d#sigma/d#Omega, ÜÑ/áà" );
        histo->SetStats( kFALSE );          // do not draw stats box
        histo->Draw();
        //c1->SaveAs( "c1_qt.eps" );
    }
    
    void histoTest_qt( void )
    {
        gROOT->SetStyle( "Plain" );
        gStyle->SetTitleBorderSize( 0 );    // do not draw frames around title
        gStyle->SetTitleOffset( 1.1, "xy" );// do not let axes' titles overlap ticks
        createHisto();
        if ( gROOT->IsBatch() )
            exit( 0 );
    }
    
    Заметили "кракозябры" внутри скрипта? Это еще одно неудобство. Скрипт выведен в общепринятой на сегодня кодировке UTF-8, а был записан в кодировке ISO-8859-5. В vim сохранение файла в данной кодировке обеспечивается командой
    :set fenc=iso-8859-5
    
    Однако при повторной загрузке этого файла в vim появятся всё те же "кракозябры" и новые русские записи не удастся добавить без полного переписывания русских символов заново. Возможно существуют редакторы, в которых проблема перевода в разные кодировки решается проще.

    Еще один интересный момент. Создание канваса c1 в данном варианте закомментировано. Если оставить его незакомментированным, то диапазон оси ординат изменится, и на месте гистограммы окажется чистое белое поле (!). Это еще раз подтверждает тот факт, что с текущей реализацией Qt бэкенда нужно быть очень осторожным.

    Изображение, полученное с помощью Qt бэкенда, выглядит так:


    Заметьте также, что Qt бэкенд применил преобразования локали: вместо точек в вещественных числах на координатных осях стоят запятые. 
  3. Третий подход основан на Latex и двух латеховских модулях - standalone и psfrag. Оба модуля можно найти на ctan.org. В пакет texlive для Fedora 14 они не входят, однако существует отдельный репозиторий texlive, в котором эти модули присутствуют. Информация об этом репозитории здесь. Преимущество данного подхода в том, что он полностью автоматизирован. Скрипт histoTest_latex.C выглядит так:
    void  createHisto( void )
    {
        TCanvas *  c1 = new TCanvas();
        TH1 *      histo = new TH1F( "h1", "CT", 10, 400., 600. );
        Double_t   content[] = { 0.0, 0.115, 0.145, 0.158, 0.170, 0.182, 0.180,
                                 0.172, 0.154, 0.140, 0.132, 0.0 };
        Double_t   errors[] = { 0.0, 0.0015, 0.0012, 0.0008, 0.0016, 0.0023, 0.0018,
                                0.0013, 0.0014, 0.0006, 0.0002, 0.0 };
        histo->SetContent( content );
        histo->SetError( errors );
        histo->GetXaxis()->SetTitle( "CX" );
        histo->GetYaxis()->SetTitle( "CY" );
        histo->SetStats( kFALSE );          // do not draw stats box
        histo->Draw();
        c1->SaveAs( "c1_latex.eps" );
    }
    
    void histoTest_latex( void )
    {
        gROOT->SetStyle( "Plain" );
        gStyle->SetTitleBorderSize( 0 );    // do not draw frames around title
        gStyle->SetTitleOffset( 1.2, "xy" );// do not let axes' titles overlap ticks
        createHisto();
        if ( gROOT->IsBatch() )
            exit( 0 );
    }
    
    Главным отличием от исходного скрипта является то, что оригинальные титул и подписи к осям заменены метками CT, CX и CY, которые будут обрабатываться в теховском скрипте с помощью psfrag. Идея psfrag весьма проста - заменить метки в исходном ps или eps файле указанными значениями. Отмечу сразу, что метки для подстановки следует выбирать короткие, иначе psfrag может сгенерировать ломаный файл dvi. Скрипт c1_latex.tex выглядит так:
    \documentclass{standalone}
    
    \usepackage[T2A]{fontenc}
    \usepackage[utf8x]{inputenc}
    
    \usepackage[dvips]{graphicx,color}
    \usepackage{psfrag}
    
    \begin{document}
    \psfrag{CT}[lt][lt][1.8]{\bf ДСР в зависимости от энергии}
    \psfrag{CX}[rt][rt][1.4]{\bf $\mathbf{E_{\mbox{цм}}}$, МэВ}
    \psfrag{CY}[rt][rt][1.4]{\bf $\mathbf{d\sigma/d\Omega}$, мб/ср}
    \includegraphics{c1_latex.eps}
    \end{document}
    
    О параметрах psfrag можно прочитать в документации к данному пакету; кратко, первый параметр в фигурных скобках является заменяемой меткой, последний параметр в фигурных скобках - подстановкой, первые два параметра в квадратных скобках после метки - позиционными якорями, третий параметр в квадратных скобках - коэффициентом масштабирования шрифта. Пакет standalone позволяет сохранить исходные размеры изображения.

    Русификация надписей может быть произведена с помощью отдельного шелл-скрипта mkrus:
    #!/bin/sh
    # source root macro
    root -b histoTest_latex.C
    # run psfrag
    latex c1_latex
    # make pdf
    dvips c1_latex
    ps2pdf c1_latex.ps
    # delete temporary files
    rm c1_latex.eps c1_latex.ps c1_latex.dvi c1_latex.aux c1_latex.log
    # make eps
    pdftops -eps c1_latex.pdf
    
    Этот скрипт создает два изображения: c1_latex.eps и c1_latex.pdf, которые выглядят так:


    В данном изображении используется шрифт Serif - просто в моем дистрибутиве texlive не нашлось русского Sans Serif шрифта c кодировкой T2A (которая используется в c1_latex.tex). Если необходим шрифт Sans Serif, нужно установить его из внешних источников.

суббота, 28 мая 2011 г.

Fedora 15 и wicd

Так уж получилось, что на моем ноутбуке Lenovo B560 вместо NetworkManager установлен wicd: просто на момент покупки (в феврале этого года) NetworkManager не умел работать с броадкомовским сетевым интерфейсом, установленном в B560 (да и сейчас наверное не умеет); кcтати и дрова для этого драйвера пришлось брать проприетарные - из rpmfusion (broadcom-wl). Как бы то ни было, но wicd мне вполне понравился и менять его обратно на NetworkManager я не собираюсь.

После того, как совсем недавно вышел релиз Fedora 15, я решил опробовать его на данном ноутбуке, перед тем как переносить на десктоп. Теперь я могу сказать совершенно точно, что обновлять десктоп с Fedora 14 до Fedora 15 я не буду, подожду следующего релиза. И, конечно же, огромное спасибо за такое решение хочется сказать разработчикам Gnome 3 :) Ну да ладно, это тема отдельного разговора.

Итак, вернемся к B560 и wicd. После обновления до Fedora 15 на ноутбуке отвалился wi-fi. Апплет wicd-gtk ругался на dbus и отказывался сканировать wi-fi источники. Первое, что удалось установить, это отсутствие модуля wl в списке загруженных модулей ядра. Оказывается, rpmfusion еще не удосужились обновиться до Fedora 15 (на момент написания этих строк репозитория rpmfusion Fedora 15 так и не появилось). В rpmfusion rawhide я этого драйвера тоже на тот момент не нашел (хотя сейчас он там уже присутствует). Поэтому я снес akmod-wl и kmod-wl и переустановил их из russianfedora. Команда modprobe wl вернула броадкомовскую железяку к жизни.

Однако это никак не повлияло на работу апплета wicd-gtk, который упорно ругался на dbus. Как выяснилось, демон wicd, который на Fedora 15 управляется новой системой загрузки systemd, умирал сразу же, как только systemd его стартовал. В багзилле Red Hat имеется соответствующий баг #327829, который был создан в апреле этого года и почему-то ни разу не комментировался. Если кому-то интересно, скрипт systemd для запуска демона wicd находится в файле /lib/systemd/system/wicd.service. Проверка статуса осуществляется командой systemctl status wicd.service, аналогично запуск и остановка - stop и start. Хотя старая добрая service wicd status тоже работает, просто перенаправляя действия на systemctl (обратите внимание, что в systemctl сначала указывается команда, а потом сервис). Как бы то ни было, но возиться с этим мне было некогда, мне нужен был рабочий wi-fi сразу после загрузки.

Очевидное решение - поместить строку /usr/sbin/wicd в файл /etc/rc.local - сработало. Остается ждать, когда разработчики починят баг #327829 и вернуть управление демоном wicd системе systemd.

воскресенье, 15 мая 2011 г.

Сравнение подходов в реализации алгоритмов на 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 варианте - с последнего. Как я уже говорил, могут существовать несколько возрастающих подпоследовательностей максимальной длины, поэтому оба случая являются правильным решением задачи.