Стрелки (arrows) и бесточечная (pointfree) нотация в haskell на конкретном примере

Стрелка — это модель обобщения вычислительного процесса, когда на вход вычисления может подаваться сразу несколько входных данных (например, в виде кортежа), а сам процесс вычисления строится с помощью комбинаторов типа first, second, (***), (&&&) и (>>>). Бесточечная нотация — это когда при записи функции в выражении (в том числе в ее определении), аргументы опускаются и, соответственно, не связываются (bind) в выражении. Поскольку стрелка абстрагирует входные данные, она выглядит хорошим кандидатом для применения в бесточечной нотации. Рассмотрим применение стрелки и бесточечной нотации на простом примере. Я взял его из очередного твита в 1HaskellADay. Задача простейшая — вывести на экран счет от целого числа from до целого числа to без использования явных циклов. Явные циклы в haskell, да и вообще в функциональном программировании, очень не приветствуются, поскольку относятся к миру императивного программирования. Поэтому данная задача выглядит простой и, в общем-то, таковой и является. Так как я собираюсь привести несколько решений, имеет смысл написать осто́вную функцию count, которая будет принимать основную функцию вычисления счета, передавать ей входные значения from и to, и выводить счет на экран.

count :: (Int -> Int -> [Int]) -> Int -> Int -> IO ()
count f from to = mapM_ print $ f from to

Здесь можно добавить проверку на то, что from меньше to, но я этого не сделал для простоты. Самую очевидную реализацию функции f я назвал cheating, поскольку в ней используется синтаксический сахар, предоставленный самим языком как раз для создания непрерывно возрастающего списка от некоторого числа m до некоторого числа n.

cheating from to = [from .. to]

Совершенно очевидное и незамысловатое решение. Его можно проверить в ghci или в функции main с помощью вызова

count cheating 1 10

Теперь простое решение без использования сахара haskell.

simple from to = takeWhile (<= to) . iterate succ $ from

Тоже несложно. Функция iterate succ строит бесконечный непрерывно увеличивающийся список, который начинается со значения from. Этот список трассируется функцией takeWhile до тех пор, пока выполняется предикат в скобках, то есть пока очередное значение в списке не превысит to. Обе функции cheating и simple просты и хороши. Но я бы хотел видеть их в бесточечной нотации, то есть без явного указания и связывания аргументов from и to. К сожалению, это невозможно, поскольку в первом случае синтаксис построения списка-диапазона требует указания обоих значений, а во втором случае значение to используется внутри предиката в самом центре тела функции. И здесь на помощь приходят стрелки! Для их использования необходимо импортировать модуль Control.Arrow.

import Control.Arrow

Я приведу тело функции arrowedPointfree, а ниже объясню, что в нем происходит.

arrowedPointfree = curry $ iterate succ *** (>=) >>> uncurry (flip takeWhile)

Видите, никаких from и to. Они неявно присутствуют в определении функции, но не связаны внутри ее тела. Оба аргумента склеиваются функцией curry в кортеж и передаются в вычислительный процесс, собранный из функций и стрелок, который начинается за символом $. Следуя традиции графического изображения стрелочных вычислений (см. здесь), я представлю (в меру своих художественных способностей) этот процесс вычисления на картинке.

