Авторы Темы Разделы О нас Ресурсы
ruHaskell

Умная проверка

let author   = "Роман Чепляка"
    date     = fromGregorian 2015 may 04
    category = "Теория"
    tags     = ["обработка ошибок"]
Оригинал

Перевод с английского - Денис Шевченко

Сегодня мы рассмотрим различные способы обработки ошибок в Haskell. Начнём с хорошо известной монады Either, далее перейдём к менее распространённому аппликативному функтору Validation, а затем повысим эффективность и удобство последнего.

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

Пример

Итак, начнём:

{-# LANGUAGE GeneralizedNewtypeDeriving, KindSignatures, DataKinds,
             ScopedTypeVariables, RankNTypes, DeriveFunctor #-}
import Text.Printf
import Text.Read
import Control.Monad
import Control.Applicative
import Control.Applicative.Lift (Lift)
import Control.Arrow (left)
import Data.Functor.Constant (Constant)
import Data.Monoid
import Data.Traversable (sequenceA)
import Data.List (intercalate, genericTake, genericLength)
import Data.Proxy
import System.Exit
import System.IO
import GHC.TypeLits

В нашем примере мы будем читать список целых чисел из файла, по одному числу на строку, а затем выведем сумму этих чисел. Вот простейший способ сделать это:

printSum1 :: FilePath -> IO ()
printSum1 path = print . sum . map read . lines =<< readFile path

Этот код работает именно так, как мы ожидаем, однако есть одна проблема: если строка будет содержать не число, а что-нибудь другое, мы получим невнятную ошибку вида:

Prelude.read: no parse

Монада Either

Перепишем нашу функцию, чтобы возможные ошибки не прошли мимо нас:

parseNum
  :: Int -- Номер строки (для отчёта об ошибке)
  -> String -- Содержимое строки
  -> Either String Integer
     -- Здесь будет либо число, извлечённое из строки, либо сообщение об ошибке
parseNum ln str =
  case readMaybe str of
    Just num -> Right num
    Nothing -> Left $
      printf "Bad number on line %d: %s" ln str

-- Печатаем сообщение и выходим
die :: String -> IO ()
die msg = do
  hPutStrLn stderr msg
  exitFailure

printSum2 :: FilePath -> IO ()
printSum2 path =
  either die print .
  liftM sum .
  sequence . zipWith parseNum [1..] .
  lines =<< readFile path

Теперь, если на одной из строк нашего файла окажется какой-нибудь хлам, мы увидим нечто подобное:

Bad number on line 2: foo

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

  1. Мы используем функцию readMaybe вместо read, что помогает нам сформировать вменяемое сообщение об ошибке. Именно для этого нам нужен номер проблемной строки.
  2. Вместо того, чтобы кидать исключение (с помощью функции error), мы возвращаем чистое Either-значение, а затем комбинируем все эти Either-значения, используя монадическую природу Either.

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

Аппликативный функтор Validation

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

Вы, засучив рукава, берётесь за дело, будучи уверенным в вашей Haskell-программе. И вот что она выдаёт вам:

Bad number on line 378: 12o0

Ага, попалась! Кто-то поставил букву o вместо нуля. Исправим же это: переходим к строке 378, исправляем букву на цифру, сохраняем файл, и перезапускаем нашу программу. Но тут снова неприятность:

Bad number on line 380: 11i3

Так, ещё одна: вместо единицы стоит буква i. Исправили, сохранили… Стоп. Если бы программа сообщила нам об этих двух ошибках сразу, мы бы исправили их быстрее! В самом деле, почему бы не сделать так, чтобы наша программа проверила каждую строку в файле и сообщила нам обо всех найденных ошибках сразу? Сказано - сделано. Однако в этом случае мы уже не сможем воспользоваться ни экземпляром Monad Either, ни Applicative Either. Нам нужен тип Validation.

Аппликативный функтор Validation совмещает два Either-значения таким образом, что если они оба инициированы Left, эти Left-значения объединяются через моноидную операцию (на самом деле, достаточно и Semigroup). Это позволяет нам собирать ошибки с разных строк нашего файла. Вот как это выглядит:

newtype Validation e a = Validation { getValidation :: Either e a }
  deriving Functor

instance Monoid e => Applicative (Validation e) where
  pure = Validation . Right
  Validation a <*> Validation b = Validation $
    case a of
      Right va -> fmap va b
      Left ea -> either (Left . mappend ea) (const $ Left ea) b

Следующий пример демонстрирует отличие между стандартным экземпляром Applicative и Validation:

> let e1 = Left "error1"; e2 = Left " error2"
> e1 *> e2
Left "error1"

> getValidation $ Validation e1 *> Validation e2
Left "error1 error2"

Хорошая реализация подобного аппликативного функтора имеется в пакете transformers. Ross Paterson заметил, что этот функтор может формироваться так:

type Errors e = Lift (Constant e)

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

printSum3 :: FilePath -> IO ()
printSum3 path =
  either (die . intercalate "\n") print .
  liftM sum .
  getValidation . sequenceA .
  map (Validation . left (\e -> [e])) .
  zipWith parseNum [1..] .
  lines =<< readFile path

Теперь нам достаточно единожды запустить программу, чтобы разом увидеть все обнаруженные ею ошибки:

Bad number on line 378: 12o0
Bad number on line 380: 11i3

Упражнение. Можем ли мы использовать Writer [String] для сбора всех сообщений об ошибках?

Упражнение. Когда мы склеиваем списки, существует риск прийти к квадратичной сложности. Произойдёт ли это в вышеприведённой функции? И должно ли это произойти в функции, которая использует функтор Validation, основанный на list monoid?

Функтор Validation: ещё умнее

На следующий день бухгалтер присылает нам другой здоровенный файл с той же просьбой: вычислить сумму чисел. Бодро запускаем нашу программу и видим большущий список ошибок следующего вида:

Bad number on line 1: 27297.
Bad number on line 2: 11986.
Bad number on line 3: 18938.
Bad number on line 4: 22820.
...

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

  1. Удобство. Едва ли пользователь прочтёт более, нежели, скажем, 10 сообщений за раз. И если мы попытаемся отобразить огромное количество сообщений об ошибках на веб-странице, это и работать будет медленно, и выглядеть будет ужасно.
  2. Эффективность. Раз уж мы согласны с тем фактом, что нет смысла выводить более 10 первых сообщений об ошибках, то, получив те самые 10 сообщений, не имеет смысла продолжать обрабатывать наш файл.

Для достижения каждой из этих двух целей нам понадобится свой механизм.

Ограниченные списки

Создадим наш собственный тип BoundedList, похожий на список, который будет хранить первые n элементов и игнорировать всё остальное. Это в первую очередь относится к нашей первой цели, а именно удобству пользователя (хотя достижения второй цели это тоже касается).

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

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

На уровне значений, мы основываем новый тип на difference list, далее DL (Прим. переводчика - речь идёт о Data.DList), во избежании квадратичной сложности, упомянутой ранее:

data BoundedList (n :: Nat) a =
  BoundedList
    !Integer -- Текущая длина списка
    (Endo [a])

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

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

singleton :: KnownNat n => a -> BoundedList n a
singleton a = fromList [a]

toList :: BoundedList n a -> [a]
toList (BoundedList _ (Endo f)) = f []

fromList :: forall a n . KnownNat n => [a] -> BoundedList n a
fromList lst = BoundedList (min len limit) (Endo (genericTake limit lst ++))
  where
    limit = natVal (Proxy :: Proxy n)
    len = genericLength lst

instance KnownNat n => Monoid (BoundedList n a) where
  mempty = BoundedList 0 mempty
  mappend b1@(BoundedList l1 f1) (BoundedList l2 f2)
    | l1 >= limit = b1
    | l1 + l2 <= limit = BoundedList (l1 + l2) (f1 <> f2)
    | otherwise = BoundedList limit (f1 <> Endo (genericTake (limit - l1)) <> f2)
    where
      limit = natVal (Proxy :: Proxy n)

full :: forall a n . KnownNat n => BoundedList n a -> Bool
full (BoundedList l _) = l >= natVal (Proxy :: Proxy n)

null :: BoundedList n a -> Bool
null (BoundedList l _) = l <= 0

SmartValidation

Теперь мы создадим аппликативный функтор SmartValidation, который будет прекращать свою работу, как только продолжать собирать ошибки станет бессмысленным. Это нечто среднее между функтором Either, способным хранить одну-единственную ошибку, и функтором Validation, хранящим все ошибки.

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

Упражение. Попробуйте реализовать тип и его аппликативный экземпляр, соответствующие вышеозвученному требованию.

Попробовали? У вас получилось? Это не риторический вопрос, мне действительно интересно (поэтому дайте мне знать о ваших результатах). Похожа ли ваша реализация на мою, или, может, она легче? А может, наоборот, сложнее?

Итак, вот моя реалиация:

newtype SmartValidation (n :: Nat) e a = SmartValidation
  { getSmartValidation :: forall r .
      Either (BoundedList n e) (a -> r) -> Either (BoundedList n e) r }
  deriving Functor

instance KnownNat n => Applicative (SmartValidation n e) where
  pure x = SmartValidation $ \k -> k <*> Right x
  SmartValidation a <*> SmartValidation b = SmartValidation $ \k ->
    let k' = fmap (.) k in
    case a k' of
      Left errs | full errs -> Left errs
      r -> b r

А вот функции для создания и анализа значений типа SmartValidation:

-- Конвертируем SmartValidation в Either
fatal :: SmartValidation n e a -> Either [e] a
fatal = left toList . ($ Right id) . getSmartValidation

-- Конвертируем Either в SmartValidation
nonFatal :: KnownNat n => Either e a -> SmartValidation n e a
nonFatal a = SmartValidation $ (\k -> k <+> left singleton a)

-- Похожа на <*>, но склеивает ошибки
(<+>)
  :: Monoid e
  => Either e (a -> b)
  -> Either e a
  -> Either e b
a <+> b = case (a,b) of
  (Right va, Right vb) -> Right $ va vb
  (Left e,   Right _)  -> Left e
  (Right _,  Left e)   -> Left e
  (Left e1,  Left e2)  -> Left $ e1 <> e2

Упражнение. Подумайте над тем, что делает fmap (.) k в определении <*>.

Упражнение. В определении <*>, должны ли мы проверять, является ли k полным перед вычислением a k'?

Упражнение. Мы разработали два механизма - BoundedList и SmartValidation, которые делают практически одно и то же, но на разных уровнях. Достаточен ли какой-то из этих двух механизмов для достижения обеих целей (удобство пользователя и эффективность) в том случае, если количество отображаемых ошибок будет велико?

Упражнение. Если бы функтор SmartValidation был основан не на DL, а на обыкновенных списках, насколько велика вероятность достижения квадратичной сложности по сравнению с решением, основанным на Validation?

Заключение

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