haskel

[dyvniy]

многопоточность и тесты
http://habrahabr.ru/company/spbau/blog/224075/

Спойлер

Haskell. Тестируем многопоточное приложение
Блог компании СПБАУ, Haskell*
Данная статья составлена преподавателем Академического университета Валерием Исаевым по материалам практики по курсу функционального программирования.

Полагаю, ни для кого не секрет, что написание многопоточных приложений связано с целым рядом проблем, отсутствующих при разработке однопоточных программ.
Одна из проблем заключается в тестировании приложения.
Мы не можем контролировать порядок, в котором выполняются операции, следовательно, не поддается контролю и результат выполнения программы. Даже если мы получим ошибку, наступить на те же грабли второй раз будет не так-то просто.
Хочу предложить небольшой рецепт того, как можно протестировать многопоточное приложение.
Из ингредиентов нам понадобятся: haskell, QuickCheck, немного монад, соль/перец по вкусу.

Рабочий пример

В качестве рабочего примера возьмем задачу об обедающих философах.

MVar a – это ссылка, которая либо содержит значение типа a, либо пуста.
putMVar ref x кладет по ссылке ref значение x.
takeMVar ref считывает содержимое ссылки, оставляя ее после этого пустой.
Если она уже была пуста, то поток засыпает, пока в нее не запишет что-нибудь другой поток.
() – это тип, имеющий единственное значение, которое обозначается так же, как и сам тип – ().
Вилки мы моделируем ссылками типа MVar ().
Таким образом, у вилки может быть два состояния: если вилка занята каким-либо философом – она пуста; если вилка свободна – она содержит значение ().

import System.Random
import Control.Monad
import Control.Concurrent
import Control.Monad.Cont
import Control.Monad.Trans
import Data.IORef
import Test.QuickCheck
import Test.QuickCheck.Gen
import Test.QuickCheck.Monadic

-- sleep останавливает поток на рандомное количество секунд (от 0 до 0.3)
sleep :: IO ()
sleep = randomRIO (0, 300000) >>= threadDelay

phil
:: Int -- Номер философа.
-> MVar () -- Ссылка на левую вилку.
-> MVar () -- Ссылка на правую вилку.
-> IO ()
phil n leftFork rightFork = forever $ do
putStrLn $ show n ++ " is awaiting"
sleep
takeMVar leftFork
putStrLn $ show n ++ " took left fork"
-- sleep
takeMVar rightFork
putStrLn $ show n ++ " took right fork"
sleep
putMVar leftFork ()
putMVar rightFork ()
putStrLn $ show n ++ " put forks"
sleep

runPhil :: Int -> IO ()
runPhil n = do

-- Создаем ссылки, которые представляют вилки.
forks <- replicateM n $ newMVar ()

-- Запускаем 5 потоков, в каждом выполняем функцию phil.
forM_ [1..n] $ \i -> forkIO $ phil i (forks !! (i - 1)) (forks !! (i `mod` n))

main = do
runPhil 5

-- Если главный поток завершится, программа остановится, поэтому мы его усыпляем навечно.
forever (threadDelay 1000000000)

В этой программе может случиться дедлок.
Чтобы полюбоваться на него, можно раскомментировать строку — sleep и немного подождать.
Наша цель – написать тесты, которые бы обнаружили эту ошибку.
Но прежде чем мы сможем это сделать, стоит понять, как мы будем управлять порядком выполнения операций. Для этого, вместо IO, используем другую монаду.

Обобщим определение функций sleep, phil и runPhil, чтобы они работали и для других монад.

sleep :: MonadIO m => m ()
sleep = do
r <- liftIO $ randomRIO (0, 100)
r `times` liftIO (threadDelay 300)
where
times :: Monad m => Int -> m () -> m ()
times r a = mapM_ (\_ -> a) [1..r]

Теперь функция sleep может работать с любой монадой, которая поддерживает IO операции. В классе MonadIO определена всего одна функция liftIO, которая позволяет это делать.
Заметим, что вместо того, чтобы один раз засыпать на рандомное число секунд, мы засыпаем рандомное число раз на 0.3 миллисекунды. Причина в том, что в нашей монаде действия внутри liftIO выполняются атомарно. Соответственно, время, на которое мы засыпаем, ни на что не влияет, важно только, сколько раз мы это делаем.

Поскольку наша монада будет работать в одном потоке, MVar для нас бесполезны, и мы позже определим свой тип ссылок, исходя из того, чтобы функция phil могла работать и с MVar, и с другими типами ссылок.
Для этого определим класс монад MonadConcurrent, в котором будут операции для создания, чтения и записи по ссылке, а также для создания потоков.

class Monad m => MonadConcurrent m where
type CVar m :: * -> *
newCVar :: a -> m (CVar m a)
takeCVar :: CVar m a -> m a
putCVar :: CVar m a -> a -> m ()
fork :: m () -> m ()


Здесь мы использовали семейства типов, которые являются расширением языка.
В данном случае нам нужно это расширение, чтобы мы могли определять для разных монад разные типы ссылок.
Для использования расширения нужно добавить следующую строчку в начало файла (и заодно подключить расширения, которые понадобятся позже):