Итак, кортеж (from, to) поступает на вход стрелочного комбинатора (***). Первый элемент кортежа (from) поступает на вход функции iterate succ, формируя бесконечный возрастающий список [from ..], второй (to) — на вход функции (>=), формируя новую функцию (>=) to. Заметьте, в функции simple мы использовали сечение (<= to). Наша новая функция эквивалентна сечению (to >=), что соответствует предикату из simple. На выходе комбинатора (***) новый кортеж ([from ..], (>=) to) поступает на оператор композиции (>>>), который передает вычисление в функцию uncurry. Функция uncurry декомпонует кортеж в последовательность двух аргументов (я изобразил это сужением вычислительного конвейера) и вызывает функцию flip takeWhile. Функция flip нужна для того, чтобы переставить аргументы [from ..] и (>=) to местами, сформировав takeWhile ((>=) to) [from ..]. Дело сделано! Не находите это решение красивым? Лично я нахожу. Это несмотря на то, что функции cheating и simple выглядят и проще, и понятнее. Но здесь нам удалось абстрагироваться от входных данных и сосредоточиться на потоке вычислений. Да, поначалу стрелки выглядят сложными, но только до тех пор, пока процесс вычисления не представлен графически. Есть еще один аспект. Часто в погоне за возможностью выразить код в бесточечном стиле (pointfree), программисты вынужденно усложняют понимание исходного кода, превращая его в pointless (бессмысленный). Поначалу я случайно назвал функцию arrowedPointfree arrowedPointless, и не сразу оценил всю глубину смысловой нагрузки этой оговорки. В этой статье приводится пример подобного усложнения (по мнению автора) и также обыгрываются синонимы pointfree и pointless. С другой стороны, невозможность записать выражение в бесточечном стиле может свидетельствовать об излишней монолитности функции. Попробуйте записать определение нашей осто́вной функции count в бесточечном стиле. Например,

count :: (Int -> Int -> [Int]) -> Int -> Int -> IO ()
count = mapM_ print

Этот вариант просто не скомпилируется: ghc пожалуется на то, что в функцию map передается слишком много аргументов. Максимальный уровень бесточечности, который можно выжать в определении функции count с такой сигнатурой, заключается в возможности опустить последний аргумент to, соединив mapM_ print и f from оператором (.).

count :: (Int -> Int -> [Int]) -> Int -> Int -> IO ()
count f from = mapM_ print . f from

Почему мы не можем выразить определение count в бесточечном стиле? Потому что мы намеренно усложнили ее определение, фактически объединив две разные функции в одну. Но в общем случае, зачем функции count знать о какой-то другой функции, принимающей какие-то аргументы и возвращающей список [Int]? Ей достаточно знать последний факт, то есть то, что она работает со списком целых чисел. Исходя из этого, определение count можно переписать в виде

count :: [Int] -> IO ()
count = mapM_ print

Вот и бесточечная нотация! Глядя на такое простое определение, мы можем заключить, что функция count нам вообще не нужна, это же просто mapM_ print, которую можно комбинировать напрямую в месте вызова. Например,

mapM_ print $ arrowedPointfree 1 10

Правда, в этом варианте пропало слово счет (count), но это уже вопрос правильного именования функций: при отсутствии осто́вной функции все функции счета следует переименовать.

Правильное нестрогое сопоставление юникодных строк в C++

Я имею в виду поиск алгоритма из набора существующих библиотек, который посчитает, что строки Семён зна́ет и семен знает равны, и сможет найти строку Знает в первой из них. Никакие strncasecmp() и iequals() в таком сравнении строк не помогут, я уже молчу о поиске подстроки — представьте, как вы будете искать подстроку с возможно измененными символами возможно другой длины в байтах! Вообще говоря, приведенный выше тип сравнения сравнением не является. В самом деле, игнорирование умляутов и преобразование произвольных букв из набора Unicode в разные регистры должны предполагать некоторую эвристику. Я не зря не использовал термин сравнение в заголовке статьи. Потому что это сопоставление, или, по-латински, коллация (collation). Объект, выполняющий коллацию, называется коллатором. Обычно существует несколько уровней коллации, начиная от самого либерального (первичный или primary) и заканчивая самым жестким, требующим полной идентичности всех символов (identical). Я не в курсе, кто изобрел эту концепцию, но она точно присутствует в библиотеке интернационализации ICU (см. документацию к классу icu::Collator). Библиотека boost::locale тоже предоставляет такой интерфейс (см. здесь), но это и не удивительно, поскольку libboost_locale, будучи слинкована с библиотеками libicuuc и libicui18n, по-видимому, просто оборачивает алгоритмы ICU. Давайте реализуем предложенное в начале статьи сравнение строк с помощью boost::locale.

#include <boost/locale.hpp>
#include <iostream>

using namespace  boost::locale;


