Через тернии к Haskell (перевод). 2/2 tutorial

Вторая часть ПЕРЕВОДА короткого и жесткого введения в Haskell. С первой можно ознакомиться здесь

Оригинал здесь

• Чертовски сложная часть
  
  • Разбираемся с IO
  • Объяснение трюка с IO
  • Монады
    
    • Maybe это монада
    • Монада списков
    
    
  
  
• Приложение
  
  • Еще несколько слов о бесконечном дереве
  
  

Чертовски тяжелая часть

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

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

• Что делать с побочными эффектами?
• Зачем понадобился такой странный синтаксис для работы с вводом-выводом (IO)?

Готовьтесь, ответы могут быть не самыми простыми.
Но польза от них будет несомненна.

---

03_Hell/01_IO/01_progressive_io_example.lhs

Разбираемся с IO

tl;dr:

Типичная функция, работающая с IO выглядит практически как императивная программа:

f :: IO a
f = do
  x <- action1
  action2 x
  y <- action3
  action4 x y

• Для присвоения значения объекту мы используем <- .
• В этом примере типом выражения в каждой строке является IO *;
  
  • action1 :: IO b
  • action2 x :: IO ()
  • action3 :: IO c
  • action4 x y :: IO a
  • x :: b, y :: c
  
  
• Несколько объектов имеет тип IO a.
  С такими объектами вы не можете использовать чистые функции.
  Для того, чтобы использовать чистые функции придется сделать action2 (purefunction x) .

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

Не останавливайтесь, если какие-то детали синтаксиса будут немного непонятны.
Мы вернемся к ним в следующем разделе.

Что мы хотим получить?

Получить от пользователя список чисел. Напечатать их сумму

toList :: String -> [Integer]
toList input = read ("[" ++ input ++ "]")

main = do
  putStrLn "Введите список чисел (разделенных запятой):"
  input <- getLine
  print $ sum (toList input)

Поведение этой программы должно быть очевидно.
Но давайте пристально посмотрим на типы.

putStrLn :: String -> IO ()
getLine  :: IO String
print    :: Show a => a -> IO ()

Вы заметили, что каждое выражение в блоке do имеет тип IO a?

main = do
  putStrLn "Введите ... " :: IO ()
  getLine               :: IO String
  print Something       :: IO ()

Также обратите внимание на поведение символа <-.

do
 x <- something

Если something :: IO a, то x :: a.

Важное замечание по использованию IO. Все строки в do-блоке должны выглядеть одним из двух способов:

action1             :: IO a
                    -- в общем случае это будет a = ()

или

value <- action2    -- где
                    -- bar z t :: IO b
                    -- value   :: b

Эти две записи соответствуют различным способам описания действий. Полное осознание этого предложения наступит у вас к концу следующего раздела.

03_Hell/01_IO/01_progressive_io_example.lhs

---

03_Hell/01_IO/02_progressive_io_example.lhs

Давайте разберем, как ведет себя эта программа.Например, что будет, если пользователь введет что-то странное?
Пробуем:

 % runghc 02_progressive_io_example.lhs
    Enter a list of numbers (separated by comma):
    foo
    Prelude.read: no parse

Арррггхххх! Дьявольское сообщение об ошибке и падение программы!
Тогда первым шагом нам надо сделать так, чтобы сообщение об ошибке было легко читаемо.

Для того, чтобы это сделать, мы должны понять что что-то пошло не так.
Один из способов — использовать тип Maybe.
Этот тип очень часто используется в программах на Haskell.

import Data.Maybe

Что это за штука? Maybe это тип, принимающий один параметр. Вот его определение:

data Maybe a = Nothing | Just a

Это хороший способ понять, произошла ли ошибка при попытке создания\вычисления значения.
Функция maybeRead — прекрасный пример подобного подхода.
Эта функция похожа на функцию read (что очень похоже на javascript функцию eval, которая обрабатывает JSON-строку.),
но если что-то пойдет не так, результатом будет Nothing.
А если результат будет правильным, она возвратит Just <значение>.
Не пытайтесь глубоко вникнуть в эту функцию.
Код в ней более низкого уровня чем использует read; .

maybeRead :: Read a => String -> Maybe a
maybeRead s = case reads s of
                  [(x,"")]    -> Just x
                  _           -> Nothing