{-# LANGUAGE TypeFamilies, ExistentialQuantification, GeneralizedNewtypeDeriving #-}

Определим instance этого класса для монады IO.
Тут всё легко: мы просто используем соответствующие операции для MVar.

instance MonadConcurrent IO where
type CVar IO = MVar
newCVar = newMVar
takeCVar = takeMVar
putCVar = putMVar
fork m = forkIO m >> return ()

Обобщим функции phil и runPhil.

phil :: (MonadIO m, MonadConcurrent m) => Int -> CVar m () -> CVar m () -> m ()
phil n leftFork rightFork = forever $ do
liftIO $ putStrLn $ show n ++ " is awaiting"
sleep
takeCVar leftFork
liftIO $ putStrLn $ show n ++ " took left fork"
takeCVar rightFork
liftIO $ putStrLn $ show n ++ " took right fork"
sleep
putCVar leftFork ()
putCVar rightFork ()
liftIO $ putStrLn $ show n ++ " put forks"
sleep

runPhil :: (MonadIO m, MonadConcurrent m) => Int -> m ()
runPhil n = do
forks <- replicateM n $ newCVar ()
forM_ [1..n] $ \i -> fork $ phil i (forks !! (i - 1)) (forks !! (i `mod` n))

Запустим программу и убедимся, что она работает как прежде.

Монада Concurrent

А теперь начинается самое интересное.

Определим монаду, в которой будем работать (забегая вперед, скажу, что называется она Cont). Также рискну предположить, что Cont – одна из самых сложных и самых мощных монад одновременно.
Используя эту монаду, с потоком управления можно делать всё что угодно: например, вместо того, чтобы выполнять действия, можно их сохранить в структуре (с этой целью объявим тип Action) и выполнить их позже, возможно, в другом порядке.

data Action = Atom (IO Action)
| forall a. ReadRef (MaybeRef a) (a -> Action)
| forall a. WriteRef (MaybeRef a) a Action
| Fork Action Action
| Stop

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

Например:
Функция getSum задает действие, которое считывает два числа с клавиатуры, печатает их сумму и завершается.

getSum :: Action
getSum = Atom $ do
x <- readLn -- считываем первое число
return $ Atom $ do -- возвращаем продолжение
y <- readLn -- считываем второе число
return $ Atom $ do -- возвращаем продолжение
print (x + y) -- печатаем сумму
return Stop -- возвращаем продолжение

Далее:
Действие WriteRef ref val act записывает значение val по ссылке ref, в act находится продолжение.
Действие ReadRef ref act считывает значение по ссылке ref, act принимает это значение и возвращает продолжение.
Чтобы в Action можно было сохранять ссылки произвольных типов, мы используем еще одно расширение языка – экзистенциальную квантификацию.

Тип MaybeRef представляет тип ссылок, которые мы будем использовать вместо MVar, и определяется он как ссылка на Maybe.

newtype MaybeRef a = MaybeRef (IORef (Maybe a))

Теперь мы можем определить нашу монаду.
Как я и обещал, мы просто оборачиваем монаду Cont.

newtype Concurrent a = Concurrent (Cont Action a) deriving Monad

Монада Cont Action устроена следующим образом.
Вместо того чтобы возвращать значение типа a, она принимает продолжение типа (a -> Action), передает в эту функцию значение и возвращает результат.
То есть можно считать, что Cont Action a = (a -> Action) -> Action.
Если точнее, у нас есть следующая пара функций, которые переводят (a -> Action) -> Action в Cont Action a и обратно.

cont :: ((a -> Action) -> Action) -> Cont Action a.
runCont :: Cont Action a -> (a -> Action) -> Action

Теперь мы можем определить instance классов MonadIO и MonadConcurrent.

instance MonadIO Concurrent where
liftIO m = Concurrent $ cont $ \c -> Atom $ do
a <- m
return (c a)

Давайте посмотрим, что здесь происходит.
liftIO принимает IO операцию и оборачивает ее в атомарное действие. А именно: мы в cont передаем функцию, которая принимает продолжение (то есть c имеет тип a -> Action) и возвращает атомарное действие, выполняющее IO операцию m.
Мы определили Atom так, что атомарная операция должна возвращать Action, являющийся продолжением.
Собственно это мы и делаем: после того как мы выполнили m, мы вызываем c, которое и возвращает необходимое продолжение.

Теперь определим instance MonadConcurrent.
Создаем в newCVar ссылку, используя только что определенную функцию liftIO.
В takeCVar и putCVar возвращаем соответствующее действие, а продолжение сохраняем внутри этой структуры.
В fork возвращаем действие, в котором сохранены оба потока: один передается в аргументы функции fork, другой приходит из продолжения.

instance MonadConcurrent Concurrent where
type CVar Concurrent = MaybeRef
newCVar a = liftIO $ liftM MaybeRef $ newIORef (Just a)
takeCVar v = Concurrent $ cont (ReadRef v)
putCVar v a = Concurrent $ cont $ \c -> WriteRef v a $ c ()
fork (Concurrent m) = Concurrent $ cont $ \c -> Fork (runCont m $ \_ -> Stop) $ c ()

Наша монада практически готова, осталось только научиться ее запускать.
Для начала напишем функцию, запускающую Action. Она принимает список действий, каждый элемент в котором – отдельный поток.
Стратегии по запуску действий могут быть различными. Определимся с двумя моментами: в каком порядке выполнять потоки, и что делать, если мы пытаемся считать значение из переменной, которая пуста. Напомню, что в переменной может ничего не лежать, и тогда нам нужно дождаться, когда другой поток в нее что-нибудь положит.
Давайте вначале напишем простую версию, где будем выполнять потоки по очереди; а поток, пытающийся считать из пустой переменной, будем перемещать в конец очереди.

runAction :: [Action] -> IO ()
-- Если потоков не осталось, завершаемся.
runAction [] = return ()

-- Выполняем атомарное действие, а продолжение, которое оно возвращает, кладем в конец очереди.
runAction (Atom m : as) = do
a' <- m
runAction $ as ++ [a']

-- Кладем два новых потока в конец очереди.
runAction (Fork a1 a2 : as) = runAction $ as ++ [a1,a2]

-- Продолжаем запускать остальные потоки.
runAction (Stop : as) = runAction as

runAction (ReadRef (MaybeRef ref) c : as) = do

-- Считываем содержимое ссылки.
ma <- readIORef ref
case ma of

-- Если там было что-то, то
Just a -> do

-- Опустошаем содержимое ссылки.
writeIORef ref Nothing

-- Кладем в конец очереди продолжение.
runAction (as ++ [c a])

-- Если там ничего не было, то нужно попробовать считать эту ссылку позже, поэтому добавляем в конец очереди то же самое действие.
Nothing -> runAction (as ++ [ReadRef (MaybeRef ref) c])

-- Записываем по ссылке значение, продолжением кладем в конец очереди.
runAction (WriteRef (MaybeRef ref) val a : as) = do
writeIORef ref (Just val)
runAction (as ++ [a])

Заметьте, что putMVar работает несколько иначе, чем наша реализация WriteRef.
Если по ссылке уже было какое-то значение, то putMVar заморозит поток, пока переменная не освободится. В этом случае перезапишем значение.
Версию, работающую как putMVar, создавать в данной ситуации не стоит, чтобы не переусложнять код.

Далее пишем функцию, запускающую Concurrent, и переопределяем main.

runConcurrent :: Concurrent () -> IO ()
runConcurrent (Concurrent c) = runAction [runCont c $ \_ -> Stop]

main = runConcurrent (runPhil 5)

Так как теперь мы работаем в одном потоке, и threadDelay останавливает всю работу, скорость немного снизилась.

Пишем тесты

Настало время «добавить в блюдо приправу» – написать тесты для нашего примера.
Для этого используем библиотеку QuickCheck, генерирующую случайные входные данные для тестов. Поскольку мы хотим запускать наши потоки в различных порядках, то входные данные для наших тестов – это порядок, в котором мы выбираем очередной поток из списка.
Можно закодировать входные данные списком чисел, но проблема в том, что мы не знаем заранее, из какого диапазона следует выбирать эти числа, так как число потоков может меняться.
Поэтому кодировать входные данные мы будем списком функций типа Int -> Int, которые принимают число n и возвращают число из интервала [0,n-1].

newtype Route = Route [Int -> Int]

Класс Arbitrary, предоставляемый библиотекой QuickCheck, предназначен для описания типов, позволяющих генерировать элементы случайным образом.
В этом классе объявлено две функции — shrink и arbitrary.
У shrink есть реализация по умолчанию, так что переопределять ее не будем.
В функции arbitrary сгенерируем список случайных функций, где каждая функция возвращает число из интервала [0,n-1].

instance Arbitrary Route where
arbitrary = fmap Route (listOf arbitraryFun)
where
arbitraryFun = MkGen $ \q s n -> unGen (choose (0, n - 1)) q s

Определяем также instance Show для Route, поскольку этого требует QuickCheck.
К сожалению, слишком полезный show мы написать не можем. Более того, эта функция использоваться не будет, поэтому мы оставляем ее неопределенной.

instance Show Route where
show = undefined

Теперь можно приступить к написанию более умной версии runAction.
Первое отличие заключается в том, что мы разделим выполнение атомарных действий и работу с ссылками.
Для начала напишем вспомогательную функцию skipAtoms, выполняющую атомарные действия: функция принимает список действий, выполняет Atom, Fork и Stop, остальные возвращает в качестве результата.

skipAtoms :: [Action] -> IO [Action]
skipAtoms [] = return []
skipAtoms (Atom m : as) = do
a <- m
skipAtoms (as ++ [a])
skipAtoms (Fork a1 a2 : as) = skipAtoms (as ++ [a1,a2])
skipAtoms (Stop : as) = skipAtoms as
skipAtoms (a : as) = fmap (a:) (skipAtoms as)

Второе отличие новой версии runAction от прежней заключается в том, что мы отслеживаем получение дедлока.
Для этого заводим два списка действий. В первом хранятся активные (выполняемые нами) потоки. Во втором – потоки, ждущие обновления какой-либо ссылки.
Если список активных потоков пуст, а списка ждущих нет, значит, мы получили дедлок, и в этом случае бросаем исключение.

Третье нововведение – аргумент типа Route, используемый для выбора номера потока, который следует выполнить на текущем шаге.

runAction :: Route -> [Action] -> [Action] -> IO ()
runAction _ [] [] = return ()
runAction _ [] _ = fail "Deadlock"
runAction (Route []) _ _ = return ()
runAction (Route (r:rs)) as bs = do
as <- skipAtoms as
let n = length as
case splitAt (r n) as of
(as1, ReadRef (MaybeRef ref) c : as2) -> do
ma <- readIORef ref
case ma of
Just a -> do
writeIORef ref Nothing
runAction (Route rs) (as1 ++ [c a] ++ as2) bs
Nothing -> runAction (Route rs) (as1 ++ as2) (bs ++ [ReadRef (MaybeRef ref) c])
(as1, WriteRef (MaybeRef ref) x c : as2) -> do
writeIORef ref (Just x)
runAction (Route rs) (as1 ++ [c] ++ as2 ++ bs) []

Функция runConcurrent практически не поменялась.

runConcurrent :: Route -> Concurrent () -> IO ()
runConcurrent r (Concurrent c) = runAction r [runCont c $ \_ -> Stop] []

Можно проверить, как работает новая версия, передав в качестве первого аргумента round_robin. Это простая стратегия выполнения, аналогичная тому, как функция runAction работала раньше. Здесь мы просто генерируем бесконечный список и для каждого элемента берем остаток по модулю числа потоков.

round_robin :: Route
round_robin = Route $ map rem [0..]

Запустив вычисления на этих входных данных, мы, скорее всего, быстро получим дедлок – по причине того, что работа нашего примера построена на основе генератора случайных чисел – следовательно, не смотря на то, что входные данные всегда одни и те же, порядок выполнения оказывается случайным.
Если бы наш пример был более детерминирован, нам пришлось бы варьировать входные данные случайным образом, что мы сейчас и сделаем.

main = quickCheck $ monadicIO $ do
r <- pick arbitrary
run $ runConcurrent r (runPhil 5)

Мы выбираем произвольный элемент типа Route, используя реализованную нами ранее функцию arbitrary. После чего запускаем наше вычисление на этом входе.
Об остальном позаботится QuickCheck, а именно: запустит наш тест 100 раз, с каждым разом увеличивая размер входных данных.

Запустив программу, мы увидим следующее:

...
3 took left fork
4 put forks
4 is awaiting
5 took left fork
4 took left fork
1 took right fork
1 put forks
1 is awaiting
1 took left fork
2 took left fork
*** Failed! Exception: 'user error (Deadlock)' (after 36 tests):

Что и требовалось получить!

Заключение

Мы научились писать тесты, которые могут обнаруживать состояние дедлока в многопоточном приложении.
В процессе мы видели примеры использования монады Cont, семейств типов, экзистенциальной квантификации и библиотеки QuickCheck.
Кроме того, мы узнали, как можно собрать модель многопоточного выполнения программы из подручных материалов.
haskell, образование, многопоточность, тестирование
+39 11204
65Ankuzik 0,0
Похожие публикации

Онлайн-программа по основам программирования (12)
Задачи по алгоритмам (36)
Студенческие школы в образовании (3)
Опрос: каким должно быть дополнительное образование? (49)
IT + образование. Еще раз о бакалавриате (24)
Комментарии (19) отслеживать новые: в почте в трекере

+2 Alexeyco26 мая 2014 в 08:02#
Простите. Почему у человека на картинке такие огромные мешки под глазами?
+2 HaruAtari26 мая 2014 в 08:07#↵↑
Это же монады!
0 denisshevchenko26 мая 2014 в 09:24 (комментарий был изменён)#↵↑
Ну так и что? Суть монад вполне можно объяснить «в пяти словах или меньше»…
+2 datacompboy26 мая 2014 в 16:30 (комментарий был изменён)#↵↑
«моноид в категории эндофункторов»? ну да, 4 слова…
а если по-человечески?
0 denisshevchenko26 мая 2014 в 16:36#↵↑
Нет, лучше так: «Абстракция последовательной связки вычислений.»
+2 Alexeyco26 мая 2014 в 17:27 (комментарий был изменён)#↵↑
— Весь этот разговор довольно примитивен. Мы ведь начали с того, кто я по своей природе. Если угодно, я полагаю себя… Ну скажем, монадой. В терминах Лейбница.
— А кто тогда тот, кто полагает себя этой мандой?
— Монада и полагает, — ответил я, твердо решив держать себя в руках.

В. Пелевин, «Чапаев и Пустота»
+4 denisshevchenko26 мая 2014 в 19:30#↵↑
По каким-то историческим причинам, понятие «монада» покрылось некой сакральной тайной. А как правильно выразился один разработчик, «монаду можно воспринимать как особый паттерн проектирования». Ничего сакрального в нём нет.
0 HaruAtari27 мая 2014 в 07:47#↵↑
Понятно, что монада — это не так страшно, как ее малюют.
Недавно в учебнике прочитал пример: пример монады в других языках — объект jquery. И в принципе это верно, но много ли frontend разработчиков знают, как оно там внутри устроено? Сомневаюсь.

Тем более, что, объясняя, что такое монада, нужно не только объяснить «что это», но и «как это устроено» и «зачем/как/когда это использовать».

Я например начал использовать монады довольно просто. Но до сих пор не осознал до конца ее сакрального смысла. Не проникся так сказать.
0 denisshevchenko27 мая 2014 в 09:34#↵↑
Тем более, что, объясняя, что такое монада, нужно не только объяснить «что это», но и «как это устроено» и «зачем/как/когда это использовать».

Что это и когда использовать — да. Но как устроено… Я не вижу необходимости в знании внутреннего устройства монады. Да, если монада рассматривается как объект исследования — тогда конечно. Если же она рассматривается как инструмент для практического применения — в этом случае вовсе не обязательно знать, что там у неё под капотом.
+2 VoidEx26 мая 2014 в 08:10#
times :: Monad m => Int -> m () -> m ()
times r a = mapM_ (\_ -> a) [1..r]

Можно через sequence_
times r = sequence_ . replicate r
+2 VoidEx26 мая 2014 в 08:24#
Статья супер, спасибо!
+1 denisshevchenko26 мая 2014 в 09:26#
Большое спасибо за статью! Весьма доходчиво.
НЛО прилетело и опубликовало эту надпись здесь
–2 shock_one26 мая 2014 в 12:35#
Монада — моноид в категории эндофункторов.
0 ymn26 мая 2014 в 14:26#↵↑
Спасибо, кэп!
–8 BalinTomsk26 мая 2014 в 21:05#
--Одна из проблем заключается в тестировании приложения.
--Мы не можем контролировать порядок, в котором выполняются операции

дак научитесь писать юнит-тесты. Или это особенность (недостаток) Хаскеля?
0 denisshevchenko26 мая 2014 в 21:14#↵↑
Это особенность чистого кода. Мы действительно не можем контролировать порядок, в котором выполняются чистые (математические) функции, ведь конечный результат их работы от этого порядка никак не зависит.
–5 BalinTomsk26 мая 2014 в 21:36#↵↑
любой поряд выполнения кода кем-то логически запрограмирован.
А юнит тесты все таки позволяют любой порядок выполнить. На этом мир TDD держится
+4 hoq26 мая 2014 в 21:57#↵↑
Речь идет о тестировании многопоточного приложения и том, что порядок, в котором выполняются операции в различных потоках, не фиксирован.

[dyvniy]

3d игра на haskell !!
https://wiki.haskell.org/Frag
http://alenacpp.blogspot.ru/2005/12/3d-haskell.html

phpBB [media] link

[dyvniy]

В реальной жизни, парсинг логов
http://habrahabr.ru/post/129235/

Спойлер

Haskell в реальном мире
Haskell*
В этом блоге уже много написано о самом языке Haskell, и было несколько статей о его практическом применении. Сейчас я вдохновенно расскажу еще об одном реальном применении языка в производстве.

Описание данных

Я работаю в телекомах: фиксированная телефонная связь, интернет, IP-телефония. В задачи входит обработка трафика с АТС, с серверов IP-телефонии, поддержка текущего биллинга, написание софта и администрирование сетей, домена (да, «программист на все руки»). Недавно в моей организации было установлено новое оборудование, работающее совсем по другим принципам, и трафик, соответственно, тоже изменился. Теперь он поставляется в двух вариантах: со старых станций и с новых. Новый трафик дублируется в бинарном и текстовом форматах. Бинарники нам вообще не подходят (хотя кое-кто по незнанию говорил: «А чего там? Берешь их, и они сами в биллинг заскакивают!»), текстовый же занимает на порядок больше места, но именно с ним можно что-то сделать. Трафик со старого оборудования все еще идет, и его мы с напарником забрасываем с помощью отработанных схем, использующих сервисы местной СУБД. Можно было бы настроить эти же сервисы для трафика с новых станций, но обнаружилось несколько особенностей. Трафик на новых станциях пишется в отдельные файлы каждые 15 минут; всего таких файлов за месяц получается около 3000 (в идеале — 2976 за 31 день и 2880 за 30 дней). Каждый файл отдельно импортировать не будешь, ибо маразм. Слить в один их можно и даже нужно, благо они все текстовые, и записи о звонках расположены построчно. Ручное слияние выглядит так: выделяешь файлы только за прошлый месяц и добавляешь их в простейший скрипт слияния в командной строке. Формат имени файла фиксирован, следовательно, слияние можно автоматизировать, только придется парсить год и месяц. Линуксоиды бы использовали какой-нибудь Bash, Perl или Python, — дешево и сердито, но на Windows-машину их ради одной операции не поставишь, то же самое касается и PowerShell. А cmd — это извращение, о чем мы с вами хорошо знаем. Наконец, в самом трафике тоже обнаружились сюрпризы, из-за которых даже после слияния и импорта с помощью средств СУБД требовалось много ручной SQL-работы. В общем, факторы как-то так удачно сложились в задачу для Haskell, который я в то время (апрель-май 2011) начал изучать.

Итак, ~ 3000 15-тиминутных файлов за месяц. На оборудовании можно изменить интервал и поставить не 15 минут, а любое другое значение: 5, 10, 30, 45… Количество файлов и их размеры, соответственно, изменятся. Пример имени файла (за 09.05.2011 09:30:00):

999992011050909300081.txt
99999 - идентификатор, вшитый в оборудование (по понятным причинам, я его заменил на девятки)
2011 - год
05 - месяц
09 - день
09 - часы
30 - минуты
00 - секунды
81 - какое-то случайное число, возможно, десятые доли секунд.


Абонентов становится больше, и каждый файл уверенно растет в размере. Сейчас у нас в среднем 240 строчек на файл, но было сезонное летнее проседание, люди разъехались по отпускам и звонили меньше. За сентябрь ждем увеличения активности в полтора-два раза.

Записи о звонках разнообразны. Есть несколько разных типов записей, у которых разное количество полей. Записи типа R210 попадаются очень редко, и что они значат, мы не стали выяснять (здесь и далее данные трафика заменены случайными):

|R210|2011-06-24 21:43:53|2011-06-24 01:43:52|1|


Как нетрудно убедиться, здесь всего лишь 4 поля: идентификатор типа записи, дата начала, дата конца (формат ISO 8601/SQL) и, зачем-то, единичка. Поля разделяются вертикальной чертой, которая должна стоять и в начале записи, и в конце, так что реально полей на 1 больше, то есть, 5. Удобно считать, что поле с индексом 0 пустое, находится перед первой вертикальной чертой. Тогда отсчет значимых полей будет идти с 1.

Обычные звонки регистрируются в записях типа R200. Там уже 152 поля, причем это можно перенастроить на оборудовании: какие-то поля добавить, какие-то удалить, а у прочих, возможно, поменять формат.

|R200|99999|111111|CR,CS,AM|1|1|3022|222222|333333|||2011-06-23 11:33:58|C|2011-06-23 11:34:22|S|0|16|1||||||1|1||||||3|162|17|1|12|24|||||||||||16|0||||||192.168.1.172||192.168.1.12||||||8|8|20|20|64|64|20|0|0|OS|7777|8888|555555|666666|0|8|9||||OS|19|||30|10|42|43||||||||||||1||||||1|1|0|3||222222|||||||2|1||333333|||||||||||||||||||||||||||||||


Нас интересуют поля с индексами [7, 8, 9, 12, 14, 36, 112, 122], и в конечном результате хотелось бы отфильтровать всё ненужное, чтобы лишнего в СУБД не импортировать. Выбрав из сырых данных только нужное, получим строку:

Запись: 3022|222222|333333|2011-06-23 11:33:58|2011-06-23 11:34:22|24|222222|333333
Индексы: 7 |8 |9 |12 |14 |36|112 |122

Индексы | Объяснение
---------------------------
7 | код города Читы
8, 112 | исходящий номер
9, 122 | входящий номер
12 | дата и время начала разговора
14 | дата и время конца разговора
36 | длительность разговора в секундах


Все остальные поля особо не нужны. Некоторые, как вы видите, вообще пустые, а смысл прочих — неизвестен. Разве что IP-адреса (изменены) принадлежат двум платам в инфраструктуре телефонной сети, между которыми пойдет RTP-трафик. Импортировав эти поля, можно было бы изучить нагрузку на платы. Возможно, в будущем пригодится.

Записи в трафике идут плотно, строка за строкой. Возможно, есть какие-то другие типы записей, но они нам не интересны. Для тарификации достаточно только записей типа R200. Однако, во время визуального исследования трафика выяснилось еще одно интересное обстоятельство. Иногда попадались звонки с одного номера, начавшиеся в одно и то же время, но длительность их была разная. Сначала, в условиях неполной информации я подумал, что это какой-то глюк, ведь не может же человек звонить параллельно с одного и того же номера. Потом стала просматриваться закономерность, и, наконец, я понял, в чем дело. Вот пример таких записей на один номер телефона, все лишние поля я для наглядности выбросил:

|7 |8 |9 |12 |14 |36 |
|3022|222222|333333|2011-05-23 13:07:54|2011-05-23 13:37:54|1800|
|3022|222222|333333|2011-05-23 13:07:54|2011-05-23 13:59:40|3106|

|3022|444444|555555|2011-05-23 14:53:52|2011-05-23 15:23:52|1800|
|3022|444444|555555|2011-05-23 14:53:52|2011-05-23 15:53:52|3600|
|3022|444444|555555|2011-05-23 14:53:52|2011-05-23 16:00:50|4018|

|3022|666666|777777|2011-05-23 19:15:55|2011-05-23 19:45:54|1800|
|3022|666666|777777|2011-05-23 19:15:55|2011-05-23 20:15:54|3600|
|3022|666666|777777|2011-05-23 19:15:55|2011-05-23 20:45:54|5400|
|3022|666666|777777|2011-05-23 19:15:55|2011-05-23 20:47:17|5483|


Вам-то сейчас видно, в чем соль, а тогда мне эти записи среди тысяч им подобных, среди кучи лишних полей, букв и цифр, найти было нелегко. В общем, это было или везение, или интуиция, или волшебство. А разгадка проста: оборудование каждые полчаса (1800 секунд) отмечает «веху разговора» на случай, если что-то произойдет. Даже если последние 29 минут разговора были почему-то утеряны, весь предыдущий трехчасовой дискурс был многажды зафиксирован — для пущей надежности. В последней записи будут актуальные данные. Возможно, на оборудовании длительность вех можно как-то изменить, а пока их ряд выглядит так: [1800, 3600, 5400, 7200, 9000, over 9000..] Здесь еще примечательно то, что запись-веха отличается в нескольких «неважных» полях от записи-результата. Возможно, стоит учесть это в будущем, чтобы более качественно отфильтровывать ненужное, а пока я принял решение все записи с длительностью из этого ряда просто выбрасывать. Теоретически, здесь какой-то малый процент нормальных звонков будет утерян, но для этого нужно, чтобы человек разговаривал полчаса в точности до секунды. Вероятность этого очень-очень маленькая, а объемы у нас не такие значительные, чтобы закон больших чисел как-то повлиял на выборку. Мы назвали это явление творчески: «Проблема 1800 секунд».

Кратко о программах

Всего я создал четыре программы, которые сливали нужные файлы и отфильтровывали полезную информацию. Первоначально это были parser и merger — две программы, написанные по отдельности и соединенные в третью, тоже названную merger. Все они работали крайне медленно и потребляли много памяти, хотя с задачами справлялись. Данные одного месяца (3000 файлов по 240 строк = 720000 строк) они могли обрабатывать, минимум, 10 минут с отжиранием 500 мб памяти (а то и больше, ведь работал своп). Очень, очень страшный результат. И хотя задачу надо было выполнять 1 раз в месяц, мой напарник презрительно морщил нос на Haskell. Правда, Haskell тут ну совершенно ни при чем; это я допустил в программах ряд типичных ошибок начинающего функциональщика, из-за чего кривые алгоритмы работали из рук вон плохо. Но работали! Даже больше: программы (а самая большая из них занимает всего лишь 150 полезных строк) можно было настроить из командной строки. Вот какие функции были доступны:

1. Работа в режиме без параметров. Поля берутся по умолчанию, берутся файлы прошлого месяца.
2. Работа в режиме с параметрами:
— Fields [<список индексов полей>] — какие поля взять (parser Fields [1, 24, 55]);
— (yyyy, mm) — какой месяц обрабатывать (merger (2011, 5));
-W — не закрывать консольное окно после отработки (от слова «wait»).
3. Получались три файла:
— yyyy.mm.txt — в него сливались все файлы с сырым трафиком за этот месяц;
— processed.txt — файл только с нужными полями за этот месяц;
— yyyy.mm.txt.log — файл-лог, где перечисляются задействованные сырые файлы и пишется сводная информация (количество строк, файлов, диапазон дат).
4. Программы выводят на экран статистику и примеры обработанного трафика.

Пару-тройку раз мы пользовались, чем было, но потом я, конечно, переписал программу с нуля. Уж очень в старом коде было много кривого кода, ненужных велосипедов, глупых алгоритмов и странных решений. В итоге четвертая программа, NgnParser, при той же функциональности и на том же наборе данных работает не 10 минут, а 10 секунд, потребляя всего лишь 10 мб памяти. По скорости разница составляет почти два порядка и, как минимум, один — по памяти! Что можно было такого намутить, чтобы так замедлить программу? Полагаю, есть люди, наступившие на те же грабли, что и я, которые поверили скорее в тормознутость языка, чем в свои кривые руки, — недаром в Интернете так много воплей по поводу и без повода… Haskell — замечательный язык. Мне было легко писать эти программы. На каждую я тратил не более двух рабочих дней. И всякий раз получал море удовольствия. Не представляю, сколько было бы мучений, если бы то же самое я делал на C.

Первая программа

Первую программу я начал с простого. Покамест я сливал нужные файлы в один (merged.txt) средствами командной строки, а задача parser'а была в парсинге трафика и отфильтровывании нужных записей с идентификатором R200. Для обработки большого количества текста целесообразнее использовать специальный тип строки ByteString. Но работать с ним не так удобно, как с обычным типом String. Если ByteString — это оптимизированная реализация строки как таковой, то String — это список символов, то есть, [Char]. String, благодаря своей природе, очень удобен, но на больших данных производительность любых списков резко падает. В первых версиях программы именно String и несколько глупых решений стали причиной сильных тормозов и большого пожирания памяти. Однако, меня тогда волновала скорость разработки, а не производительность. Прототип программы я написал очень быстро. Вот как он выглядит (ревизия 2):

replaceChars :: Char -> Char -> Char -> Char
replaceChars whatC withC c = if c == whatC then withC else c

interestFields :: [String] -> [Int] -> [String]
interestFields s takeWhat = undefined -- Заглушка

isR200 :: [String] -> Bool
isR200 s = (head s) == "R200"

processLine :: String -> String
processLine s = if isR200 sInWords then unwords (interestFields sInWords [1,2,3] ) else [] -- [1,2,3] - тестовые поля
where sInWords = words ( map (replaceChars '|' ' ') s )

processString :: String -> [String]
processString s = map processLine (lines $ s)

main :: IO ()
main = do
str <- readFile "merged.txt"
putStrLn (intercalate "\r\n" (processString $ str))


Сразу можно заметить странную функцию replaceChars с типом Char -> Char -> Char -> Char. Идея была такая: берем строку-запись, заменяем вертикальную черту '|' на пробел и используем функцию words для разбиения строки на слова:

sInWords = words ( map (replaceChars '|' ' ') s )


В результате выполнения sInWords получится следующее преобразование:

"|R200|99999|111111|CR,CS,AM|1|1|3022|222222|333333|||2011-06-23 11:33:58|" -->
" R200 99999 111111 CR,CS,AM 1 1 3022 222222 333333 2011-06-23 11:33:58 " -->
["R200", "99999", "111111", "CR,CS,AM", "1", "1", "3022", "222222", "333333", "2011-06-23", "11:33:58"]


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

Замена ' ' -> '*';
Замена '|' -> ' ';
Разбиение на слова функцией words;
Обработка списка полей, получение полей с нужным индексом;
Слияние полей функцией unwords;
Замена ' ' -> '|'
Замена '*' -> ' '

Кроме того, после этих жутких преобразований количество полученных полей не совпадало с количеством исходных, — ведь пустые поля в итоге вообще исчезали (см. пример преобразования выше). Хорошо, что во всех записях пустые/заполненные поля были на одних и тех же местах, а не то б я получил неприятные артефакты. Код, как вы видите, не только избыточный, но и некрасивый. Я даже не берусь оценить его асимптотическую сложность; думаю, она далеко превысила O(n^2). Более того, ближе к ревизии 12 я понял, что надо что-то делать с полями, которые теряются из-за двойных вертикальных черт. И добавил еще одно преобразование:

-- Чтобы пустые поля, обозначенные как "||", обрабатывались корректно, между ними вставляется пробел.
refieldDoubles :: String -> String
refieldDoubles [] = []
refieldDoubles ('|':[]) = "|"
refieldDoubles ('|':'|':ss) = "| |" ++ (refieldDoubles ('|':ss))
refieldDoubles (s:[]) = [s]
refieldDoubles (s:ss) = s : (refieldDoubles ss)


Тем самым добавил еще один полный проход по каждой строке! Вот уж во истину — мартышкин труд. А ведь нужно было-то совсем немного: вместо всего этого использовать функцию split из модуля Data.String.Utils, или написать свой вариант. Тогда всего лишь за один проход по строке-записи я бы получил правильное разбиение на поля:

split "|" "|R200|99999|111111|CR,CS,AM|1|1|3022|222222|333333|||2011-06-23 11:33:58|" ->
["","R200","99999","111111","CR,CS,AM","1","1","3022","222222","333333","","","2011-06-23 11:33:58",""]

Что сказать… facepalm Слов нет, одни эмоции.

Какие возможны улучшения

Опытные хаскеллисты уже заметили, что в коде не используется бесточечный стиль (я его еще не прочувствовал на тот момент), и case-конструкций, сопоставления с образцом или там каких-нибудь охранных выражений почти нет. В итоге даже такой простой код читать местами тяжело. Вот как лучше было бы записать несколько функций:

replaceSymbols s = map (replaceChar '|' ' ') (map (replaceChar ' ' '*') s)
-- -->
replaceSymbols = map (replaceChar '|' ' ' . replaceChar ' ' '*')


isR200 s = (head s) == "R200"
-- -->
isR200 ("R200":_) = True
isR200 _ = False


replaceChars whatC withC c = if c == whatC then withC else c
-- -->
replaceChars whatC withC c | c == whatC = withC
| otherwise = c


processLine s = if isR200 sInWords then unwords (interestFields sInWords [1,2,3] ) else []
where sInWords = words ( map (replaceChars '|' ' ') s )
-- -->
processLine s | isR200 sInWords = unwords (interestFields sInWords [1,2,3] )
| otherwise = []
where sInWords = words . map (replaceChars '|' ' ') $ s


processString s = map processLine (lines $ s)
-- -->
processString = map processLine . lines


Функцию intercalate "\r\n" вообще нужно было заменить на unlines. Было бы и короче, и понятнее, да и в тестах unlines показал большую производительность — не менее 30%:

ItemsCnt testUnlines(ns) testIntercalate(ns) Percent
10 23.84 34.05 29.9
100 22.70 34.62 34.4
1000 23.28 35.48 34.3
10000 22.17 35.48 37.5
50000 22.13 33.26 33.4
100000 21.06 35.47 40.6
200000 22.70 34.05 33.3


Но будучи еще неопытным, я плохо знал стандартные функции даже из модуля Prelude, из-за чего городил ненужные велосипеды. Хотя, я даже сейчас не очень понимаю, как можно минимальными усилиями выбрать элементы с нужными индексами из списка элементов. Сравним код из старой и новой программы:

-- Старый код:
-- Аргумент 1 - список сырых поелй
-- Аргумент 2 - список нужных индексов
takeInterest :: [String] -> [Int] -> [String]
takeInterest _ [] = []
takeInterest ss (n:ns) = [ss !! n] ++ takeInterest ss ns

-- Новый код:
-- Аргумент 1 - аккумулятор
-- Аргумент 2 - список нужных индексов
-- Аргумент 3 - список сырых полей
collectFields :: Int -> [Int] -> [String] -> [String]
collectFields _ _ [] = []
collectFields idx fis (s:ss) | idx `elem` fis = s : collectFields (idx+1) fis ss
collectFields idx fis (s:ss) | otherwise = collectFields (idx+1) fis ss


В первом случае мы итерируем список индексов и вытаскиваем элемент с помощью небезопасной функции !!. Во втором случае используем аккумулятор одновременно с итерацией по списку полей, и если аккумулятор нашелся в списке индексов, берем текущее поле с индексом аккумулятора в коллекцию. И там, и там — хвостовая рекурсия. Хотя, по тестам, новый код оказался на 40% медленнее. Возможно, в данном случае стоит вернуть старый код, — еще больше ускорить новую программу.

ItemsCnt takeInterest(ns) collectFields(ns) Percent
10 17.33 36.84 52.9
100 20.58 36.84 44.1
1000 21.67 37.92 42.8
10000 21.13 36.84 42.6
50000 21.67 37.92 42.8


Идем дальше

Следующая программа — merger — должна была соединять все текстовые файлы за прошлый месяц в один. (Не хотелось каждый раз делать это вручную, а лень, как известно, движитель прогресса.) Возник вопрос: откуда узнать, какой у нас будет прошлый месяц? Да, в общем-то, это просто: берем текущую дату и отнимаем один месяц. Программа должна была использоваться исключительно в первых числах месяца, так что тут проблем не предвиделось. Текущая дата и вообще операции с датой-временем находятся в модуле Time. Операции со структурой файловой системы лежат в модуле System.Directory. И те, и другие функции, в основном, работают в монаде IO, а в то время я еще толком не умел причесывать монадный код, в итоге он выглядит жутко (merger, ревизия 14):

main :: IO ()
main = do
args <- getArgs
curDir <- getCurrentDirectory
dirContents <- getDirectoryContents curDir
curTime <- T.getClockTime
monthAgoTime <- return $ T.addToClockTime (T.TimeDiff 0 (-1) 0 0 0 0 0) curTime
calendarMonthAgoTime <- T.toCalendarTime monthAgoTime
let maybeDateRange = case args of
(a:b:_) -> readDateRange (unwords [a, b])
_ -> Just $ defaultDateRange calendarMonthAgoTime
case maybeDateRange of
Just dr -> do
let fsToMerge = filesToMerge dirContents dr
let fsToMergeCountStr = show $ length fsToMerge
let mergeLog = (newFileName dr ++ ".log")
let dateRangeMsg = "DateRange: " ++ show dr
fsContents <- merge fsToMerge
writeFile (newFileName dr) (unlines fsContents)
writeFile mergeLog (unlines fsToMerge ++ printf "\n%s\nTotal files: %s" dateRangeMsg fsToMergeCountStr)
putStrLn (unlines fsContents)
putStrLn dateRangeMsg
--putStrLn ("Files to merge: " ++ unlines fsToMerge)
putStrLn (printf "Count of files: %s. See %s for file list." fsToMergeCountStr mergeLog)
Nothing -> putStrLn ("Invalid date range.")


Что этот код делает — даже не рекомендую вникать… Но именно здесь закрался росток будущей огромной ошибки, из-за которой последняя версия старой программы пожирала огромное количество памяти. Рассмотрим функцию merge, которая вызывается из этого кода:

merge :: [String] -> IO [String]
merge fsToMerge = mapM readFile fsToMerge


Она принимает список файлов, которые надо смержить, читает их и возвращает список их содержимого. В коде есть такие две строчки:

do
...
fsContents <- merge fsToMerge
writeFile (newFileName dr) (unlines fsContents)
...


Ключевой момент — unlines fsContents. То есть, все сырое содержимое всех файлов соединялось в один присест и запихивалось в файл-результат. В последствии, когда parser и merger были объединены, именно этот огромный объем данных передавался в обработку parser-части, где, вы помните, есть целая куча замен, проходов и прочего оверхеда. Вот как выглядит эта часть кода в старой программе, собранной из parser и merger:

do
...
fsContents <- readFilesToMerge fsToMerge
let mergedContents = unlines fsContents
writeFile (newFileName dr) mergedContents
let processedContentStr = unlines $ processData nedeedFields mergedContents
...


И это не просто facepalm плохо, это грубейшее нарушение dataflow-концепции. Должно быть так:

Схема 1
_____ _____ _____
| | | | | |
A1 -> |F(A1)| -> B1 -> |G(B1)| -> C1 -> |H(C1)| -> RESULT 1 -> SAVE
|_____| |_____| |_____|

_____ _____ _____
| | | | | |
A2 -> |F(A2)| -> B2 -> |G(B2)| -> C2 -> |H(C2)| -> RESULT 2 -> SAVE
|_____| |_____| |_____|

_____ _____ _____
| | | | | |
A3 -> |F(A3)| -> B3 -> |G(B3)| -> C3 -> |H(C3)| -> RESULT 3 -> SAVE
|_____| |_____| |_____|


...-> ... -> ... -> ... -> ... -> ... -> RESULT n -> SAVE


А получилось так:

Схема 2
____________________ ____________________ ____________________
| | | | | |
| | | | | |
| | | | | |
A->| F(A) |->B->| G(B) |->С->| H(С) |->RESULT->SAVE
| | | | | |
| | | | | |
|____________________| |____________________| |____________________|


Разницу между последовательной обработкой частей и обработкой всего сразу я прочувствовал в полной мере. Теперь я знаю: не стоит брать весь объем работ сразу, лучше создать механизм, который выдает данные порциями, — так будет и по памяти эффективно, и по скорости лучше. И, кроме всего прочего, программу, сделанную по второй схеме, нельзя распараллелить. Ужас, одним словом…

Позже я пытался соптимизировать старую программу, — заменял почти везде String на ByteString. Выигрыш, конечно, был небольшой, но — веером тумана не разгонишь.

Надо ли говорить, что новую программу, NgnTraffic, я делал, имея уже нормальный запас знаний? В ней соблюдено многое. Программа разбита на модули: Main, Constants, DataProcess, FileListProces, Options, Tools, Types. Используется, конечно, схема 1. Вместо String изначально взят тип ByteString (Strict-вариант). Код более причесан, даже бесточечный стиль в наличии. И, главное, поменялся принцип действия. Сначала собирается список файлов, которые нужно обработать, — эта часть похожа на аналогичную из старой программы. Затем, однако, файлы не читаются все сразу в одну большую переменную, а каждый читается по отдельности. Его содержимое тут же обрабатывается, строки парсятся, записи фильтруются, нужные поля вытаскиваются. Результат дописывается в результирующий файл. В итоге имеем цикл «Чтение с диска (F(An)) — Обработка строк (G(Bn)) — Запись результата на диск (H(Cn))» — и так много раз по числу файлов. Плюс, конечно, нет никаких замен одного символа на другой, а есть простая функция split из модуля Data.ByteString.Char8, которая за один проход разбивает строку-запись на поля и сама по себе выигрывает чудовищную долю производительности. Вот как выглядят функции, удовлетворяющие схеме 1:

process' :: ResFilePath -> FieldIndexes -> FilePath -> IO ()
process' resFile fis targetFile = do
fileContents <- C.readFile targetFile
let processResult = processData fis predicates fileContents
C.appendFile resFile processResult

process :: ResFilePath -> [FilePath] -> FieldIndexes -> IO String
process _ [] _ = return "No files to process."
process resFile fs fieldIndexes = do
C.writeFile resFile C.empty
mapM_ (process' resFile fieldIndexes) fs
return "All ok."


Здесь process принимает имя файла-результата, список файлов на обработку и индексы нужных полей. Индексы могут прийти из командной строки, поэтому они выведены как аргумент этой функции. process берет по очереди имя каждого файла и применяет к нему функцию process' (в строке mapM_ (process' resFile fieldIndexes) fs). Она уже занимается главной работой с файлами. Функция processData берет на себя обработку содержимого файла. Интересно то, что помимо фильтрования R200-записей в новой программе создан механизм предикатов: можно любое любую запись проверить по доступному предикату, а сами предикаты нетрудно дополнить нужным. Пока сделано два: поле с индексом x принадлежит списку полей и не принадлежит ему. Так выглядит тип предикатов:

data Predicate = NotInList [C.ByteString]
| InList [C.ByteString]
type PredicateMap = [(FieldIndex, Predicate)]


А это заданные предикаты-константы:

predicates :: PredicateMap
predicates = [(1, InList [C.pack "R200"]),
(36, NotInList (map C.pack ["1800", "3600", "5400", "7200", "9000", "10800", "12600", "14400", "16200", "18000", "19800", "21600", "23400"]) )]


Нетрудно догадаться, что предикатам будут удовлетворять только те записи, у которых поле 1 равно «R200», и поле 36 не содержится в списке «Проблемы 1800 секунд». Отсеивание происходит в функциях checkPredicate и examineFields:

checkPredicate :: Predicate -> C.ByteString -> Bool
checkPredicate (NotInList l) str = (not . elem str) l
checkPredicate (InList l) str = elem str l

examineFields :: Int -> PredicateMap -> Fields -> Bool
examineFields _ _ [] = True
examineFields idx preds (s:ss) = case L.lookup idx preds of
Just pred -> (checkPredicate pred s) && (examineFields (idx+1) preds ss)
Nothing -> examineFields (idx+1) preds ss


Сейчас я вижу, что функцию examineFields вполне можно было сделать через foldr, но это так, мелочи.

В целом, я доволен проделанной работой. Такое бывает редко, — но код NgnTraffic мне даже нравится. А особенно нравится тот прогресс, который стал виден на примере одной и той же программы, написанной в разное время и с разными знаниями. А «еще особеннее» нравится то, что это реальная программа на Haskell, использующаяся в реальном производстве.

Кто бы что ни говорил, — Haskell — потрясающий язык, лучший из тех, с которым мне приходилось работать.

Исходники parser по ревизиям: [2], [6], [12]
Исходники merger (в том числе и объединенная программа merger): [13], [14], [16], [23]
Исходники NgnTraffic

P.S. Перевод следующей части Yet Another Monad Tutorial тоже скоро будет.
P.P.S. Поправил ссылки на программы, спасибо товарищу steck.
P.P.P.S. Исправил пару ошибок, спасибо товарищам goder и jack128.
haskell, haskell in real world, ngnparser, traffic parsing
+31 7373
32graninas 0,0 G+
Похожие публикации

Ciklum Odessa Speakers’ Corners: 5 Dimensions of developing BIG REAL-WORLD CLOUD products
Haskell, как что-то очень близкое, или получаем комиты из github api (3)
Вебинар «User Experience in an Agile Process — When the Real World Comes Knocking» от датского дизайнера интерфейсов Trifork A/S Янне Юл Янсен
Haskell в продакте: Отчёт менеджера проекта (124)
Семинар «Why do people use short queries in real life? A session-based analysis of short query effectiveness» (1)
Комментарии (59) отслеживать новые: в почте в трекере

+2 tranquil27 сентября 2011 в 16:17#
Ключевой момент — unlines fsContents.

Не совсем. Ключевой момент на две строчки ниже — putStrLn (unlines fsContents).
Если это второе использование fsContents вырезать, то всё будет работать в константе памяти (если конечно нет других ошибок). Сборщик мусора должен всё собрать, а ленивый ввод-вывод не допустить полной загрузки содержимого файлов в память.

В хаскеле кроме чистых функций ленивость реализована в операциях ввода-вывода. Внутри merge readFile фактически начнёт читать в тот момент, когда данные потребуются. И будет читать их чанками фиксированного размера. Грубо говоря каждый чанк будет проходить обработку, записываться в writeFile и подчищаться сборщиком мусора. Если после этого на них него других ссылок, а у вас есть.
0 graninas27 сентября 2011 в 16:23#↵↑
Безусловно да. Но уже в ревизии 23 эта строчка преобразовалась в следующую:

putStrLn (unlines . take 100 $ processedStrings)

Это чтобы лишнее не выводить. Не скажу, правда, где именно возникают те дополнительные ссылки, которые мешают лениво читать и обрабатывать данные.
+1 tranquil27 сентября 2011 в 16:24#↵↑
Это всё равно ссылка на всю строку, которая непозволит сборщику очистить все элементы строки после 100
0 graninas27 сентября 2011 в 16:26#↵↑
А вот ради интереса завтра уберу строку и протестирую программу.
+3 tranquil27 сентября 2011 в 16:24#
Очень рекомендую эту главу RWH. Помогает бороться с проблемой поедания O(n) памяти. Которой обусловлены почти все проблемы «производительности».

А статья классная, хоть и сумбурная. Бесточечная нотация поначалу совсем не обязательна. И не только по началу.

Других способов получше разобраться с хаскелем как я понимаю нет. После руководств совсем не понятно как всё это используется на практике. Приходится просто писать.
0 graninas27 сентября 2011 в 16:25#↵↑
Большое спасибо!

Вообще да, эту главу я еще не читал, но уже почти собирался. Книга весьма хорошая, название этой статьи как бы намекает.
+5 erazer27 сентября 2011 в 16:49#
Линуксоиды бы использовали какой-нибудь Bash, Perl или Python, — дешево и сердито, но на Windows-машину их ради одной операции не поставишь, то же самое касается и PowerShell.

Звучит будто Haskell входит в стандартную поставку MS Windows.
+1 graninas27 сентября 2011 в 16:53#↵↑
Нет, но можно собрать исполняемый файл и использовать его на машине, где Haskell нет. Правда не знаю, можно ли скомпилировать программы на языках Perl и Python. Подозреваю, что можно.
+2 xryundel27 сентября 2011 в 17:26#↵↑
Для Perl'а можно, например, использовать PAR::Packer. Сгенерирует .exe-шник, в который будут засунуты все зависимые модули, библиотеки и perl'овый интерпретатор.
+2 Urevic28 сентября 2011 в 14:01#↵↑
Для Питона есть py2exe.
+1 Bonart29 сентября 2011 в 12:10#↵↑
PowerShell даже на Xp ставит банальный Windows Update. И exe с помощью PowerGui собать можно.Но статической типизации там нет, да.
НЛО прилетело и опубликовало эту надпись здесь
+1 graninas27 сентября 2011 в 17:55#↵↑
На самом деле проблема глубже. Что будет, если человек начинает длительный разговор в одном месяце, а заканчивает в другом? Ему два раза начислится сумма. А заранее знать не можем, трафика за следующий месяц может и не быть. Единственный выход — тарифицировать только запись с признаками, что она конечная, последняя.
+2 korum27 сентября 2011 в 17:52#
>>Линуксоиды бы использовали какой-нибудь Bash, Perl или Python
Эка вы поддели армию кодеров на этих языках )
0 tranquil27 сентября 2011 в 19:02#
Кстати что значит «хаскель в реальном мире»?
В этой задаче perl или python подошёл бы ничуть не хуже.