namespace
{
    generator                 gen;
    std::locale               loc( gen( "" ) );
    const collator< char > &  col( std::use_facet< collator < char > >( loc ) );
}


int  main( void )
{
    std::string  a( "Семён зна́ет" );
    std::string  b( "семен знает" );

    bool  eq( col.compare( collator_base::primary, a, b ) == 0 );

    std::cout << a << " and " << b << " are " <<
            ( eq ? "identical" : "different" ) << " on primary comparison" <<
            std::endl;

    eq = col.compare( collator_base::secondary, a, b ) == 0;

    std::cout << a << " and " << b << " are " <<
            ( eq ? "identical" : "different" ) << " on secondary comparison" <<
            std::endl;

    std::string  c( "приём!" );

    std::cout << to_upper( c, loc ) << std::endl;
}

Внутри анонимного пространства имен определены базовые объекты boost::locale: генератор локалей gen, локаль loc, инициализируемая системной локалью (да, я предполагаю, что системной локалью является UTF-8), и ссылка на коллатор col. Внутри функции main() мы сравниваем строки с Семёном, используя первичный и вторичный уровни коллации в предположении, что в первом случае строки должны оказаться равными, а во втором нет за счет замены ё на е и снятия ударения над а. В самом низу мы также проверим, что функция boost::locale::to_upper() правильно переводит строку приём! в верхний регистр. Поместим данный исходный код в файл test.cc и скомпилируем.

g++ -Wall -o test test.cc -lboost_locale

Теперь запустим программу на выполнение.

./test
Семён зна́ет and семен знает are identical on primary comparison
Семён зна́ет and семен знает are different on secondary comparison
ПРИЁМ!

Работает! Теперь давайте искать подстроки в строке Семён зна́ет. Идею я взял из этого комментария. Вверху программы добавим новые инклюды.

#include <vector>
#include <string>
#include <algorithm>
#include <iterator>

Ниже определим тело функции find().

bool  find( const std::vector< std::string > &  p, const std::string &  s,
            collator_base::level_type  level = collator_base::primary )
{
    std::size_t  pos( 0 );
    std::string  snorm( col.transform( level, s ) ); 

    std::size_t  ssize( snorm.size() - 1 );
    std::size_t  len( ssize );

    for ( std::vector< std::string >::const_iterator  k( p.begin() );
          k != p.end(); ++k )
    {
        std::string  pnorm( col.transform( level, *k ) );
        std::size_t  psize( pnorm.size() - 1 );

        if ( psize > len )
            return false;

        std::string  scur( std::string( snorm, pos, len ) );
        std::size_t  scur_pos( scur.find( pnorm.c_str(), 0, psize ) );

        if ( scur_pos == std::string::npos )
            return false;

        std::size_t  shift( scur_pos + psize );

        pos += shift;
        len -= shift;
    }

    return true;
}

На вход find() подается ссылка на вектор искомых подстрок p, строка s, в которой будет осуществляться поиск, а также уровень коллации level. Внутри функции find() из строки s с помощью метода transform() коллатора col формируется новая бинарная строка snorm, внутри которой в цикле по всем элементам вектора p формируются соответствующие бинарные строки pnorm, которые последовательно ищутся в строке snorm обычным методом std::string::find(). Согласно автору приведенного комментария, строки snorm и pnorm содержат в конце ненужные нулевые символы, поэтому все сравнения производятся с подстроками snorm и pnorm без последнего символа (для этого объявлены дли́ны ssize и psize). Внизу функции main() добавляем код, тестирующий функцию find().

    std::vector< std::string >  parts;

    parts.push_back( "емен" );
    parts.push_back( "Зн" );
    parts.push_back( "ет" );

    bool  in( find( parts, a ) );

    std::cout << a << ( in ? " contains " : " does not contain " );
    std::copy( parts.begin(), parts.end(),
               std::ostream_iterator< std::string >( std::cout, " " ) );
    std::cout << "on primary comparison" << std::endl;