Теперь, когда код стал более читаемым, напишем функцию, которая делает следующее:
если строка пришла в неверном формате, она вернет Nothing.
В остальных случаях, например для “1,2,3”, она вернет Just [1,2,3].

getListFromString :: String -> Maybe [Integer]
getListFromString str = maybeRead $ "[" ++ str ++ "]"

А теперь протестируем наш код используя функцию main.

main :: IO ()
main = do
  putStrLn "Введите список чисел, разделенных запятой:"
  input <- getLine
  let maybeList = getListFromString input in
      case maybeList of
          Just l  -> print (sum l)
          Nothing -> error "Неверный формат строки. Прощайте."

В случае ошибки, мы показываем симпатичное сообщение об ошибке.

При этом тип каждого выражения в do-блоке функции main остается в виде IO a.
Единственная странная вещь — это error.
Функция error msg просто принимает на вход любой тип (IO () в нашем случае).

Обратите внимание на очень важную вещь — типы всех функций определены заранее.
Существует только одна функция, с типом IO и это: main.
Это значит, что main не является чистой функцией.
Но она использует чистую функцию getListFromString.
Просто глядя на объявленные типы функций мы можем отличить чистые функции от функций с побочными эффектами.


Почему важны чистые функции?
Я могу забыть некоторые вещи, но вот три основных причины:

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

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

03_Hell/01_IO/02_progressive_io_example.lhs

---

03_Hell/01_IO/03_progressive_io_example.lhs

Следующим этапом будет постоянный опрос пользователя, до тех пор, пока он не введет правильный ответ.

Первая часть останется без изменений:

import Data.Maybe

maybeRead :: Read a => String -> Maybe a
maybeRead s = case reads s of
                  [(x,"")]    -> Just x
                  _           -> Nothing
getListFromString :: String -> Maybe [Integer]
getListFromString str = maybeRead $ "[" ++ str ++ "]"

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

askUser :: IO [Integer]
askUser = do
  putStrLn "Введите список чисел, разделенных запятыми:"
  input <- getLine
  let maybeList = getListFromString input in
      case maybeList of
          Just l  -> return l
          Nothing -> askUser

Тип этой функции IO [Integer].
Это значит, что мы получили результат типа [Integer] используя IO действия.
Некоторые люди объясняют это так:

«Это [Integer] внутри IO»

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

В итоге, наша функция main получилась гораздо проще:

main :: IO ()
main = do
  list <- askUser
  print $ sum list

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

• в блоке do каждое выражение должно иметь тип IO a.
  У вас есть достаточно ограниченный набор возможных выражений:
  getLine, print, putStrLn, и т.п.
• Постарайтесь по максимуму использовать чистые функции.
• тип IO a означает следующее — IO действие, которое возвращает результат типа a.
  IO тип для представления действий, а IO a — это тип функции.
  Если вам все еще интересно — читайте следующий раздел.

Немного практики, и использование IO не будет для вас проблемой.

Упражнения:

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

03_Hell/01_IO/03_progressive_io_example.lhs

Объяснение трюка с IO

tl;dr:

Чтобы отличать чистые функции,
main определена как функция, которая меняет состояние мира

main :: World -> World

Функции с этим типом гарантированно будут иметь побочные эффекты. Посмотрите на типичную main-функцию:

main w0 =
    let (v1,w1) = action1 w0 in
    let (v2,w2) = action2 v1 w1 in
    let (v3,w3) = action3 v2 w2 in
    action4 v3 w3

В этом примере много временных значений (w1, w2 и w3)
которые используются для передачи данных следующему действию.

Мы пишем функцию bind или (>>=). Благодаря bind нам больше не понадобятся именованные временные значения.

 main =
  action1 >>= action2 >>= action3 >>= action4
 

Бонус: Haskell припас для нас синтаксический сахар:

 main = do
  v1 <- action1
  v2 <- action2 v1
  v3 <- action3 v2
  action4 v3
 

Зачем нужен такой странный синтаксис, и что из себя представляет тип IO? Пока все это выглядит как какая-то магия.

Забудем на некоторое время о чистых функциях. Сконцентрируемся на побочных эффектах:

askUser :: IO [Integer]
askUser = do
  putStrLn "Введите список чисел, разделенных запятыми:"
  input <- getLine
  let maybeList = getListFromString input in
      case maybeList of
          Just l  -> return l
          Nothing -> askUser