Технических проблем, связанных с написанием любого ПО, в хаскеле давно нет.
А никто не использует его просто потому, что он никому не нужен.
+2 erazer27 сентября 2011 в 20:27#↵↑
Думается, именно то и значит. Очевидно, автор не ставил себе цели доказать что-то кому-то — это удел адептов той или иной технологии. Мне показалось, автор попытался просто привести пример использования действительно «из жизни», — и это вполне получилось.
+3 voidlizard27 сентября 2011 в 21:26#↵↑
Насчет никому не нужен, не вполне понятно.

Хаскелл жив, развивается, догоняет Эрланг по некоторым возможностям (ForkIO, epoll/kqueue), но при этом является статически типизированным, со средствами метапрограммирования, компилируемым в нативный код, обладает оптимизирующим компилятором с llvm-ным бэкендом, обрастает библиотеками и пакетами, имеет несколько веб-фреймворков и много что еще.

Никому не нужен? А что нужно тогда?
+1 tranquil27 сентября 2011 в 21:34#↵↑
Никому не нужен в смысле не используется в бизнесе.

Все мейнстримные языки худо-бедно справляются со своими задачами.

Плюс к этому проблема курицы и яйца. На рынке труда нет вакансий инженеров-хаскелистов. Поэтому мало кто интересуется языком. Поэтому никто не использует его в проектах, т.к. боится недостатка кадров. Поэтому на рынке труда нет вакансий.
+1 voidlizard27 сентября 2011 в 21:41#↵↑
Это верно только в рамках странной предпосылки, что программист программирует обязательно на каком-то определенном языке и не в состоянии использовать другой.