Вектор искомых подстрок parts состоит из трех элементов: емен, Зн и ет. Они должны быть найдены в строке a при использовании первичной коллации. Я не стал добавлять проверку вторичной коллации, потому что … Скомпилируем и запустим программу.

./test
Семён зна́ет and семен знает are identical on primary comparison
Семён зна́ет and семен знает are different on secondary comparison
ПРИЁМ!
Семён зна́ет does not contain емен Зн ет on primary comparison

Потому что наша find() не работает! Если вы думаете, что я где-то ошибся, попробуйте вставить поиск подстроки емен в строке Семён зна́ет в исходный код оригинального примера. Этот поиск не сработает. В этом треде автор вопроса утверждает, что после трансформации строки методом transform() на ее хвосте появляется не одиночный нулевой символ, а сразу несколько разных, в том числе не нулевых, символов. Главным результатом является один из ответов на этот вопрос, в котором утверждается, что transform() не гарантирует возможность поиска подстрок, являясь лишь инструментом для сопоставления строк. Получается, boost::locale не предоставляет возможности для нестрого поиска подстрок внутри юникодной строки. Что же тогда делать? А давайте обратимся к ICU, на которой, как мы увидели, основан boost::locale. Добавляем новые инклюды

#include <unicode/unistr.h>
#include <unicode/stsearch.h>
#include <unicode/coll.h>

, объявляем использование нового пространства имен

using namespace  icu;

, пишем новую функцию find_icu().

bool  find_icu( const std::vector< std::string > &  p, const std::string &  s,
                Collator::ECollationStrength  strength = Collator::PRIMARY )
{
    int32_t        pos( 0 );
    UnicodeString  su( UnicodeString::fromUTF8( StringPiece( s ) ) );

    for ( std::vector< std::string >::const_iterator  k( p.begin() );
          k != p.end(); ++k )
    {
        UnicodeString  pu( UnicodeString::fromUTF8( StringPiece( *k ) ) );
        UErrorCode     status( U_ZERO_ERROR );

        StringSearch   it( pu, UnicodeString( su, pos ), Locale::getDefault(),
                           NULL, status );

        it.getCollator()->setStrength( strength );

        int32_t        scur_pos( it.first( status ) );

        if ( scur_pos == USEARCH_DONE )
            return false;

        pos += scur_pos + it.getMatchedLength();
    }

    return true;
}

Здесь много новых типов, но логика не отличается от логики функции find(). Вместо строки snorm здесь мы создаем юникодную строку su, в цикле по элементам вектора p вместо строк pnorm создаются юникодные строки pu. Собственно поиск осуществляется с помощью метода first() итератора it типа StringSearch. Вместо длины строки pu к значению pos прибавляется значение, возвращаемое методом getMatchedLength() итератора it. Уровень коллации в ICU называется строгостью (strength), поэтому мы заменили название переменной level на strength. Вставим полноценную проверку поиска подстрок функцией find_icu() в main().

    in = find_icu( parts, a );

    std::cout << a << ( in ? " contains " : " does not contain " );
    std::copy( parts.begin(), parts.end(),
               std::ostream_iterator< std::string >( std::cout, " " ) );
    std::cout << "on ICU primary comparison" << std::endl;

    in = find_icu( parts, a, Collator::SECONDARY );

    std::cout << a << ( in ? " contains " : " does not contain " );
    std::copy( parts.begin(), parts.end(),
               std::ostream_iterator< std::string >( std::cout, " " ) );
    std::cout << "on ICU secondary comparison" << std::endl;

Компилируем программу

g++ -Wall -o test test.cc -lboost_locale -licuuc -licui18n

(заметили линковку новых библиотек?), и запускаем ее на выполнение.

./test
Семён зна́ет and семен знает are identical on primary comparison
Семён зна́ет and семен знает are different on secondary comparison
ПРИЁМ!
Семён зна́ет does not contain емен Зн ет on primary comparison
Семён зна́ет contains емен Зн ет on ICU primary comparison
Семён зна́ет does not contain емен Зн ет on ICU secondary comparison

Вот теперь все работает! Исходный код тестовой программы можно скачать отсюда.