main :: IO ()
main = do
  list <- askUser
  print $ sum list

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

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

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

В Haskell-е состояние мира задается явно. Мы четко говорим, что функция main потенциально может изменить состояние мира. И ее тип будет выглядеть примерно так:

main :: World -> World

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

Haskell считает, что мир — это входной параметр функции main.
Но реальный тип этой функции больше похож на

main :: World -> ((),World)

(Для тех, кому интересно, тип выражения — data IO a = IO {unIO :: State# RealWorld -> (# State# RealWorld, a #)}. Все # связаны с оптимизацией, и в примере я поменял местами несколько полей. Но в целом, идея не поменялась.)


Тип () — это пустой тип.
Пустота.

Давайте перепишем нашу функцию, не забывая о :

main w0 =
    let (list,w1) = askUser w0 in
    let (x,w2) = print (sum list,w1) in
    x

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

World -> (a,World)

Где a — тип результата.
Например, функция getChar должна иметь тип World -> (Char,World).

Другая неочевидная вещь — порядок вычисления функций.
В Haskell, если вы попытаетесь вычислить f a b, у вас будет несколько вариантов:

• вычислить a, потом b потом f a b
• сначала вычислить b, потом a и в завершение f a b.
• параллельно вычислить a и b, а затем f a b

Поскольку язык функционально чистый — такие фокусы реальны.

Если теперь присмотреться к функции main, очевидно, что первая строка должна вычисляться раньше второй, потому что первая строка вычисляте параметр для второй.

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

• напечатать что-то на экране
• изменить идентификатор мира
• вернуть в качестве результата ((),новый_идентификатор_мира).

Теперь main выглядит просто ужасно. Давайте проделаем то же самое с функцией askUser :

askUser :: World -> ([Integer],World)

До

askUser :: IO [Integer]
askUser = do
  putStrLn "Введите список чисел:"
  input <- getLine
  let maybeList = getListFromString input in
      case maybeList of
          Just l  -> return l
          Nothing -> askUser

После

askUser w0 =
    let (_,w1)     = putStrLn "Enter a list of numbers:" in
    let (input,w2) = getLine w1 in
    let (l,w3)     = case getListFromString input of
                      Just l   -> (l,w2)
                      Nothing  -> askUser w2
    in
        (l,w3)

Похоже, но уродливо. Вы только посмотрите на эти корявые переменные w*.

Урок, который мы вынесли — наивная реализация ввода-вывода в функционально чистом языке выглядит ужасно.

К счастью, есть более прямой подход к решению этой проблемы. Мы видим паттерн. Каждая строка представлена как:

let (y,w') = action x w in

Даже если первый параметр x не нужен, результатом будет пара (answer, newWorldValue). Каждая функция f должна иметь тип, похожий на:

f :: World -> (a,World)

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

let (y,w1) = action1 w0 in
let (z,w2) = action2 w1 in
let (t,w3) = action3 w2 in
...

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

Например, мы могли бы написать:

let (_,w1) = action1 x w0   in
let (z,w2) = action2 w1     in
let (_,w3) = action3 x z w2 in
...

И, естественно, actionN w :: (World) -> (a,World).

ВАЖНО! есть только два паттерна, на которые стоит обратить внимание:

let (x,w1) = action1 w0 in
let (y,w2) = action2 x w1 in

и

let (_,w1) = action1 w0 in
let (y,w2) = action2 w1 in

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

bind :: (World -> (a,World))
        -> (a -> (World -> (b,World)))
        -> (World -> (b,World))

Не забывайте о том, что (World -> (a,World)) это тип для IO действия.
Давайте для простоты его переименуем:

type IO a = World -> (a, World)

Пара примеров:

getLine :: IO String
print :: Show a => a -> IO ()

getLine это IO действие, которое получает мир в качестве параметра и возвращает пару (String,World). Можно сказать, типом getLine будет IO String.
Также мы можем ее воспринимать как IO действие, которое вернет нам String “заключенную внутрь IO” .

Функция print тоже достаточно интересна. Она принимает на вход параметр, который потом отобразит. Но на самом деле она принимает два параметра. Первым параметром идет значение, которое будет отображаться, вторым — состояние мира. В качестве результата она возвращает пару ((),World). То есть она изменяет состояние мира, но не возвращает каких-либо данных.

Этот тип позволит упростить нам определение типа для функции bind:

bind :: IO a
        -> (a -> IO b)
        -> IO b

bind принимает 2 IO действия в качестве аргументов и возвращает еще одно IO действие.

Теперь освежим в памяти важные паттерны. Первый был таким:

let (x,w1) = action1 w0 in
let (y,w2) = action2 x w1 in
(y,w2)

Обратите внимание на типы:

action1  :: IO a
action2  :: a -> IO b
(y,w2)   :: IO b

Выглядит знакомо, не правда ли?

(bind action1 action2) w0 =
    let (x, w1) = action1 w0
        (y, w2) = action2 x w1
    in  (y, w2)

Основная идея заключается в том, чтобы спрятать параметр World при помощи этой функции. Поехали! Вот приблизительно то, что мы хотим получить:

let (line1,w1) = getLine w0 in
let ((),w2) = print line1 in
((),w2)

А теперь, задействуем функцию bind :

(res,w2) = (bind getLine (\l -> print l)) w0

Поскольку print имеет тип (World -> ((),World)), мы знаем, что res = () (null type).
Если вы не видите здесь особой уличной магии, попробуем написать программу из трех строк.

let (line1,w1) = getLine w0 in
let (line2,w2) = getLine w1 in
let ((),w3) = print (line1 ++ line2) in
((),w3)

Что аналогично следующему:

(res,w3) = bind getLine (\line1 ->
             bind getLine (\line2 ->
               print (line1 ++ line2)))

А теперь заметили?
Да, больше никаких временных переменных World!
Это МА.ГИ.Я

Но мы можем воспользоваться другим синтаксисом.
Давайте заменим bind на (>>=).
(>>=) это инфиксная функция, такая же, как
(+); напоминаю 3 + 4 ⇔ (+) 3 4

(res,w3) = getLine >>=
           \line1 -> getLine >>=
           \line2 -> print (line1 ++ line2)

Хо хо хо! Всех с новым годом! Haskell припас для нас синтаксический сахар:

do
  x <- action1
  y <- action2
  z <- action3
  ...

Можно заменить на:

action1 >>= \x ->
action2 >>= \y ->
action3 >>= \z ->
...

Вы можете использовать x в action2 и x с y в action3.

Но что насчет строк, которые не используют <-?
Легко! У нас есть функция blindBind:

blindBind :: IO a -> IO b -> IO b
blindBind action1 action2 w0 =
    bind action (\_ -> action2) w0

Я специально не упрощал это выражение.
Конечно, если мы хотим сделать код проще, мы можем использовать оператор (>>).

И таким образом

do
    action1
    action2
    action3

Превращается в

action1 >>
action2 >>
action3

Кстати, вот еще одна достаточно полезная функция:

putInIO :: a -> IO a
putInIO x = IO (\w -> (x,w))

Это стандартный способ запихивать чистые значения в “IO контекст”.
Обычно putInIO называют return.
Такое название функции очень путает при изучении Haskell-а. return очень отличается от аналогов в других языках.

---

03_Hell/01_IO/21_Detailled_IO.lhs

Напоследок, давайте перепишем наш пример:

askUser :: IO [Integer]
askUser = do
  putStrLn "Введите список числе, разделенных запятыми:"
  input <- getLine
  let maybeList = getListFromString input in
      case maybeList of
          Just l  -> return l
          Nothing -> askUser

main :: IO ()
main = do
  list <- askUser
  print $ sum list

Можно переписать как:

import Data.Maybe

maybeRead :: Read a => String -> Maybe a
maybeRead s = case reads s of
                  [(x,"")]    -> Just x
                  _           -> Nothing
getListFromString :: String -> Maybe [Integer]
getListFromString str = maybeRead $ "[" ++ str ++ "]"
askUser :: IO [Integer]
askUser = 
    putStrLn "Введите список чисел, разделенных запятыми:" >>
    getLine >>= \input ->
    let maybeList = getListFromString input in
      case maybeList of
        Just l -> return l
        Nothing -> askUser

main :: IO ()
main = askUser >>=
  \list -> print $ sum list

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

А теперь, давайте представим, как бы все это выглядело без (>>) и (>>=).

03_Hell/01_IO/21_Detailled_IO.lhs

---

03_Hell/02_Monads/10_Monads.lhs

Монады

А теперь раскроем секретный секрет: IO — это монада.
Использование монады значит, что вы можете использовать синтаксический сахар do нотации.
Но самое главное — это паттерн проектирования, который позволит писать более чистый и понятный код.

Важное замечение:

• Монады не обязательно связаны с побочными эффектами!
  Существует множество чистых монад.
• Суть монад — в композиции вычислений

В терминах языка Haskell — Monad это класс типов.
Чтобы стать экземпляром этого класса, вам необходимо определить функции (>>=) и return.
Функция (>>) будет создана автоматически на основе (>>=).
Вот (почти полное)определение класса Monad :

class Monad m  where
  (>>=) :: m a -> (a -> m b) -> m b
  return :: a -> m a

  (>>) :: m a -> m b -> m b
  f >> g = f >>= \_ -> g

  -- Эту функцию в большинстве случаев вы можете игнорировать
  -- я думаю она существует только как историческое наследие
  fail :: String -> m a
  fail = error

Замечания:

• ключевое слово class это не то, что вы думаете.
  Класс в Haskell это не класс из ООП.
  Класс в Haskell больше похож на интерфейс в Java или C#.
  Лучше было бы его назвать typeclass.
  Что значит множество классов.
  Чтобы тип мог принадлежать этому классу, тип должен реализовать все функции класса.
• В данном конкретном случае тип m должен быть типом, который может принимать аргумент.
  например IO a, а также Maybe a, [a], и т.д.
• Чтобы быть полезной монадой, ваша функция должна соблюдать некоторые законы.
  Если ваша функция будет нарушать эти законы, будут происходить странные вещи:
  

  return a >>= k  ==  k a
  m >>= return  ==  m
  m >>= (\x -> k x >>= h)  ==  (m >>= k) >>= h
  

  
  

Maybe — это монада

Существует много типов, которые являются экземпляром Monad.
Самый простой пример — Maybe.
Если у вас есть набор Maybe значений, вы можете воспользоваться монадами для работы с ними. В частности это может быть полезно, чтобы избавиться от вложенных if..then..else...

Представьте себе сложную банковскую операцию вы можете претендовать на бонус 700€ только если у вас есть история операций без ухода в минус.

deposit  value account = account + value
withdraw value account = account - value

eligible :: (Num a,Ord a) => a -> Bool
eligible account =
  let account1 = deposit 100 account in
    if (account1 < 0)
    then False
    else
      let account2 = withdraw 200 account1 in
      if (account2 < 0)
      then False
      else
        let account3 = deposit 100 account2 in
        if (account3 < 0)
        then False
        else
          let account4 = withdraw 300 account3 in
          if (account4 < 0)
          then False
          else
            let account5 = deposit 1000 account4 in
            if (account5 < 0)
            then False
            else
              True

main = do
  print $ eligible 300 -- True
  print $ eligible 299 -- False

03_Hell/02_Monads/10_Monads.lhs

---

03_Hell/02_Monads/11_Monads.lhs

А теперь наведем порядок в этом коде используя Maybe и ее Monad-ическую сущность:

deposit :: (Num a) => a -> a -> Maybe a
deposit value account = Just (account + value)

withdraw :: (Num a,Ord a) => a -> a -> Maybe a
withdraw value account = if (account < value) 
                         then Nothing 
                         else Just (account - value)

eligible :: (Num a, Ord a) => a -> Maybe Bool
eligible account = do
  account1 <- deposit 100 account 
  account2 <- withdraw 200 account1 
  account3 <- deposit 100 account2 
  account4 <- withdraw 300 account3 
  account5 <- deposit 1000 account4
  Just True

main = do
  print $ eligible 300 -- Just True
  print $ eligible 299 -- Nothing

03_Hell/02_Monads/11_Monads.lhs

---

03_Hell/02_Monads/12_Monads.lhs

Уже неплохо, но можно сделать еще лучше:

deposit :: (Num a) => a -> a -> Maybe a
deposit value account = Just (account + value)

withdraw :: (Num a,Ord a) => a -> a -> Maybe a
withdraw value account = if (account < value) 
                         then Nothing 
                         else Just (account - value)

eligible :: (Num a, Ord a) => a -> Maybe Bool
eligible account =
  deposit 100 account >>=
  withdraw 200 >>=
  deposit 100  >>=
  withdraw 300 >>=
  deposit 1000 >>
  return True

main = do
  print $ eligible 300 -- Just True
  print $ eligible 299 -- Nothing

Итак, мы доказали что монады могут сделать наш код более элегантным.
Вообще говоря, подобное использование Maybe сработает в большинстве императивных языков.
Это достаточно естественная конструкция.

Важное замечание:

Первое вычисление, результатом которого будет Nothing остановит все дальнейшие вычисления.
Это значит, что выполнится не весь код.
И эта оптимизация доступна вам абсолютно бесплатно, благодаря ленивости языка.

Можете переписать этот код, используя определение (>>=) для Maybe
:

instance Monad Maybe where
    (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
    Nothing  >>= _  = Nothing
    (Just x) >>= f  = f x

    return x = Just x

Монада Maybe доказала свою полезность даже в таком маленьком примере. Мы также видели использование монады IO. Но есть и более интересный пример — списки.

03_Hell/02_Monads/12_Monads.lhs

---

03_Hell/02_Monads/13_Monads.lhs

Монада списков

Монада списка позволяет нам моделировать недетерминированные вычисления.
Например:

import Control.Monad (guard)

allCases = [1..10]

resolve :: [(Int,Int,Int)]
resolve = do
              x <- allCases
              y <- allCases
              z <- allCases
              guard $ 4*x + 2*y < z
              return (x,y,z)

main = do
  print resolve

МА. ГИ. Я. :

[(1,1,7),(1,1,8),(1,1,9),(1,1,10),(1,2,9),(1,2,10)]

Для монады списка тоже есть синтаксический сахар:

  print $ [ (x,y,z) | x <- allCases,
                      y <- allCases,
                      z <- allCases,
                      4*x + 2*y < z ]

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

• IO,
• недетерминированных вычислений,
• генерации псевдослучайных чисел,
• хранения конфигурации,
• работы с состояниями,
• …

Если вы вы добрались до этого места, мои поздравления!
Теперь и вы знаете кунг-фу монады! (Конечно, вам понадобится практика чтобы к ним привыкнуть. Напишите парочку своих. Но вы уже сделали огромный шаг в этом направлении)

03_Hell/02_Monads/13_Monads.lhs

Приложение

Этот раздел не относится напрямую к изучению Haskell. Мы просто уделим большее внимание некоторым деталям.

---

04_Appendice/01_More_on_infinite_trees/10_Infinite_Trees.lhs

Еще кое-что по поводу бесконечных деревьев

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

1. отсутствие дубликатов в узлах дерева
2. упорядоченное дерево

В данном разделе мы займемся первым свойством.
Касательно второго — мы немного ослабим его, но постараемся быть настолько близко к идеалу, насколько возможно.

Для начала давайте создадим список из набора псевдослучайных чисел:

shuffle = map (\x -> (x*3123) `mod` 4331) [1..]

Чтобы освежить память, продублируем реализациюtreeFromList

treeFromList :: (Ord a) => [a] -> BinTree a
treeFromList []    = Empty
treeFromList (x:xs) = Node x (treeFromList (filter (<x) xs))
                             (treeFromList (filter (>x) xs))

и treeTakeDepth:

treeTakeDepth _ Empty = Empty
treeTakeDepth 0 _     = Empty
treeTakeDepth n (Node x left right) = let
          nl = treeTakeDepth (n-1) left
          nr = treeTakeDepth (n-1) right
          in
              Node x nl nr

Посмотрим на результат:

main = do
      putStrLn "take 10 shuffle"
      print $ take 10 shuffle
      putStrLn "\ntreeTakeDepth 4 (treeFromList shuffle)"
      print $ treeTakeDepth 4 (treeFromList shuffle)

% runghc 02_Hard_Part/41_Infinites_Structures.lhs
take 10 shuffle
[3123,1915,707,3830,2622,1414,206,3329,2121,913]
treeTakeDepth 4 (treeFromList shuffle)

< 3123
: |--1915
: |  |--707
: |  |  |--206
: |  |  `--1414
: |  `--2622
: |     |--2121
: |     `--2828
: `--3830
:    |--3329
:    |  |--3240
:    |  `--3535
:    `--4036
:       |--3947
:       `--4242

Ура! Заработало! Но оно будет работать только в том случае, если вам есть что добавить в ветку.

Например:

treeTakeDepth 4 (treeFromList [1..]) 

будет выполняться бесконечно.
Это происходит потому, что код пытается получить голову выражения filter (<1) [2..].
Но filter не настолько умен, чтобы понять, что результатом выражения будет пустой список.

Тем не менее это хороший пример того, что могут делать нестрогие программы.

Упражнение для читателя:

• Докажите существование такого числа n, что treeTakeDepth n (treeFromList shuffle) упадет в бесконечный цикл.
• Найдите верхнюю границу для n.
• Докажите, что не существует такого shuffle списка, выполняя который, программа завершится.

04_Appendice/01_More_on_infinite_trees/10_Infinite_Trees.lhs

---

04_Appendice/01_More_on_infinite_trees/11_Infinite_Trees.lhs

Давате немного модифицируем
treeFromList и shuffle для того, чтобы избавиться от этой проблемы.

Первая проблема — нехватка случайных числе в нашей реализации shuffle.
Мы сгенерировали только 4331 различных чисел.
Улучшим нашу функцию shuffle.

shuffle = map rand [1..]
          where 
              rand x = ((p x) `mod` (x+c)) - ((x+c) `div` 2)
              p x = m*x^2 + n*x + o -- some polynome
              m = 3123    
              n = 31
              o = 7641
              c = 1237

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

Строго говоря, мы не можем сказать, пустой ли список filter (<x) xs.
Чтобы решить эту проблему, я немного поломаю нашу реализацию двоичного дерева. В новой реализации для некоторых узлов не будет выполняться следующее условие:

Любой элемент левой (соотв. правой) должен быть строго меньше (соотв. больше) значения в корне дерева.

При этом дерево останется практически упорядоченным. Более того, на этапе создания дерева мы обеспечим уникальность узлов.

В новой версии treeFromList мы просто заменили filter на safefilter.

treeFromList :: (Ord a, Show a) => [a] -> BinTree a
treeFromList []    = Empty
treeFromList (x:xs) = Node x left right
          where 
              left = treeFromList $ safefilter (<x) xs
              right = treeFromList $ safefilter (>x) xs

Функция safefilter почти идентична filter но не падает в бесконечный цикл при обработке бесконечных деревьев. Если она не может найти подходящий элемент за 10000 шагов, она прерывает поиск.

safefilter :: (a -> Bool) -> [a] -> [a]
safefilter f l = safefilter' f l nbTry
  where
      nbTry = 10000
      safefilter' _ _ 0 = []
      safefilter' _ [] _ = []
      safefilter' f (x:xs) n = 
                  if f x 
                     then x : safefilter' f xs nbTry 
                     else safefilter' f xs (n-1) 

Запустим же программу и возрадуемся:

main = do
      putStrLn "take 10 shuffle"
      print $ take 10 shuffle
      putStrLn "\ntreeTakeDepth 8 (treeFromList shuffle)"
      print $ treeTakeDepth 8 (treeFromList $ shuffle)

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

Даже если увеличить глубину поиска с 8 до 100,
функция будет работать, и при этом не сожрет всю оперативную память!


Упражнение для читателя:

• Даже для больших значений deep и nbTry, функция работает нормально.Но в самом худшем случае нас может ожидать экспоненциальный рост.
  Найдите наихудший возможный вариант списка для treeFromList.
  подсказка: подумайте о ([0,-1,-1,....,-1,1,-1,...,-1,1,...]).
• Сначала я пытался реализовать safefilter следующим образом:
  

  safefilter' f l = if filter f (take 10000 l) == []
                    then []
                    else filter f l
  

  
  Объясните, почему эта функция зациклится.
  
• Предположим, что shuffle это список случайных значений.
  Если вы проанализируете эту структуру, то заметите, что со 100% вероятностью она конечна.
  Используя код приведенный ниже
  (допустим, что мы можем использоватьsafefilter' напрямую)
  напишите такую функцию f которая сгенерирует бесконечный список после
  treeFromList’ shuffle. Приведите доказательство.
  

treeFromList' []  n = Empty
treeFromList' (x:xs) n = Node x left right
    where
        left = treeFromList' (safefilter' (<x) xs (f n)
        right = treeFromList' (safefilter' (>x) xs (f n)
        f = ???

04_Appendice/01_More_on_infinite_trees/11_Infinite_Trees.lhs

Благодарности (от автора, не переводчика)

Спасибо /r/haskell и
/r/programming.
Ваши комментарии неоценимы.

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