Как выяснилось, на практике людей на хаскелл найти совсем несложно. Определенные преимущества при разработке он дает. Почему бы его не использовать?

Кстати, в бизнесе он используется. Но мало, да.
+2 tranquil27 сентября 2011 в 21:46#↵↑
Если он программирует на с++, то в состоянии использовать питон. Или с#. Или жаву.

Но другую парадигму он не в состоянии быстро начать использовать.

Просто разобраться хотя бы в нескольких концепциях хаскеля занятие не быстрое. А начать писать код с их помощью можно не известно через какое время. Хотелось бы на практике узнать длительность «втягивания» в процесс разработки на хаскеле с нуля.
+1 voidlizard27 сентября 2011 в 21:53#↵↑
Ну на практике, какое-то количество людей на рынке знакомы с функциональным программированием и хотели бы его использовать, просто нет шансов его где-то применить, потому что нет вакансий.

И на практике мы хаскелльную вакансию закрыли за неделю, а отклик был достаточный, что бы понять, что проблема с такими кадрами — скорее, страшилка.

Переехать с окамла на хаскелл можно дня за три. Окамл очень простой и осваивается недели за две, как и Эрланг, например. Хаскель, безусловно, сложнее, но писать на нём можно и не владея всеми концепциями; сложные вещи можно осваивать постепенно по мере надобности.

+1 tranquil27 сентября 2011 в 21:56#↵↑
А у вас это где если не секрет? И что за хаскельная вакансия? Закрыли опытным хаскелистом или переучивали?
+1 voidlizard27 сентября 2011 в 22:04#↵↑
Небольшая компания. Разрабатываем собственный продукт и ПО на заказ. Для операторов мобильной связи, например.

Вакансия — писать приложения на хаскелле. Клиент-сервер, работа с железом, веб и проч.

Насчет опытного не уверен, до этого он писал на PHP и вроде бы знал эрланг лучше, чем хаскелл, но это только вопрос практики.

Сейчас у нас пока эрланга больше, чем хаскелла, но я планирую новые проекты в основном начинать на хаскелле, ввиду его преимуществ. Там, где больше смысла использовать эрланг (SMPP, SNMP и прочие библиотеки) — будет эрланг.
+1 tranquil27 сентября 2011 в 22:15#↵↑
Я уже оказывается спрашивал.

Вот и подтверждение тому, что хаскель используют очень ограниченный круг людей.
+2 voidlizard27 сентября 2011 в 22:19#↵↑
Кто спорит? Но то, что его не используют другие, не повод же самому не использовать, если вещь годная?
+1 graninas28 сентября 2011 в 02:44#↵↑
Я не знаю, может, я какой-то особенный, но мне хватило пары недель, чтобы понять, как Хаскелль работает и что такое функциональное программирование. При том на первой неделе я уже писал простые арифметические программы вроде факториалов и чисел Фибоначчи. К концу месяца изучения вполне свободно использовал основные монады (IO, Maybe, []). И не заметил особых трудностей в этом языке. Я даже утверждаю, что С++ гораздо сложнее, запутаннее и непрозрачнее. Нормальные программы на нем начинаешь писать позже. Конечно, мы не говорим о качестве моих знаний, приобретенных за месяц, — и в статье убедительно показывается, где они были недостаточными.

Может быть, если это получится, я напишу и о процессе своего «втягивания» с нуля, — но тут история получится не слишком захватывающей. Все обыденно: писал себе и писал каждый день после работы, и как дите радовался, если что-то вдруг ни с того ни с сего заработало.
+1 GooRoo28 сентября 2011 в 11:52#↵↑
«…ни с того ни с сего заработало» — это сильно сказано
0 graninas28 сентября 2011 в 12:05#↵↑
Тут, я думаю, работало подсознание. В самом деле, я писал простенькие арифметические функции по разным примерам, еще не зная, с какой стороны подойти к языку. Просто писал что-то, внутри чего логика связей была такой же, как в примерах, с поправками на свою задачу. И оно почему-то начинало работать…
+2 tanenn27 сентября 2011 в 20:26#
За код на хаскеле спасибо, но решение странное и медленное. Во-первых, поставить, например, питон под вин не просто, а очень просто. Во-вторых, что касательно скорости. Я тоже работаю в провайдерской компании, только пишу софт для тарификации интернета. За одни сутки необходимо протарифицировать примерно 100 млн. трафиковых записей. Записи идут пачками по 100 000. Обработка такого объема проходит примерно за 6 секунд. Это агрегация, ассоциация, тарификация, расчет баланса. При этом идет активное общение с базой данных, что занимает чуть ли не половину времени работы. Жрет всё это дело 4-20 Мб оперативной памяти. Так что мне не кажется выбор хаскеля для этой задачи правильным.
+1 erazer27 сентября 2011 в 20:29#↵↑
Но ведь вам для вашей задачи никто и не предлагал использовать хаскель? Автору захотелось попробовать «чего-то эдакого» — он попробовал и у него получилось. Своими достижениями автор поделился с общественностью. Я не заметил чтобы автор делал какие-то категоричные утверждения касательно необходимости использования той или иной технологии для каких-либо видов задач.
+1 tanenn27 сентября 2011 в 20:39#↵↑
Я всего лишь привел пример производительности решения аналогичной задачи на питон. Я считаю, что каждой задаче свои инструменты. И, возможно, для задачи из топика и подходит хаскаль, но я прочитал только такие критерии выбора языка для реализации: «факторы как-то так удачно сложились». Против статьи же вообще ничего против не имею, статья интересная и полезная.
И я не заставляю использовать питон, но при этом считаю, что он лучше подходит для этой задачи.
+1 erazer27 сентября 2011 в 20:56#↵↑
Я веду к тому что автор ведь не утверждал, что данная задача подходит для хаскеля или наоборот. Соответственно и пытаться это оспорить просто бессмысленно. Захотелось автору именно такую задачу решить именно на хаскеле — и все дела. А народ начинает спорить о том, какой ЯП больше подходит для данной задачи — да статья-то вообще не об этом!
+1 tranquil27 сентября 2011 в 21:09#↵↑
http://shootout.alioth.debian.org/u64q/benchmark.php?test=all&lang=ghc&lang2=python3

бенчмарки не считают что питон лучше подходит в плане производительности
+1 philpirj27 сентября 2011 в 21:50#↵↑
По вашей ссылке показывается, что на идентичных задачах питоновский код вдвое короче. Его можно выбрать для некритичных к производительности задач. Возможно, что краткость исходников обусловлена отсутствием статической типизиции.
+3 tranquil27 сентября 2011 в 21:55#↵↑
В этом случае длинна хаскельных исходников обусловлена чрезмерной оптимизацией.
+1 Bonart29 сентября 2011 в 12:21#↵↑
Для ультимативной скорости при равной кривизне рук хаскель подходит лучше — ибо оптимизирующий компилятор.
Для ультимативной надежности при тех же равных — опять лучше хаскель ибо сильная статическая типизация.
Но если функциональщина еще не вошла в мозг — то рулит питон, повершелл и т.п.
+3 voidlizard27 сентября 2011 в 21:14#↵↑
Подобные файлы скорее всего легко парсятся fsm, а значит, заметного отставания, например, от Си в этом вопросе не будет. Файловый ввод-вывод на байтстрингах тоже не уступает; вот например рассчет sha1 от файла:

fileHash :: FilePath -> IO FileHash
fileHash f = do
content <- L.readFile f
let hash = H.hashlazy content
return $ concatMap (printf "%02x") (B.unpack hash)

этот код работает ровно со скоростью стандартной sha1sum

Хаскелл быстрее и питона, и перла. И у него очень простой и удобный FFI, который позволяет выносить критичные места в Си, если это нужно. Но это нужно крайне редко.

Вот например рассчет crc16 на Haskell и С. Задача для хаскелла нехарактерная, однако справляется не сильно хуже, чем тот же Си. Так что не надо нездорового ажиотажа, Хаскелл — ок. Другое дело, что при наивных реализациях он начинает внезапно сливать. Тот же приведенный выше код рассчета SHA1 от файла при тупой реализации в лоб жрал память и не завершался. Практика нужна, и всё.

+1 tanenn27 сентября 2011 в 21:32#↵↑
Я лишь привел пример как уже есть в моем варианте. Сравнивал я с показателями из статьи. Я не гуру в Haskell, я просто сравнил то, что есть у меня и то, что показал автор. В моем варианте идет обработка 3 млрд. трафиковых записей в месяц онлайн и даже не чихает и есть запас в разы. Может я как-то неправильно сравнил, может реализация автора подкачала, может задача не для хаскеля. Я не знаю, я просто попытался сравнить и привести пример.
+2 voidlizard27 сентября 2011 в 21:38#↵↑
Но вы при этом сразу делаете вывод, что хаскелл не подходит.

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

Я не вникал детали того, что конкретно делал автор, но если он не использовал для парсинга своих файлов attoparser или happy/alex или bnfc — значит, скорее всего делал что-то не то, какой смысл парсить это вручную вообще, да еще и медленно.

+1 tanenn27 сентября 2011 в 21:45#↵↑
«делаете вывод, что хаскелл не подходит». Я не просто так его сделал, я посмотрел, что получил автор в результате и решил, что не подходит. Сугубо на фактах из статьи, конкретно в данном случае. Мой же пример еще и активно тарифицирует (это портянка парсилка/считалка тарифов на 2000 строк на питоне) и пишет в базу.
А то, что хаскель язык общего назначения я в курсе, и мне хаскель нравится, и я периодически пытаюсь подтрягивать знания о нем. И еще одно «но». «Язык общего назначения» это вовсе не значит, что язык можно использовать везде, где не лень с практической точки зрения. Можно и на C++ реализовать установочные скрипты, например, но куда быстрее и приятнее это сделать на bash или python.
+1 voidlizard27 сентября 2011 в 21:54#↵↑
Вы сравнили разный код для разных задач, написанный разными людьми с разным уровнем владения инструментом.
+1 tanenn27 сентября 2011 в 21:56#↵↑
Каюсь, что ж теперь.
0 graninas28 сентября 2011 в 03:07#↵↑
Я более чем уверен, что даже моя вторая, эффективная, программа может быть улучшена по многим показателям. Я пока еще не гуру Хаскелля.
+1 Defined30 сентября 2011 в 00:36#↵↑
Тоже самое можно сказать и о Perl, легко ставится под винду, задача как раз для него, и со строками справляется лучше всех =)
не Питоном единым сыты
+1 mclander28 сентября 2011 в 00:57#
Прочитал о воркарраунде с заменой пробела звездочкой и окончательно убедился, что люди готовы на любое извращение, лишь бы ничего не знать об «этих жутких регэкспах».

* Правда сам грешен сегодня выкусывал из html'a кусок типа $.get(url, function(s){ $("#id").html( $s.substring(s.indexOf('>', s.indexOf('<BODY'))+1, s.indexOf(''))); });
0 graninas28 сентября 2011 в 03:09#↵↑
Можно было бы и регэкспы. Было бы интересно сравнить производительность разных решений.
+1 tranquil28 сентября 2011 в 10:50#↵↑
Есть мнение что об «этих жутких регекспах» действительно можно ничего не знать.

Есть такая штука как комбинаторы парсеров. Они легче понимаются чем регекспы, их легче читать. И они позволяют решать гораздо больше задач. Так как могут парсить контекстно свободные грамматики, которые шире чем регулярные грамматики.

Комбинаторы парсеров в питоне, в хаскеле.

ipAddr :: GenParser Char st Word32
ipAddr = do
as <- many1 digit
let a = read as
when (a > 255) $ fail "ip address octet must be >= 0 && < 256"
char '.'
bs <- many1 digit
let b = read bs
when (b > 255) $ fail "ip address octet must be >= 0 && < 256"
char '.'
cs <- many1 digit
let c = read cs
when (c > 255) $ fail "ip address octet must be >= 0 && < 256"
char '.'
ds <- many1 digit
let d = read ds
when (d > 255) $ fail "ip address octet must be >= 0 && < 256"
eof
return $ shiftL a 24 + shiftL b 16 + shiftL c 8 + d
0 graninas28 сентября 2011 в 11:13#↵↑
И так тоже можно было бы…
+1 mclander28 сентября 2011 в 12:03#↵↑
интересно. действительно интересно.

но человека который так решил приведенную задачу я бы на работу не взял, как и человека написавшего регэксп. в этой задаче обычного split выше крыши
0 graninas28 сентября 2011 в 12:09#↵↑
Я вас не совсем понимаю. split в полной мере используется в новой версии программы. А в начале своего пути я, конечно, дал маху с заменами символов, но это было по неопытности. Вряд ли можно корить начинающего в том, что он начинающий.
+2 tranquil28 сентября 2011 в 12:47#↵↑
Это задача парсинга пользовательского ввода.

Сплит это конечно хорошо. Но там ещё нужен один ифник для проверки того, что октетов 4. И ещё проверки того, что не встретились посторонние символы. А может тестировщик найдёт и другие проблемы.

Здесь мы получаем автоматическую генерацию сообщений об ошибках. Введена буква? Библиотека внутри сгенерит ошибку «expected digit». 3 октета вместо 4, будет сгенерина ошибка «unexpected eof, expected digit or '.'», если октетов больше 4, будет сгенерина ошибка «unexpected '.', expected eof». И это всё уже внутри этого кода.

Кроме того, этот подход универсален. Эта функция парсит ip адрес, другие функции в этом модуле точно так же парсят более сложные вещи. Ip-адрес конечно можно распарсить сплитом и регекспом. Но, например, выражение со скобками нельзя.

Используя комбинаторы парсеров везде, мы получаем выйгрыш в универсальности.
0 mclander28 сентября 2011 в 13:19#↵↑
Это смешение теплого и мягкого — сплиты применяются для разбора структурированных данных, регэкспы для быстрой проверки/выкуса конкретного фрагмента.

Более серьезный парсинг требует серьезных средств. Синтаксис регэкспов (если без фанатизма) настолько прост, что нет повода его не применять. Там где он даст выигрыш, например подсчитайте с помощью парсеров количество слова регэксп (и его склонений) в моем посте.

scalar($post =~ /\bрегэксп/mgo);

+2 mclander28 сентября 2011 в 12:34#
я имел ввиду пример с парсингом ip

а по поводу вашей программы… могу сказать только одно — вы молодец.

любая решенная задача (не важно каким методом или какими средствам) это плюс в карму в реале)
+1 pro100tak28 сентября 2011 в 16:36#
Чур какашками не кидаться, но у меня парсер access-logs, разбитых с помощью cronolog на файлы по 1 минуте работает достаточно шустро: просто парсинг без базы данных и др. логики — 4 минуты на ~15 млн. записей (лог за месяц).
0 graninas28 сентября 2011 в 17:28#↵↑
Ну что вы так сразу — «не кидаться»… Здесь вроде бы культурные люди собрались. А иным Haskell и не интересен.

Видимо, это хороший результат — 15 млн. записей за 4 минуты… Но мне кажется, можно было еще быстрее. То есть, у меня 10 сек. = 700 000 записей, 1 мин. = 4 200 000 записей. На 4 минуты это уже 16 млн… То есть, примерно как у вас. Я хочу еще больше оптимизировать свою программу, благо, пути для этого наметились. Если выйдет что-нибудь интересное, опять будет топик.
+1 pro100tak28 сентября 2011 в 18:13#↵↑
Если ценой одного рабочего дня производительность поднимется на 10% для операции периодической и некритичной — то ну его нафиг такую оптимизацию Есть куча критичных задач, да и сервера свои и за процессорное время и т.д. мы не платим.
0 graninas29 сентября 2011 в 02:44#↵↑
Ну а у меня это просто повод изучить оптимизацию в Haskell.
+1 sergeypid28 сентября 2011 в 18:07#
Интересно, как некоторые языки прочно привязаны к одной области применения. Например хаскель, эрланг настолько прочно к биллингу в сотовых сетях, что вот и эта статья про биллинг, и в комментариях есть «Небольшая компания. Разрабатываем собственный продукт и ПО на заказ. Для операторов мобильной связи, например.»

В каких еще областях у хаскеля есть success stories? Просто интересно.
0 graninas29 сентября 2011 в 02:58#↵↑
На самом деле применения есть, но, конечно, их мало в сравнении с другими языками. На странице «Haskell in industry» приводится несколько десятков успешных программ на Haskell. Из них:

* ИИ для оборонной промышленности
* Обработка ДНК в терапевтической компании
* Симуляторы для тестирования беспроводного оборудования
* В Bank of America Merril Lynch Haskell используется как бэкенд для обработки данных
* И многое другое

[dyvniy]

Превращение С++ в Haskell
http://habrahabr.ru/post/205026/

Спойлер

Монады и do-нотация в C++ из песочницы
Haskell*, C++*
В Хаскеле как известно есть монады, а в C++ их нет. Но ничто не мешает реализовать монады в С++. Посмотрим есть ли у нас всё необходимое для их реализации:
Передача функции как аргумент в другую функцию – есть.
Лямбда-функции – есть, добавлены в C++11. Я не уверен, что они необходимы для реализации монад, но с ними, несомненно, проще.
Type classes – нет. В C++ хотели добавить их аналог – концепты, но пока не добавили. Но для реализации монад они не нужны, можно просто перегружать функции или операторы под конкретные монады.
do-нотация. В C++ её нет, но для реализации монад она не нужна, хотя и делает их использование гораздо более удобным. Уже есть предложение добавить её аналог в стандарт, но об этом ниже.

Монада в Haskell определяется следующим образом:
class Monad m where
(>>= ) ::m a -> (a->m b)->m b
(>> ) ::m a->m b->m b
return ::a->m a
fail::String->m a

Для начала возьмём некую абстрактную монаду, пусть в C++ она имеет тип Monad<T>. Посмотрим, как будут выглядеть соответствующие функции.
template<typename A, typename B>
Monad<B> operator>>=(Monad<A> ma, function<Monad<B> (A)> f)
{
... // реализация зависит от монады
}
Эта функция извлекает значение из объекта ma, подставляет в функцию f и возвращает результат f.

template<typename A, typename B>
Monad<B> operator>>(Monad<A> ma, Monad<B> mb)
{
return Ma >>= [=](A){ return mb; };
}
Эта функция аналогична функции >>=, но она игнорирует значение извлечённое из первой монады. У этой функции есть стандартная реализация (m >> k = m >>= \_ -> k), которую я перевёл с Haskell на C++.

template<typename A>
Monad <A> mreturn(A a)
{
... // реализация зависит от монады
}
Слово return является зарезервированным в C++, поэтому я назвал эту функцию mreturn. Смысл этой функции в том, что она помещает объект a в некий минимальный контекст для данной монады.
Функция fail нужна для обработки ошибок, чтобы не загромождать эту статью я её опущу.

Итак, теперь понятно как будут выглядеть монады на C++, настало время взять какую-нибудь конкретную монаду и реализовать для неё эти функции. Можно конечно начать с монад типичных для Хаскеля — Maybe, список и др., но меня больше интересует std::future. Этот класс был добавлен в C++11. Объект типа future<T> позволяет получить доступ к объекту типа T, который будет доступен в будущем. Это может быть, например, результат вычисления какой-то очень сложной функции, которая долго вычисляется в другом потоке, или результат ввода, например информация, которая должна будет поступить по сети. Из всего класса future нас будет интересовать только функция get.
template<class T>
class future
{
public:
...
T get(); // функция get дожидается пока будет доступен объект и возвращает его
...
};

Также в C++11 появилась новая функция – std::async. В качестве аргумента она принимает функцию, запускает её в другом потоке и возвращает её результат в std::future. То есть можно писать код навроде этого:
future<int> result = async(f);
// делаем какие-то операции одновременно с вычислением функции f
int a = result.get(); // дожидаемся выполнения функции f и получаем её рузультат.

Теперь нам не составит труда реализовать функции mreturn и >>= для монады std::future
#include <future>
using namespace std;

template<typename A>
future<A> mreturn(const A& a)
{
return async([=]{ return a; });
}
То есть, чтобы поместить уже известное значение в future мы вызываем в другом потоке функцию, возвращающую наше значение. Это не самый эффективный способ, зато простой и понятный.

template<typename A, typename B>
future<B> operator>>=(future<A>& ma, const function<future<B> (A)>& f)
{
return async([&] () -> B { return f(ma.get()).get(); });
}
Здесь немного посложнее, мы создаём новый поток, в котором дожидаемся пока будет готово значение из ma, потом передаём это значение в функцию f, затем ждём пока будет готово значение возвращённое из f.

Реализация готова, осталось проверить выполняются ли аксиомы монад. Всего у нас 3 аксиомы, которые на Хаскеле выглядят так:
Left identity : return a >>= f == f a
Right identity: m >>= return == m
Associativity: (m >>= f) >>= g == m >>= (\x -> f x >>= g)

Переводим первую аксиому на C++, получается:
(mreturn(a) >>= f) == f(a)
Подставим наши функции, получим:
async([&] () -> B { return f(mreturn(a).get()).get(); }) == f(a)
Ясно, что mreturn(a).get() это тоже самое, что а. Эта конструкция просто помещает a в std::future, а затем извлекает его оттуда. Упрощаем, получаем:
async([&] () -> B { return f(a).get(); }) == f(a)
Эта операция, вообще говоря, не эквивалента непосредственному вызову f, так как здесь функция вызывается в другом потоке. При определённых условиях, например если f является чистой, эти операции внешне будут эквивалентны (за исключением времени выполнения).

Вторая аксиома:
m >>= mreturn == m
Подставим наши функции, получим:
async([&] () -> B { return mreturn(m.get()).get(); }) == m
Мы опять можем избавиться от mreturn(x).get(), получим:
async([&] () -> B { return m.get(); }) == m
Теперь ясно, что выражение слева эквивалентно m. Оно просто создаёт поток, который дожидается пока будет доступно значение из m.

Третья аксиома:
(m >>= f) >>= g == m >>= (\x -> f x >>= g)
Рассматривать подробно третью аксиому мне уже лень, но грубо говоря, она означает следующее. В выражении слева к фьючеру m навешивается функция f, которая будет выполнена, когда будет доступно значение из m. Затем на полученную конструкцию вешается функция g, которая будет выполнена после f. В выражении справа функции f и g сперва объединяются в одну функцию и затем уже она вешается на фьючер m.

С аксиомами мы разобрались. Теперь можно написать какой-нибудь бессмысленный код с нашей монадой:
function<future<int> (int)> f = [](int a){ cout << a << '\n'; return mreturn(a + 6); };
int a = (mreturn(5) >>= f).get();
cout << a;
Как и ожидалось, этот код выводит 5 и 11.

В C++11 нет функций аналогичных написанным мной mreturn и >>=. Но есть предложение добавить подобные функции: n3721
Аналогом mreturn будет make_ready_future.
Аналогом >>=, будет функция класса std::future под названием then. Основное её отличие в том, что она принимает аргумент не типа A, а типа future<A>. Это сделано для обработки ошибок, если нужное значение так и не будет сгенерировано, то получится future<A> содержащий ошибку и функция, переданная в then, сможет его обработать.
Также планируется добавить функцию unwrap которая сможет преобразовывать значения типа future<future<A>> в future<A>. Это аналог join из Control.Monad в Хаскеле.

Использование then может стать весьма нетривиальной вещью:
future<int> f(shared_ptr<stream> str)
{
shared_ptr<vector<char>> buf = ...;
return str->read(512, buf).then([](future<int> op)
{
return op.get() + 11;
});
}

future<void> g()
{
shared_ptr<stream> s = ...;
return f(s).then([s](future<int> op)
{
s->close();
});
}
Сразу так и не поймешь, что тут происходит, и это у нас ещё нет условных операторов и циклов. Для решения этой проблемы были предложены resumable функции: n3722. С ними этот кусок кода будет выглядеть так:
future<int> f(stream str) resumable
{
shared_ptr<vector<char>> buf = ...;
int count = await str.read(512, buf);
return count + 11;
}
future<void> g() resumable
{
stream s = ...;
int pls11 = await f(s);
s.close();
}
Ключевое слово resumable означает, что это определение функции, которая может быть прервана, а затем её вычисление может быть продолжено. Самое интересное здесь это await – это аналог стрелки влево (<-) в do нотации в Хаскеле. Заметьте, что и str.read и f возвращают значения типа future<int>, но после применения к ним await получается int, аналогично работает и стрелка влево в Хаскеле.

Как же всё это должно работать? Та статья, в которой это предлагается, даёт два возможных пути для реализации: первый из них основан на создании дополнительного стека под каждую resumable функцию, аналогично тому, как работают Fibers в Windows или boost::coroutine. Второй способ более эффективный, интересный и сложный для реализации. В этом случае каждая resumable функция будет как-бы разбиваться на составляющие в местах, в которых находится await. Так, что каждый await будет вызывать соответствующий then и передавать ему в качестве аргумента функцию, которая начинается после await. Это позволит использовать resumable функции не только с std::future, но и с любыми типами у которых есть методы then и get. Тогда можно будет использовать и другие монады на C++, хотя возможно проблемы могут возникнуть с теми монадами, где требуется копирование функции, как например, в монаде список. Сложно сказать будет ли вообще смысл в использовании других монад помимо std::future.
Что интересно, в статье предлагающей resumable функции ни разу не упоминается слово монада. Видимо её авторы не знают что это такое, так как связь между resumable функциями и монадами довольно очевидна.
монады
+30 13289
86stepik777 0,0
Похожие публикации

Чем хороши свободные монады (2)
Монады в Scala (14)
Еще Одно Руководство по Монадам (часть 4: Монада Maybe и монада списка) (6)
Еще Одно Руководство по Монадам (часть 2: функции >>= и return) (4)
Еще Одно Руководство по Монадам (часть 1: основы) (26)
Комментарии (26) отслеживать новые: в почте в трекере

+3 abby 6 декабря 2013 в 12:55#
Думаю, что не хватает ссылки FTL — The Functional Template Library
+1 Vitter 6 декабря 2013 в 13:12#
Приятно, что открытия, совершённые Хаскелем более 15 лет назад наконец-то внедряются в мейнстримовые языки программирования
+2 Dima_Sharihin 6 декабря 2013 в 14:20#↵↑
Честно говоря, после C#, Java и прочих современных управляемых языков программирования, смотреть на синтаксис C++ лично мне, все-таки страшно
+1 IRainman 7 декабря 2013 в 14:26#↵↑
Зато С++ всё так же работает быстрее, даже если сравнивать C++ с C++, т.е. код на C++11, благодаря семантике перемещения, будет работать быстрее чем код на C++03, а вообще, конечно же, ждём развития D до более менее адекватного состояния.
0 Gorthauer87 7 декабря 2013 в 16:00#↵↑
А в чем там принципиальная разница кроме управляемости, которая не везде в плюс работает?
0 potan 6 декабря 2013 в 15:51#
Не очень элегантно, но классы типов выражаются через аргументы поумолчанию.
Примерно так:
template <M> class monadVTBL {
template <v,x> M<x> bind(v, function<M<x> (M<x>)) = 0;
template <v> M<v> mreturn(v) = 0;
}

template<M,x,v> M<x> bind(v i, function<M<x> f(M<x>), monadVTBL<M> tbl = new monadVTBL<M>()) { return tbl.bind(i, f); }
template<M,v> M<v> mreturn(v i, monadVTBL<M> tbl = new monadVTBL<M>()) { return tbl.mreturn(i); }


А потом специализируем monadTBL для инстансов наших монад.
По большому счеты Haskell почти так же внутри делает. С небольшими оптимизациями.

PS на плюсах давно не писал, сейчас проверю компилируемость…
0 potan 6 декабря 2013 в 16:22#↵↑
Исправил код
template <template<typename _> class M, typename v, typename x> class monadVTBL {
M<x> bind(v, M<x>(*)(M<x>)) = 0;
M<v> mreturn(v) = 0;
};

template<template<typename _> class M, typename x, typename v> M<x> bind(v i, M<x>(*f)(M<x>), monadVTBL<M,v,x> tbl = new monadVTBL<M,v,x>()) {
return tbl.bind(i, f);
}
template<template<typename _> class M, typename v> M<v> mreturn(v i, monadVTBL<M,v,void> tbl = new monadVTBL<M,v,void>()) {
return tbl.mreturn(i);
}
0 roman_kashitsyn 6 декабря 2013 в 18:39#↵↑
Увлекаетесь скалой? Вы уверены, что это работает? У класса по умолчанию все члены закрытые. Типы у последних аргументов и их значений по-умолчанию в функциях не совпадают.

Как уже сказал автор статьи, гораздо удобнее и проще монады в с++ реализовать через перегрузку функций.
0 potan 6 декабря 2013 в 19:43#↵↑
Не то, что бы увлекаюсь — скорее использую . Но Вы правы — этот прием я от туда почерпнул.
Через перегрузку кое-что теряется. Не получится написать функцию, которая работает с абстрактной монадой, не зная ее конкретный тип. Например как в Haskell:
example :: (Monad m, Show x) => m x -> m String
example i o =
do
x <- i
return (show x)
0 roman_kashitsyn 6 декабря 2013 в 19:51#↵↑
template<typename M, typename T>
M<std::string> example(M<T> const& mx)
{
using monad::map;
return map(show, mx);
}


Что есть o (второй аргумент example) в вашей функции?
0 potan 6 декабря 2013 в 20:24#↵↑
o — опечатка.

А от куда example узнает имплементацию show для типа T?
0 roman_kashitsyn 6 декабря 2013 в 21:49#↵↑
Да, действительно. Первое, что приходит в голову — как-то совместить вывод типов с type erasure, но я не уверен, что это будет работать…
template< template<typename _> class M, typename T >
M<std::string> example(M<T> const& mx)
{
using monad::map;
const std::function<std::string(T)> f = show;
return map(f, mx);
}


Другой вариант — сделать show шаблонным function object и полагаться на частичные специализации (show<T> f; map(f, mx);), но это не очень в духе с++.
+5 roman_kashitsyn 6 декабря 2013 в 16:00#
В Хаскеле как известно есть монады, а в C++ их нет

Монады — это абстракция, они существуют в нашей голове. Средств для явного выражения абстракции монад в с++ нет. Но нужны ли они там? Мне кажется, нет. В C++ другие средства выражения тех же идей, зачем навязывать чуждые ему концепции?

Возьмём, к примеру, Monoid. В c++ для представления monoid достаточно иметь конструктор по умолчанию и оператор + (желательней, правда, +=). И всё, можно писать простой обобщённый код.
+4 Gunnar 6 декабря 2013 в 17:31 (комментарий был изменён)#
А можно для ржавых сиприплюсников объяснить что такое эта ваша монада и зачем она нужна? А то из статьи в вики я ничего не понял.

О функциональном программировании знаю только то, что оно существует. Не обессудьте.
0 Vitter 6 декабря 2013 в 18:08#↵↑
В чистом функциональном языке монады используются чтобы получать вычисления, зависимые от ранее вычисленного.
Или более обще — чтобы получать вычисления в контексте.

А зачем они нужны плюсам — ещё не до конца понял из статьи.
По идее может оказаться удобным инструментом для асинхронных вычислений.
+5 roman_kashitsyn 6 декабря 2013 в 18:22#↵↑
Монада это абстрактная структура (нечто вроде группы в абстрактной алгебре), которая относительно легко поддаётся линейной композиции. Как и в абстрактной алгебре, для определения требуется тип (в случае монады — параметризованный, т.е. шаблонный) и операции над ним. Для начала удобно представлять себе монаду в виде коробки с объектом типа t внутри (шаблонный тип с одним параметром — типом box).

Операции включают в себя:
1. Операция — единичка. Берёт простой объект типа t и помещает его в коробку box.
2. Операция применения (map). Если нам дают коробку box с объектом и функцию t2 f(t), операция map должна применить функцию к объекту внутри коробки и вернуть результат box.
3. Операция связывания (bind). Если нам дают коробку с объектом box и функцию box f(t), bind сможет вытащить объект из коробки и подставит его в f, получив новую коробку box.

На примере асинхронных вычислений:
1. Единичка берёт объект t и возвращает готовый фьючерс async.
2. Map берёт фьючерс async и функцию t2 f(t) и возвращает новый фьючерс async, объект в котором получается применением функции f к результату первого фьючерса при его готовности. Это по сути планирующийся then.
3. Bind берёт async и возвращает async, полученный ожиданием t из async и применением f к тому, что получилось.

Смысл монад в том, что можно написать довольно много обобщённого кода, которых будет работать для многих типов и операций, внешне не связанных, но обладающих похожей структурой. Примеры скрытых монад: std::vector, boost::optional, std::future. Идея в чём-то отражает намерения Степанова, при написании STL. Как итераторы приводят к многим универсальным алгоритмам, так монады приводят к многим управляющим структурам, поддающимся композиции.
+1 roman_kashitsyn 6 декабря 2013 в 18:49#↵↑
ну вот, хабр съел мои <t> и <t2>

Операции включают в себя:
1. Операция — единичка. Берёт простой объект типа t и помещает его в коробку box<t>.
2. Операция применения (map). Если нам дают коробку box<t> с объектом и функцию t2 f(t), операция map должна применить функцию к объекту внутри коробки и вернуть результат box<t2>.
3. Операция связывания (bind). Если нам дают коробку с объектом box<t> и функцию box<t2> f(t), bind сможет вытащить объект из коробки и подставит его в f, получив новую коробку box<t2>.
0 MuLLtiQ 7 декабря 2013 в 01:19#↵↑
Хм, а map через bind разве нельзя выразить?

Например, вот так на Scala
+1 Vitter 7 декабря 2013 в 01:39 (комментарий был изменён)#↵↑
Можно.
В моей последней статье на Хабре Löb и möb: странные петли в Хаскел я дал код как определён код функции fmap для функтора списков:
instance Functor [] where
fmap = map


Если у нас есть монада, тогда существует и функтор, который можно определить так:
instance Monad m => Functor m where
fmap = liftM

где
liftM :: Monad m => (a -> b) -> m a -> m b
liftM f m = m >>= return . f


Теперь если допустить, что у нас есть bind для списка, тогда можно пере-определить map

map = liftM
+1 Vitter 7 декабря 2013 в 02:01#↵↑
Вообще, если под map понимать fmap, то монаду теоретически можно определить 2 путями

— через return
и
1) — bind
2) — fmap; — join

То есть альтернативно bind определяется так:
(>>=) :: Monad m => m a -> (a -> m b) -> m b
m >>= g ≡ join ((fmap g) m)

0 roman_kashitsyn 7 декабря 2013 в 11:11#↵↑
Причём математическое определение, как правило, использует join, т.к. он проще и нагляднее. Я так понимаю, в Haskell используют bind напрямую, т.к. он важнее с точки зрения практического программирования и его можно реализовать эффективнее.
0 Vitter 8 декабря 2013 в 03:27#↵↑
Прежде всего потому, что Функтор не является (всё ещё) суперклассом Монаде, ведь кроме join надо определить ещё и fmap
0 roman_kashitsyn 8 декабря 2013 в 12:06#↵↑
Мне, кстати, в Haskell часто не хватает возможности сказать «любой инстанс класса X является также инстансом класса Y вот таким образом».
0 Vitter 8 декабря 2013 в 14:14#↵↑
Сейчас уже можно так написать, но это всё ещё плохо работает ((
С помощью следующих расширений:
-XUndecidableInstances
-XOverlappingInstances
и возможно,
-XIncoherentInstances
0 Vitter 6 декабря 2013 в 19:03 (комментарий был изменён)#
Я вот одного не понял, зачем для фьючерсов нужна фукнция mreturn.
По идее просто надо в определение bind добавить, что если значение не в асинхронном режиме, то не вытаскиваем его из этого режима, а используем как есть.
0 andy_p 6 декабря 2013 в 22:36#
У Лейбница было понятие — монада всех монад.
Здесь такое есть?

[dyvniy]

Use haskel in c++
http://stackoverflow.com/questions/3859340/calling-haskell-from-c-code?rq=1

Спойлер

I'm currently writing an app in C++ and found that some of its functionality would be better written in Haskell. I've seen instructions on calling Haskell from C code, but is it possible to do the same with C++?

EDIT: To clarify, what I'm looking for is a way to compile Haskell code into an external library that g++ can link with the object code from C++.

UPDATE: I've put up a working example below for anyone else interested (also so I won't forget).

c++ haskell linker ffi
shareimprove this question
edited Apr 23 '11 at 21:20

Don Stewart
109k26276407
asked Oct 4 '10 at 21:37

Tomer Vromen
974913
2
Have you tried it? That is to say, when you follow the C language directions from C++ code, does it work? Unless the guys preparing these instructions forgot extern "C", rely heavily on implicit conversion of void pointers, or named some variable class etc., I don't see why not. – asveikau Oct 4 '10 at 21:46

Because according to the instructions, I have to compile the C code with ghc. – Tomer Vromen Oct 4 '10 at 23:38
add a comment
4 Answers
activeoldestvotes
up vote
19
down vote
accepted
Edit: You should also see Tomer's answer below. My answer here describes the theory of what's going on, but I may have some of the details of execution incomplete, whereas his answer is a complete working example.

As sclv indicates, compiling should be no problem. The difficulty there is likely to be linking the C++ code, and here you will have a little bit of difficulty with getting all the needed runtime libraries linked in. The problem is that Haskell programs need to be linked with the Haskell runtime libraries, and C++ programs need to be linked with the C++ runtime libraries. In the Wiki page you reference, when they do

Код: Выделить всё

$ ghc -optc -O test.c A.o A_stub.o -o test

to compile the C program, that actually does two steps: It compiles the C program into an object file, and then links it together. Written out, that would be something like (probably not quite right, as I don't speak GHC):

Код: Выделить всё

$ ghc -c -optc-O test.c -o test.o
$ ghc test.o A.o A_stub.o -o test

GHC just acts like GCC (and, IIUC, functionally is GCC) when compiling the C program. When linking it, however, it is different from what happens if you call GCC directly, because it also magically includes the Haskell runtime libraries. G++ works the same way for C++ programs -- when it's used as a linker, it includes the C++ runtime libraries.

So, as I mentioned, you need to compile in a way that links with both runtime libraries. If you run G++ in verbose mode to compile and link a program, like so:

Код: Выделить всё

$ g++ test.cpp -o test -v

it will create a long list of output about what it's doing; at the end will be a line of output where it does the linking (with the collect2 subprogram) indicating what libraries it links to. You can compare that to the output for compiling a simple C program to see what's different for C++; on my system, it adds -lstdc++.

Thus, you should be able to compile and link your mixed Haskell/C++ program like so:

Код: Выделить всё

$ ghc -c -XForeignFunctionInterface -O A.hs     # compile Haskell object file.
$ g++ -c -O test.cpp                            # compile C++ object file.
$ ghc A.o A_stub.o test.o -lstdc++ -o test      # link

There, because you've specified -lstdc++, it will include the C++ runtime library (assuming -l is the right GHC syntax; you'll need to check), and because you've linked with ghc, it will include the Haskell runtime library. This should result in a working program.

Alternately, you should be able to do something similar to the -v output investigation with GHC, and figure out what Haskell runtime library (or libraries) it links to for Haskell support, and then add that library when linking your program with C++, just as you already do for pure C++ programs. (See Tomer's answer for details of that, since that's what he did.)

[dyvniy]

Опять про монады
http://habrahabr.ru/post/272115/

Спойлер

«Страшные» абстракции Haskell без математики и без кода (почти). Часть I tutorial
Функциональное программирование*, Программирование*, Haskell*
— Для чего нужны монады?
— Для того, чтобы отделить чистые вычисления от побочных эффектов.
(из сетевых дискуссий о языке Haskell)

Шерлок Холмс и доктор Ватсон летят на воздушном шаре. Попадают в густой туман и теряют ориентацию. Тут небольшой просвет — и они видят на земле человека.
— Уважаемый, не подскажете ли, где мы находимся?
— В корзине воздушного шара, сэр.
Тут их относит дальше и они опять ничего не видят.
— Это был математик, – говорит Холмс.
— Но почему?
— Его ответ совершенно точен, но при этом абсолютно бесполезен.
(анекдот)

Когда древние египтяне хотели написать, что они насчитали 5 рыб, они рисовали 5 фигурок рыб. Когда они хотели написать, что насчитали 70 людей, они рисовали 70 фигурок людей. Когда они хотели написать, что насчитали в стаде 300 овец, они… — ну, в общем, вы поняли. Так и мучились древние египтяне, пока самый умный и ленивый из них не увидел нечто общее во всех этих записях, и не отделил понятие количества того, что мы подсчитываем, от свойств того, что мы подсчитываем. А потом другой умный ленивый египтянин заменил множество палочек, которыми люди обозначали количество, на значительно меньшее количество знаков, короткой комбинацией которых можно было заменить огромное количество палочек.

То, что сделали эти умные ленивые египтяне, называется абстракцией. Они подметили нечто общее, что свойственно всем записям о количестве чего-либо, и отделили это общее от частных свойств подсчитываемых предметов. Если вы понимаете смысл этой абстракции, которую мы сегодня называем числами, и то, насколько она облегчила жизнь людям, то вам не составит труда понять и абстракции языка Haskell — все эти непонятные, на первый взгляд, функторы, моноиды, аппликативные функторы и монады. Несмотря на их пугающие названия, пришедшие к нам из математической теории категорий, понять их не сложнее, чем абстракцию под названием «числа». Для их понимания совершенно не требуется знать ни теорию категорий, ни даже математику в объёме средней школы (арифметики вполне достаточно). И объяснить их тоже можно, не прибегая к пугающим многих математическим понятиям. А смысл абстракций языка Haskell точно такой же, как и у чисел — они значительно облегчают программистам жизнь (и вы пока даже не представляете, насколько!).

Отличия функциональных и императивных программ
Познаём преимущества чистых функций
Вычисления и «что-то ещё»
Инкапсуляция «чего-то ещё»
Функтор — это не просто, а очень просто!
Аппликативные функторы — это тоже очень просто!
Вы будете смеяться, но монады также просты!
А давайте определим ещё пару монад
Применяем монады
Определяем монаду Writer и знакомимся с моноидами
Моноиды и законы функторов, аппликативных функторов и монад
Классы типов: десятки функций бесплатно!
Ввод-вывод: монада IO

Для того, чтобы понять (и принять) абстракции, людям, обычно, нужно взглянуть на них с нескольких сторон:

Во-первых, им нужно понять, что введение дополнительного уровня сложности в виде предлагаемой абстракции позволяет исключить гораздо больший уровень сложности, с которым они постоянно сталкиваются. Поэтому я опишу то огромное количество проблем, с которыми программисты перестанут сталкиваться, используя чистые функции (не беспокойтесь, ниже я объясню, что это такое) и описываемые абстракции.

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

И, в третьих, людям нужно понять не только то, как реализованы абстракции, но и как их применять в их повседневной жизни. Поэтому я опишу в статье и это. Тем более, это не просто, а очень просто — даже проще, чем понять, как эти абстракции реализованы (а вы сами увидите, что понять реализацию описываемых абстракций совсем несложно).

Впрочем, введение несколько затянулось, поэтому, пожалуй, начнём. Я лишь добавлю, что в статье будет очень мало кода, поэтому вам совершенно не обязательно быть знакомым с синтаксисом Haskell, чтобы понять и оценить всю красоту и мощь его абстракций.

Disclaimer
Отличия функциональных и императивных программ

Если взглянуть на программы, написанные на функциональных и императивных языках, с высоты птичьего полёта, то они ничем не отличаются. И те, и другие программы представляют из себя некоторый чёрный ящик, который принимает исходные данные и выдаёт на выходе другие данные, преобразованные из исходных. Отличия мы увидим, когда захотим заглянуть внутрь чёрных ящиков, чтобы понять, каким именно образом в них происходит преобразование данных.

Заглянув в императивный чёрный ящик, мы увидим, что входящие в него данные присваиваются переменным, а затем эти переменные многократно последовательно изменяются, пока мы не получим нужные нам данные, которые мы и выдаём из чёрного ящика.

В функциональном чёрном ящике эта превращение входящих данных в исходящие происходит путем применения к ним некоторой формулы, в которой конечный результат выражен в терминах зависимости от входящих данных. Помните из школьной программы, от чего зависит средняя скорость движения? Правильно: от пройденного пути и времени, за которое он пройден. Зная исходные данные (путь S и время t), а также формулу вычисления средней скорости (S / t), мы можем вычислить конечный результат — среднюю скорость движения. По такому же принципу зависимости конечного результата от исходных данных вычисляется и конечный результат работы программы, написанной в функциональном стиле. При этом, в отличие от императивного программирования, в процессе вычисления у нас не происходит никакого изменения переменных — ни локальных, ни глобальных.

Вообще-то, в предыдущем абзаце правильнее было бы употребить вместо слова формула слово функция. Я этого не сделал из-за того, что словом функция в императивных языках программирования чаще всего называют совсем не то, что подразумевается под этим термином в математике, физике и в функциональных языках программирования. В императивных языках функцией зачастую называют то, что правильнее называть процедурой — то есть именованной частью программы (подпрограммой), которая используется, чтобы избежать повторения неоднократно встречающихся кусков кода. Чуть позже вы поймете, чем функции в функциональных языках программирования (так называемые чистые функции, или pure functions) отличаются от того, что называют функциями в императивных языках программирования.

Примечание: Деление языков программирования на императивные и функциональные достаточно условно. Можно программировать в функциональном стиле на языках, которые считаются императивными, а в императивном стиле на языках, которые считаются функциональными (вот пример программы, вычисляющей факториал, в императивном стиле на Haskell и ее сравнение с такой же программой на C) — просто это будет неудобно. Поэтому давайте считать императивными языками те, которые поощряют программирование в императивном стиле, а функциональными языками — те, которые поощряют программирование в функциональном стиле.

Познаём преимущества чистых функций

Подавляющую часть времени программист на языке Haskell имеет дело с так называемыми чистыми функциями (все, конечно, зависит от программиста, но мы здесь говорим о том, как должно быть). Вообще-то, «чистыми» эти функции называют для того, чтобы их не путали с тем, что подразумевают под термином «функция» в императивном программировании. На самом деле это самые обычные функции в математическом понимании этого термина. Вот простейший пример такой функции, складывающей три числа:

addThreeNumbers x y z = x + y + z

Объяснение для тех, кто не знаком с синтаксисом Haskell
Обратите внимание на знак = (равно). В отличие от императивного программирования, он не означает операции присваивания. Знак равно означает, что то, что стоит слева от него — это то же самое, что и выражение справа от него. Совсем как в математике: 6 + 4 — это то же самое, что 10, поэтому мы пишем 6 + 4 = 10. В любом вычислении мы можем вместо десятки подставить выражение (6 + 4), и мы получим тот же самый результат, как если бы мы подставили десятку. То же самое и в Haskell: вместо addThreeNumbers x y z мы можем подставить выражение x + y + z, и получим тот же самый результат. Компилятор, кстати, так и делает — когда он встречаем имя функции, то подставляет вместо него выражение, определённое в её теле.

В чем же заключается «чистота» этой функции?

Результат функции зависит только лишь от ее аргументов. Сколько бы раз мы ни вызвали эту функцию с одними и теми же аргументами, она всегда вернет нам один и тот же результат, потому что функция не обращается к какому-либо внешнему состоянию. Она полностью изолирована от внешнего мира и при вычислениях учитывает только то, что мы явно передали ей в качестве ее аргументов. В отличие от такой науки, как история, результат математических вычислений не зависит от того, коммунисты ли у власти, демократы или Путин. Наша функция родом из математики — она зависит лишь от переданных ей аргументов и ни от чего больше.

Вы можете проверить это сами: сколько бы раз вы ни передавали этой функции в качестве аргументов значения 1, 2 и 4, вы всегда в качестве результата получите 7. Вы даже можете вместо «3» передавать "(2 + 1)", а вместо «4» — "(2 * 2)". Вариантов получить с этими аргументами другой результат попросту нет.

Функция addThreeNumbers называется чистой еще и потому, что она не только не зависит от внешнего состояния, но и не способна его изменять. Она даже не может изменять локальные переменные, переданные ей в качестве аргументов. Все, что она может (и должна) делать — это вычислить результат, исходя из значений переданных ей аргументов. Другими словами, эта функция не обладает побочными эффектами.

Что же нам это дает? Почему хаскеллисты так держатся за эту «чистоту» своих функций, презрительно кривясь, глядя на традиционные функции императивных языков программирования, построенных на мутации локальных и глобальных переменных?

Поскольку результат вычисления чистых функций никак не зависит от внешнего состояния и никак не изменяет внешнее состояние, мы можем вычислять такие функции параллельно, не заботясь о гонке данных, которые конкурируют друг с другом за общие ресурсы. Побочные эффекты — погибель параллельных вычислений, а раз наши чистые функции их не имеют, нам не о чем беспокоиться. Мы просто пишем чистые функции, не заботясь ни о порядке вычисления функций, ни о том, как нам распараллелить вычисления. Распараллеливание мы получаем «из коробки», просто потому, что пишем на Haskell.

Кроме того, поскольку вызывая чистую функцию несколько раз с одними и теми же аргументами, мы всегда гарантировано получим один и тот же результат, Haskell запоминает вычисленный однажды результат, и при повторном вызове функции с теми же аргументами не вычисляет его снова, а подставляет ранее вычисленный. Это называется мемоизацией (memoization). Он является весьма мощным инструмент оптимизации. Зачем считать снова, если мы знаем, что результат всегда будет одинаков?

Если суть императивного программирования — в мутации (изменении) переменных в строго определённой последовательности, то суть функционального программирования — в иммутабельности данных и в композиции функций.

Если у нас есть функция g :: a -> b (читается как «функция g, принимающая аргумент типа a и возвращающая значения типа b») и функция f :: b -> c, то мы можем путём их композиции получить функцию h :: a -> c. Подавая на вход функции g значение типа a, мы получим на выходе значение типа b — а значения именно такого типа принимает на вход функция f. Поэтому результат вычисления функции g мы можем сразу передать в функцию f, результатом которой будет значение типа c. Записывается это так:

h :: a -> c
h = f . g



Точка между функциями f и g — это оператор композиции, который имеет следующий тип:

(.) :: (b -> c) -> (a -> b) -> (a -> c)

Оператор композиции здесь взят в скобки потому, что именно так (в скобках) он используется в префиксном стиле, как обычная функция. Когда же мы используем его в инфиксном стиле — между двумя его аргументами — то он используется без скобок.

Мы видим, что оператор композиции в качестве первого аргумента принимает функцию b -> c (стрелка тоже обозначает тип — тип функции), что соответствует нашей функции f. Вторым аргументом он тоже принимает функцию — но уже с типом a -> b, что соответствует нашей функции g. И возвращает нам оператор композиции новую функцию — с типом a -> c, что соответствует нашей функции h :: a -> c. Поскольку функциональная стрелка имеет правую ассоциативность, последние скобки мы можем опустить:

(.) :: (b -> c) -> (a -> b) -> a -> c

Теперь мы видим, что оператору композиции нужно передать две функции — с типами b -> c и a -> b, а также аргумент типа a, который передастся на вход второй функции, и на выходе мы получим значение типа c, которое возвратит нам первая функция.
Почему оператор композиции обозначается точкой
Композиция функций f . g означает то же самое, что и f (g x) — т.е. функция f, применённая к результату применения функции g к аргументу x.

Постойте! А куда потерялся аргумент типа a в определении функции h = f . g? Две функции в качестве аргументов оператора композиции вижу, а значение, передаваемое на вход в функцию g не вижу!
Почему именно композиция функций является сутью функциональных языков программирования? Да потому, что любая программа, написанная на функциональном языке, является ничем иным, как композицией функций! Функции — это кирпичики нашей программы. Композируя их, мы получаем другие функции, которые, в свою, композируем для получения новых функций — и т.д. Данные перетекают из одной функции в другую, трансформируясь, и единственное условие для композиции функций — чтобы данные, возвращаемые одной функцией, имели тот же самый тип, который принимает следующая функция.

Поскольку функции в Haskell у нас чистые, и зависят только от явно переданных им аргументов, то мы легко можем «вытащить» из цепочки композиции функций какой-то «кирпичик», чтобы отрефакторить или даже полностью заменить его. Всё, о чём нам надо позаботиться — это чтобы наша новая функция-кирпичик принимала на входе и выдавала на выходе значения того же типа, что и старая функция-кирпичик. И всё! Чистые функции никак не зависят от внешнего состояния, поэтому тестировать функции мы можем без оглядки на него. Вместо тестирования программы целиком мы тестируем отдельные функции. Ситуация, описанная в этом весьма жизненном рассказе, в нашем случае становится просто невозможной:

Маркетолог спрашивает программиста:
— В чём сложность поддержки большого проекта?
— Ну, представь, что ты писатель, и поддерживаешь проект «Война и мир», — отвечает программист. — У тебя ТЗ — написать главу о том, как Наташа Ростова гуляла под дождём по парку. Ты пишешь «шёл дождь», сохраняешься — и тебе вылетает сообщение об ошибке: «Наташа Ростова умерла, продолжение невозможно». Как умерла, почему умерла? Начинаешь разбираться. Выясняется, что у Пьера Безухова скользкие туфли, он упал, его пистолет ударился о землю, а пуля от столба срикошетила в Наташу. Что делать? Зарядить пистолет холостыми? Поменять туфли? Решили убрать столб. Убрали, сохраняемся и получаем сообщение: «Поручик Ржевский умер». Опять садишься, разбираешься и выясняется, что в следующей главе он облокачивается на столб, которого уже нет…

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

Другими словами, создатели языка Haskell придумали себе (и нам) такой полностью изолированный от внешнего состояния мирок, эдакого сферического коня в вакууме, в котором все функции чистые, нет никакого состояния, все оптимизировано до невозможности и все само собой распараллеливается без всяких усилий с нашей стороны. Не язык, а мечта! Осталось только понять, что делать с «сущими мелочами», которые в своей научной работе, посвященной концепции монад, перечислил Eugenio Moggi:

Как в этом самом сферическом коне в вакууме получать исходные данные для наших программ, которые приходят как раз из внешнего мира, от которого мы изолировались? Можно, конечно, использовать в качестве аргумента нашей чистой функции результат пользовательского ввода (например, функцию getChar, принимающую ввод символа с клавиатуры), но, во-первых, таким образом мы впустим в наш уютный чистый мирок «грязную» функцию, которая нам все там сломает, а, во-вторых, у такой функции аргумент всегда будет один и тот же (функция getChar), а вот вычисляемое значение всегда будет разным, потому что пользователь (вот засада!) будет все время нажимать разные клавиши.

Как выдавать результат в изолированный нами же от нашего уютного чистофункционального мирка внешний мир результат работы программы? Ведь функция в математическом смысле этого слова всегда должна возвращать результат, а функции, отправляющие какие-то данные во внешний мир, ничего нам не возвращают, а значит, и не являются функциями!

Что делать с так называемыми частично определёнными функциями — то есть с функциями, которые определены не для всех аргументов? Например, всем известная функция деления не определена для деления на ноль. Такие функции тоже не являются полноценными функциями в математическом смысле этого термина. Можно, конечно, для таких аргументов бросать исключение, но...

… но что нам делать с исключениями? Исключения — это совсем не тот результат, который мы ожидаем от чистых функций!

А что делать с недетерминированными вычислениями? То есть с такими, где правильный результат вычислений не один, а их много. Например, мы хотим получить перевод какого-то слова, а программа выдает нам сразу несколько его значений, каждое из которых является правильным результатом. Чистая функция всегда должна выдавать только один результат.

А что делать с продолжениями? Продолжения — это когда мы производим какие-то вычисления, а затем, не дождавшись их окончания, сохраняем текущее состояние и переключаемся на выполнение какой-то другой задачи, чтобы после ее выполнения вернуться к незавершенным вычислениям и продолжить с того места, где мы остановились. О каком состоянии мы ведем речь в нашем чистофункциональном мирке, где никакого состояния нет и быть не может?

И что, наконец, нам делать, когда нам нужно не только как-то считать внешнее состояние, но и как-то изменить его?

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

Вычисления и «что-то ещё»

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

Иногда у нас есть функции, которые определены не для всех аргументов. Когда мы передаём этой функции аргументы, на которых функция определена, мы хотим, чтобы она вычислила результат. Но при передаче её аргументов, на которых она не определена, мы хотим, чтобы функция возвратила нам что-то ещё (исключение, сообщение об ошибке или аналог императивного null).

Иногда функции могут выдавать нам не один результат, а что-то ещё (например, целый список результатов, или вообще никакого результата (пустой список результатов)).

Иногда, для вычисления значения функции, мы хотим получать не только аргументы, но и что-то ещё (например, какие-то данные из внешнего окружения, или какие-то настройки из конфигурационного файла).

Иногда мы хотим не только получить результат вычисления для передачи следующей функции, но и применить его в качестве аргумента к чему-то ещё (получив некоторое состояние, к которому можно затем вернуться, чтобы продолжить вычисления, что является смыслом продолжений (continuations).

Иногда мы хотим не только произвести вычисления, но и сделать что-то ещё (например, записать что-то в лог).

Иногда, композируя функции, мы хотим передать следующей функции не только результат нашего вычисления, но и что-то ещё (например, некоторое состояние, которое мы сначала считали откуда-то, а затем как-то контролируемо изменили).

Заметили общий паттерн? На псевдокоде его можно записать примерно так:

функция (аргументы и/или иногда что-то ещё)
{
// сделай чистые вычисления
и/или
// сделай что-то ещё
return (результат чистых вычислений и/или что-то ещё)
}


Можно, конечно, передавать это «что-то ещё» в качестве дополнительного аргумента в наши функции (такой подход применяется в императивном программировании, и называется «выделением состояния» (threading state)), но смешивать чистые вычисления с «чем-то ещё» в одну кучу — не самая лучшая идея. Кроме того, это не позволит нам получить единое решение для всех описанных ситуаций.

Давайте вспомним древних египтян, о которых шла речь в начале, и которые изобрели числа. Вместо рисования множества фигурок овец они отделили вычисление от его контекста. Выражаясь современным языком, они инкапсулировали вычисления и их контекст. И если до них понятие вычисления количества было неразрывно связано с тем, что именно мы считаем, то их инновация разделила это на два параллельных «потока исполнения» — на поток, связанный непосредственно с вычислениями, и на поток, в котором хранится или обрабатывается что-то ещё — а именно, контекст вычисления (потому что в ходе вычисления контекст может не только храниться, но и изменяться, если мы, например, подсчитываем, сколько шашлыков получится из овец, находящихся в стаде).



Когда мы хотим в Haskell’е выразить «что-то ещё», и при этом получить максимально обобщённое решение, это «что-то ещё» мы выражаем в виде дополнительного типа. Но не простого типа, а типа-функции, который принимает в качестве аргумента другие типы. Звучит сложно и непонятно? Не волнуйтесь, это очень просто, и через несколько минут вы сами убедитесь в этом.

Инкапсуляция «чего-то ещё»

11 декабря 1998 г. для исследования Марса был запущен космический аппарат Mars Climate Orbiter. После того, как аппарат достиг Марса, он был потерян. После расследования выяснилось, что в управляющей программе одни дистанции считались в дюймах, а другие — в метрах. И в одном, и в другом случае эти значения были представлены типом Double. В результате функции, считающей в дюймах, были переданы аргументы, выраженные в метрах, что закономерно привело к ошибке в расчётах.

Если мы хотим избежать таких ошибок, то нам нужно, чтобы значения, выраженные в метрах, отличались от значений, выраженных в дюймах, и чтобы при попытке передать в функцию значение, выраженное не в тех единицах измерения, компилятор сообщал нам об ошибке. В Хаскелле это сделать очень легко. Давайте объявим два новых типа:

data DistanceInMeters = Meter Double

data DistanceInInches = Inch Double


DistanceInMeters и DistanceInInches называются конструкторами типов, а Meter и Inch — конструкторами данных (конструкторы типов и конструкторы данных обитают в разных областях видимости, поэтому их можно было бы сделать и одинаковыми).

Присмотритесь к этим объявлениям типов. Не кажется ли вам, что конструкторы данных ведут себя как функции, принимая в качестве аргумента значение типа Double и возвращая в результате вычисления значение типа DistanceInMeters или DistanceInInches? Так и есть — конструкторы данных у нас тоже являются функциями! И если раньше мы могли случайно передать в функцию, принимающую Double, любое значение, имеющее тип Double, то теперь в этой функции мы можем указать, что её аргумент должен содержать не только значение типа Double, но и что-то ещё, а именно — соответствующую «обёртку» Meter или Inch.

Однако данном случае у нас получилось не самое обобщённое решение. В качестве аргумента наши функции-конструкторы_данных Meter и Inch могут принимать только значения типа Double. Это продиктовано логикой данной конкретной задачи, однако для решения нашей основной задачи — отделения чистых вычислений от «чего-то ещё» — нам нужно, чтобы наши «обёртки», выражающие это «что-то ещё», могли принимать в качестве своих аргументов любой тип. И эта задача тоже очень легко решается в Haskell. Посмотрим на один из встроенных типов Haskell:

data Maybe a = Nothing | Just a

Объяснение для тех, кто не разобрался, что тут написано
Смотрите, у нас есть обёртка Maybe, которая может принимать значения любого типа. Эта обёртка может либо содержать какое-то значение (если использован конструктор данных Just), либо не содержать ничего (если использован конструктор данных Nothing). Для того, чтобы узнать, есть ли какие-то данные внутри обёртки Maybe, нам нужно лишь проинспектировать обёртку. Это как с коробком спичек: чтобы узнать, пустой коробок или нет, нам не обязательно его открывать — мы лишь подносим к уху коробок и встряхиваем его.

Тип Maybe используется в Haskell для решения одной из наших задач — что делать с чистыми функциями, которые определены не для всех своих аргументов. Например, у нас есть функция lookup, которой можем передать ключ и ассоциативный список пар (ключ, значение), чтобы она нашла нам значение, ассоциированное с этим ключом. Но ведь эта функция может и не найти пары с тем ключом, который мы её передали. В этом случае она возвратит нам Nothing, а если найдёт — то возвратит нам значение, обёрнутое в Just. Т.е. когда мы передаём функции значения, на которых она определена, мы получим результат вычислений (в обёртке Just), а когда передаём значения, на которых она не определена — мы получаем «что-то ещё» (Nothing).

Но что, если мы хотим получить не просто Nothing, но и сообщение о том, почему функция нам возвратила «что-то ещё» вместо результата вычислений? Давайте более чётко определим задачу: мы хотим, чтобы если вычисления были удачными, нам был возвращён их результат, а если неудачными — то сообщение об ошибке, причём результат вычислений и сообщение об ошибке могут быть разных типов. ОК, давайте так и запишем:

data Either a b = Left a | Right b

Мы видим, что конструктор типа Either принимает 2 переменных типа — a и b (которые могут быть разными типами, но могут быть и одного типа — как нам захочется). Если результат вычислений был удачен, мы получаем их в обёртке Right (результат вычислений будет иметь тип b), а если вычисления закончились неудачей, то мы получаем сообщение об ошибке типа a в обёртке конструктора данных Left.

Ну а что с работой с внешним окружением? Что, если значение нашего вычисления зависит от некоторого внешнего окружения, которое мы должны прочитать и передать в качестве аргумента функции, вычисляющей нужное нам значение? Как сформулировано, так и запишем:

data Reader e a = Reader (e -> a)

Окружение (Environment), от которого зависит наш результат вычислений, обозначается переменной типа e (напомню, что вместо переменной типа можно подставить любой нужный нам тип), а тип результата вычисления обозначен переменной типа a. При этом само вычисление имеет тип e -> a, т.е. это функция из окружения в нужное нам значение.

То же самое и с недетерминированными вычислениями, которые могут нам вернуть единственный результат или что-то ещё (ноль результатов или множество результатов): мы оборачиваем их в дополнительный тип, обозначающий это самое «что-то ещё». И этот тип вам наверняка знаком — это тип списка [a] (который можно написать и так: [] a, где [] обозначает это «что-то ещё», а переменная типа a — это тип наших чистых вычислений).

Аналогично мы поступаем с любым «чем-то ещё» — будь то состояние, которое нам нужно изменить параллельно с исполнением наших чистых вычислений, или исключения, которые могут возникать в процессе исполнения нашей программы. Мы инкапсулируем это «что-то ещё» в типе, в который мы «оборачиваем» наши чистые вычисления, и разделяем обработку «чего-то ещё» и чистые вычисления на два параллельных потока, с каждым из которых мы работаем явно.

Давайте резюмируем и обобщим то, что мы узнали на этот момент:

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

Однако мы встретились с рядом других проблем, которые, как мы выяснили, можно привести к единому паттерну под кодовым названием «что-то ещё». Наши функции могут возвращать, помимо результата вычислений, «что-то ещё», или мы можем передавать в них кроме обычных аргументов «что-то ещё».

Нам нужно инкапсулировать это «что-то ещё», отделив их от чистых вычислений. Чистые вычисления и вычисления с этим «что-то ещё» должны выполняться параллельно.

Мы инкапсулируем это «что-то ещё» в «обёрточном» типе, в который мы «оборачиваем» наши чистые вычисления.

На уровне типов эту инкапсуляцию мы можем представить так:

a -> m b

где m — это некоторый «обёрточный тип», в который обёрнут результат чистых вычислений b.

ОК, концептуально мы поставленные проблемы решили. Но нам стоит решить ещё несколько задач, чтобы из-за нашего решения нам не пришлось писать больше кода:

У нас есть множество функций с типом a -> b, т.е. работающие с обычными значениями. Но теперь у нас появились значения типа m a. Нам нужно либо вручную писать новые функции m a -> m b, либо придумать универсальный механизм, позволяющий «впрыскивать» наши функции типа a -> b внутрь обёрток m, чтобы вычисление a -> b произошло внутри обёртки, и мы получили значение типа m b.

У нас функциональный язык, а это значит, что функции у нас являются first class citizens. Т.е. с функциями мы можем делать то же самое, что и с данными — передавать их в качестве аргументов, возвращать их в качестве результатов других функций и т.д. Это значит, что мы можем, в том числе, оборачивать функции в наши «обёрточные» типы m. И если у нас есть функция f, применённая к аргументу a, то мы должны либо вручную определить, как каждую обёрнутую функцию m f можно применить к обёрнутому значению m a, либо придумать универсальный способ «выносить обёртку за скобки»:

m f `применённое к` m a => m (f `применённое к` a).

И, наконец, нам нужно придумать, как композировать наши новые функции, ведь именно композиция, как вы помните, является сутью функционального программирования. Если у нас есть функции f :: b -> c и g :: a -> b, то мы можем составить из них композицию функций f . g, поскольку возвращаемое значение функции g совпадает по типу со значением, которое принимает функция f. А как нам композировать функции f :: b -> m c и g :: a -> m b? Ведь m b и b — это разные типы, несмотря на то, что тип b «сидит» внутри обёртки m.

Причём нам недостаточно просто взять и «вытащить» тип b из обёртки m, чтобы передать его в качестве значения следующей функции. Ведь параллельно с чистыми вычислениями в нашей «обёртке» происходят вычисления нашего «чего-то ещё», и результат этого вычисления нам тоже нужно передать в следующую функцию. В общем, нам нужно придумать, как мы можем композировать функции a -> m b и b -> m c, чтобы мы смогли из них получить новую функцию a -> m c, и чтобы при этой композиции у нас не потерялись ни чистые вычисления, ни вычисления «чего-то ещё». Причём наше решение, как вы, наверное, уже догадались, тоже должно быть универсальным.


Функтор — это не просто, а очень просто!

Итак, у нас есть три задачи:

Придумать, как мы можем применять уже имеющиеся у нас функции, работающие с обычными значениями, к обёрнутым значениям.

Придумать, как мы можем применять обёрнутые функции, работающие с обычными значениями, к обёрнутым значениям.

Придумать, как мы можем композировать функции, принимающие обычные значения и возвращающие обёрнутые значения — так, чтобы в следующую функцию передавался как результат чистых вычислений, содержащийся внутри обёртки, так и результат вычисления «чего-то ещё», содержащийся в самой обёртке.

В принципе, если бы функциональщики не были ленивыми людьми, они бы были императивщиками просто написали кучу новых функций для работы с обёрнутыми данными. Для определения аналога функции isChar :: a -> Bool, проверяющей, является ли переданное нами значение значением типа Char, нам нужно написать столько уравнений, сколько конструкторов данных имеется в нашем обёрточном типе. Например, в обёрточном типе Maybe a есть 2 конструктора данных — Just и Nothing:

maybeIsChar :: Maybe Char -> Maybe Char -> Maybe Bool
maybeIsChar (Just x) = Just (isChar x)
maybeIsChar Nothing = Nothing

И так мы можем, не заморачиваясь (хотя это как посмотреть), определить аналог каждой чистой функции для работы с обёрнутыми данными. Причём нам нужно будет написать соответствующий аналог не только для каждой функции, но и для каждой обёртки!

Но можно сделать и по-другому. Можно определить новую функцию, которая принимает в качестве первого аргумента уже имеющуюся у нас чистую функцию, и применяет её к значению, содержащемуся внутри обёртки, возвращая нам новое значение, обёрнутое в ту же самую обёртку. Назовём эту функцию fmap:

fmap :: (a -> b) -> m a -> m b

Теперь, вместо того, чтобы определять сотни аналогов наших обычных функций для каждого из обёрточных типов, мы можем определить для каждого из обёрточных типов всего одну функцию fmap. Давайте определим функцию fmap для обёрточного типа Maybe a:

fmap f (Just x) = Just (f x)
fmap _ Nothing = Nothing

А что это за знак нижнего подчёркивания на месте первого аргумента функции fmap во втором уравнении?
Теперь мы можем применять к обёрнутым значениям типа Maybe a любые функции типа a -> b. Согласитесь, что определением одной лишь функции fmap мы избавились от массы дополнительной работы. Эту же фразу можно произнести и по-другому: сделав наш обёрточный тип Maybe a функтором, мы избавились от массы дополнительной работы.

Да-да! Чтобы сделать обёрточный тип функтором, нужно всего лишь определить для него функцию fmap, что позволит нам «впрыскивать» функции, работающие с обычными значениями, внутрь обёртки. Я же говорил, что функторы — это очень просто! И полезно, т.к. позволяет нам использовать ранее определённые чистые функции не только с обычными, но и с обёрнутыми значениями.

Аппликативные функторы — это тоже очень просто!

Мы придумали, как нам применять функции, работающие с необёрнутыми значениями, к обёрнутым значениям. Но что, если у нас обёрнута и сама функция? Как нам её применить к обёрнутому значению?

Думаю, вы уже догадались. Нам нужно объявить функцию, которая принимает в качестве первого аргумента обёрнутую функцию, а в качестве второго аргумента — обёрнутое значение, а затем определить эту функцию для каждого обёрточного типа, для которого нам нужны такие операции. Назовём эту функцию <*> (читается apply; то, что название функции начинается не с маленькой буквы, а со специального символа, говорит нам о том, что мы должны её использовать в инфиксном виде; если мы хотим её использовать в префиксном виде, как обычную функцию, нам нужно будет взять её в круглые скобки):

(<*>) :: m (a -> b) -> m a -> m b

Давайте определим объявленную функцию для типа Maybe a. При этом будем помнить, что у этого типа 2 конструктора, а значит, и обёрнутая в этот тип функция, и обёрнутое значение, могут быть как (Just функция или значение), так и Nothing:

(Just f) <*> Nothing = Nothing
Nothing <*> _ = Nothing
(Just f) <*> (Just x) = Just (f x)

Всё, теперь мы можем применять любые обёрнутые функции, которые изначально могли работать лишь с обычными значениями, к обёрнутым значениям — при условии, что наша обёртка является типом Maybe. Если же мы хотим иметь возможность делать то же самое и с другими нашими обёртками, то всё, что нам нужно — это определить для каждой из них функцию (<*>). Другими словами, нам нужно сделать эти обёртки аппликативными функторами, потому что аппликативным функтором называется обёрточный тип, для которого определены функции (<*>) и pure.

Что же делает функция pure? О, это ещё проще, чем функтор или аппликативный функтор! Функция pure принимает обычное значение и делает из него обёрнутое значение. Вот её тип:

pure :: a -> m a

Давайте определим функцию pure для обёрточного типа Maybe, сделав из него настоящий аппликативный функтор:

pure x = Just x

Всё очень сложно, правда? (табличка с надписью «Сарказм!»)

Кстати, сделав обёрточный тип аппликативным функтором, мы можем применять функции, принимающие любое количество обычных аргументов, к соответствующему количеству обёрнутых аргументов (функтор позволяет нам применять к обёрнутым значениям только обычные функции одного аргумента). Вот как, например, мы можем сложить Just 2 и Just 3:

pure (+) <*> Just 2 <*> Just 3
> Just 5

Не до конца ясен код?
Не нравится этот синтаксис? Попробуйте вот это!

Вы будете смеяться, но монады также просты!

Итак, мы придумали, как нам применять обычные функции (одного аргумента) к обёрнутым значениям. Для этого нужно определить для обёрточного типа функцию fmap. И с тех пор, как мы реализовали эту функцию для нашего обёрточного типа, он имеет право гордо именоваться функтором, ибо чтобы стать функтором, ничего больше не нужно.

Также мы придумали, как можно применять обёрнутые функции к обёрнутым значениям. Для этого нужно определить для обёрточного типа две функции — pure и <*> — и это же позволило нам применять к обёрнутым значениям обычные функции, принимающие любое количество аргументов. И как только мы определили для обёрточного типа эти функции, он сразу же заслужил право именоваться аппликативным функтором. Кстати, для того, чтобы сделать обёрточный тип аппликативным функтором, нужно сначала его сделать обычным функтором (и схитрить не получится — компилятор за этим проследит). Этому есть логичное (и, по обыкновению, простое) объяснение, которое я оставлю вам для самостоятельного изучения, ибо статья и так раздулась очень сильно.

Нам осталось понять, как мы можем составлять композицию из двух функций a -> m b и b -> m c таким образом, чтобы из первой функции во вторую передавались и результаты наших чистых вычислений, и результаты вычисления «чего-то ещё», содержащегося в нашей обёртке. Как вы уже, наверное, догадались, для этого нам также потребуется определить одну или две функции для наших обёрточных типов. А самые догадливые уже поняли, что обёрточные типы, для которых будут определены эти функции, будут называться монадами.

Первая из этих функций — функция return. Это не императивный return, который определяет точку выхода из функции. Хаскельная функция return берёт обычное значение, и делает из него обёрнутое значение:

return :: a -> m a

Похоже на функцию pure из главы, где мы превращали обёрточный тип в аппликативные функторы? Так оно и есть, эти функции делают одну и ту же работу. А поскольку есть правило, согласно которому любой обёрточный тип, который мы хотим сделать монадой, сначала должен стать аппликативным функтором (а до этого — просто функтором), а значит, для данного обёрточного типа мы уже определили функцию pure, то функцию return мы можем определить очень просто:

return = pure

Вторая функция, которую нам нужно определить для обёрточного типа, чтобы сделать его монадой, называется (>>=) (читается bind). Она имеет следующий тип:

(>>=) :: m b -> (b -> m c) -> m c

Хм… Что-то она не очень напоминает композицию функций. Всё верно: функция (>>=) принимает обёрнутое значение и функцию с типом a -> m b, и нам нужно определить, каким образом нам передать в эту функцию как результат чистых вычислений, обёрнутый в тип-обёртку, так и результат вычислений «чего-то ещё» (или результат хранения этого «чего-то ещё», если никаких вычислений с ним не производилось), содержащийся в самой обёртке. Т.е. в данном случае мы не показываем функцию a -> m b, в результате которой мы получили значение типа m b, подразумеваем, что оно уже у нас откуда-то есть. Впрочем, функцию композиции мы определим чуть позже, используя для этого функцию (>>=). А пока займёмся ею.

Давайте реализуем (>>=) для обёрточного типа Maybe. Поскольку у него 2 конструктора данных, нам потребуется для этого 2 уравнения. Давайте обзовём нашу функцию, имеющую тип b -> m c буковкой k, от названия «стрелка Клейсли» (все функции, принимающие обычное значение, и возвращающие обёрнутое значение, называются «стрелками Клейсли», и реализованная нами ранее функция return также является «стрелкой Клейсли»):

— какой бы функции мы ни передали Nothing, результатом будет Nothing
Nothing >>= _ = Nothing
— а вот если внутри обёртки есть значение, то мы его "вынимаем" и передаём функции k
(Just x) >>= k = k x

Вот и всё. Теперь наш обёрточный тип Maybe — монада! Всё, что нужно было для этого сделать — определить для него функции return и (>>=).

Что же нам это дало (помимо тех преимуществ, которые предоставляют нам чистыми функциями, и которые мы сохранили)? Представьте себе целый конвейер из стрелок Клейсли, через который мы хотим пропустить наше значение. Каждая из этих стрелок Клейсли может возвратить нам либо значение, упакованное в обёртку Maybe при помощи конструктора данных Just, либо Nothing. Очевидно, что если какая-то стрелка Клейсли из этой цепочки выдала Nothing, нет смысла передавать это значение по конвейеру дальше. Так что же нам делать? После работы каждой стрелки Клейсли проверять при помощи if then else, не вернула ли предыдущая функция Nothing?

Императивщики так и делают, строя уродливые конструкции из множества вложенных if then else. Но мы определили функцию (>>=), которая решает эту задачу без подобной жести. Посмотрите сами: если где-то у нас появился Nothing, наш оператор (>>=) просто «протянет» его до конца конвейера, не передавая ни в какую функцию. Значит, мы можем писать наши цепочки вычислений не беспокоясь о проверке на null Nothing. Монады не только позволяют нам сохранить преимущества работы с чистыми функциями, но и позволяют нам писать гораздо меньше кода и сам код получается гораздо более читабельным.

А давайте определим ещё пару монад

Давайте, может, определим ещё одну монаду? Возьмём обёрточный тип Either a b, который позволяет нам более наглядно работать с ошибками и исключениями, чем тип Maybe. Давайте вспомним определение этого типа:

data Either a b = Left a | Right b

Этот тип имеет 2 конструктора, один из которых — Left — принимает значение типа a — это тот тип, который мы будем использовать для сообщения об ошибках, которые в данной обёртке являются тем самым «чем-то ещё», а второй — Right — принимает значение типа b — это тип наших «основных» вычислений. Если «основные» вычисления у нас происходят без эксцессов, то у нас по цепочке композиции стрелок Клейсли проходят значения вычислений, обёрнутые при помощи конструктора данных Right. А как только происходит ошибка — получаем в качестве результата сообщение о ней, обёрнутое при помощи конструктора данных Left.

Определим для начала функцию return:

return x = Right x

Здесь всё очевидно. Поскольку мы передаём функции return не сообщение об ошибке, а какое-то значение типа b, то мы применяем к этому значению функцию-конструктор_данных Right и получаем значение типа Either a b.

Теперь определим оператор (>>=). Логика здесь такая же, как и с монадой Maybe: если хотя бы одна из стрелок Клейсли, которой по цепочке передаётся значение типа Either a b, выдало сообщение об ошибке, обёрнутое при помощи функции-конструктора_данных Left — то и результатом всей цепочки вычислений должно быть это сообщение об ошибке. Если же все вычисления прошли успешно (т.е. каждая из стрелок Клейсли возвратила результат вычислений, обёрнутый при помощи функции-конструктора_данных Right), то каждая следующая функция должна применяться к этому результату:

(Left x) >>= _ = Left x
(Right x) >>= k = k x

Монады Maybe и Either похожи. Обе имеют 2 конструктора данных, один из которых обозначает неудачу в вычислениях (и, следовательно, его нужно не передавать в следующую функцию, а «протащить» до конца композиции стрелок Клейсли). Второй же конструктор данных в обеих монадах означает удачно завершившиеся вычисления, и значение этих вычислений передаётся в следующую стрелку Клейсли.

Давайте теперь реализуем монаду, которая отличается от реализованных ранее монад — монаду списка. Стрелка Клейсли для монады списка имеет тип a -> [b]. Первым аргументом оператора (>>=) является обёрнутое значение типа m a — в данном случае, это [a] (список значений типа a). При этом список у нас может быть пустым, а может содержать одно или более значений типа a.

Что же, в данном случае, означает применение стрелки Клейсли к списку значений? А это означает, что мы должны её применить к каждому значению списка. В случае с пустым списком всё понятно — там не к чему применять стрелку Клейсли, и в результате мы получим пустой же список. К каждому значению непустого списка мы можем применить стрелку Клейсли, используя функцию fmap (раз мы делаем из списка монаду, то это значит, что список является и функтором — помните?). Однако давайте вспомним тип функции fmap, заменив для удобства восприятия абстрактный обёрточный тип m на наш конкретный обёрточный тип списка:

fmap :: (a -> b) -> [a] -> [b]

А теперь заменим тип функции, передаваемой в fmap, на тип нашей стрелки Клейсли:

fmap :: (a -> [b]) -> [a] -> [[b]]

Мы видим, что в результате передачи стрелки Клейсли в fmap у нас получится значение не типа m b, а типа m m b, т.е. у нас обёртка будет двойной. Это не соответствует типу оператора (>>=), поэтому одну из обёрток мы должны «снять». Для этого у нас есть функция concat, принимающая список списков, конкатенирующая внутренние списки, и возвращающая обычный список значений. Теперь мы готовы определить оператор (>>=) для монады списка:

[] >>= _ = []
xs >>= k = (concat . fmap k) xs

Вы видите, что логика определения оператора (>>=) во всех случаях одна и та же. В каждом обёрнутом значении у нас есть результат вычислений и «что-то ещё», и мы думаем, что нам нужно сделать с вычислениями и с этим «чем-то ещё» при передаче в другую функцию. «Что-то ещё» может быть маркером удачных или неудачных вычислений, может быть маркером удачных вычислений или сообщением об ошибке, может быть маркером того, что вычисления у нас могут возвратить от нуля до бесконечности результатов. «Что-то ещё» может быть записью в лог, состоянием, которое мы читаем и передаём в качестве аргумента для наших «основных» вычислений. Или состоянием, которое мы читаем, изменяем и передаём в другую функцию, где оно снова изменяется — параллельно с нашими «основными» вычислениями.

Согласитесь, что в монадах ничего сложного нет (как и в функторах, и в аппликативных функторах). Монада — это просто обёрточный тип, для которого определены две функции — return и (>>=).

Впрочем, определения (>>=) для обёрток, работающих с состоянием, несколько сложнее. Я не привожу их здесь потому, что их реализация требует более высокого уровня знакомства с синтаксисом Haskell, нежели тот, который был введён в данной статье. Но я хочу вас успокоить. Во-первых, даже весьма продвинутые программисты на Haskell обычно не пишут свои монады, а используют встроенные в язык, которых хватает на все случаи жизни. Во-вторых, использовать монады (в том числе и работающие с состоянием) гораздо проще, чем их определять, что вы увидите в следующей главе.

Для понимания монад вам нужно просто осознать простой принцип: у нас есть «основные» вычисления и вычисления «чего-то ещё», которые происходят параллельно. А как именно происходят эти вычисления в «конвейере» «стрелок Клейсли», определяет оператор (>>=). Поэтому, хотя вам вряд ли когда-то придётся самим определять оператор (>>=), весьма полезно разобраться в том, как он определён для различных встроенных монадических типов, чтобы лучше понять, что и как там всё происходит.

Кстати, когда я говорил, что оператор (>>=) — это усечённая версия композиции стрелок Клейсли, я обещал определить через него их настоящую композицию. Это стандартная функция в языке Haskell, и обозначается она (>=>), а произносится «рыбка» («fish operator»):

(>=>) :: (a -> m b) -> (b -> m c) -> a -> m c
(f >=> g) x = f x >>= g

Значение x у нас имеет тип a, f и g — стрелки Клейсли. Применив стрелку Клейсли f к значению x, мы получим обёрнутое значение. А как передавать в следующую стрелку Клейсли обёрнутое значение, как вы помните, знает оператор (>>=).

В следующей части мы увидим, как работать с определёнными в языке Haskell монадами (а другие подавляющему большинству программистов и не требуются), реализуем ещё одну стандартную монаду под названием Writer («что-то ещё» в ней выражается в записи в лог), чтобы у меня появилось веское основание рассказать вам, что такое моноид и для чего он нужен. А дальше я расскажу вам о ещё одном мощнейшем механизме Haskell под названием «классы типов», и завершу свой рассказ тем, что объясню, как связаны функторы, аппликативные функторы и монады, с которыми мы уже познакомились, с моноидами и классами типов, о которых мне ещё предстоит рассказать. А уже в самом конце я выполню своё обещание и кратко расскажу о монаде ввода-вывода, которая отличается от обычных монад (впрочем, отличается лишь в реализации, а в использовании она так же проста, как и другие монады).
haskell , монады , функторы , аппликативные функторы , моноиды , функциональное программирование , чистые функции , абстракции
—

2,1к

45


Arthur Welf @art_of_press карма86,5 рейтинг8,0
Twitter
Похожие публикации
+105
Функциональное программирование на Javascript 66,8к 938 50
+174
Функциональное программирование для всех 77,5к 1581 144
+32
Чистые функции 1,2к 5 37
Самое читаемое
Сейчас Неделя Месяц
PHP 7.0.0 37
NextCastle Party 2015: как я свою игру показывал 1
«Страшные» абстракции Haskell без математики и без кода (почти). Часть I 5
Как я много раз не бросил разработку своей второй игры 25
Корпоративное использование Android 5.0: рекомендации по безопасности 6
Сетевое оборудование под угрозой? Давайте разбираться… 6
Как общаются жители разных городов 13
Применение модулей LRDIMM в высокопроизводительных серверах 11
SQLi по прежнему в строю 2
Истории аварий на ИБП 2
Вопросы по теме
Копируется ли состояние при каждой операции над монадой состояния в Haskell? 2
Почему cabal test считает все тесты пройденными? 2
Есть ли сайты с интерактивным обучением Haskell? 2
Как запустить код написанный на Haskell из под Java проекта? 4
Как НЕ учить языки? 8
Комментарии (5)

ServPonomarev 2 декабря 2015 в 10:31 –3
Хорошая статья. Костыли функционального подхода расписаны весьма добротно.
danslapman 2 декабря 2015 в 10:55 0
Толсто
mayorovp 2 декабря 2015 в 10:42 (комментарий был изменён) 0
Компилятор, кстати, так и делает — когда он встречаем имя функции, то подставляет вместо него выражение, определённое в её теле.
Нет, так он не делает: если он начнет так делать, то любая рекурсия приведет к исполнимому файлу бесконечного размера.

Распараллеливание мы получаем «из коробки», просто потому, что пишем на Haskell.
И снова странное утверждение. Не слышал я про распаралеливающие трансляторы Хаскеля. Если бы такое делалось автоматически — зачем был бы нужен оператор `par`?
Aetet 2 декабря 2015 в 10:45 0
Превосходная статья, большое спасибо!
andreishe 2 декабря 2015 в 11:04 0
Вы можете проверить это сами: сколько бы раз вы ни передавали этой функции в качестве аргументов значения 1, 2 и 4, вы всегда в качестве результата получите 7

Никакое количество экспериментов, подтверждающих предположение не доказывает, что это предположение всегда истинно. Миллиард раз вызванная функция addThreeNumbers с аргументами 1, 2 и 4, которая миллиард раз вернула 7 не означает, что на следующий раз она вернет именно 7.