-2-2.jpg "Через тернии к Haskel (перевод). 2/2")
Вторая часть ПЕРЕВОДА короткого и жесткого введения в Haskell. С первой можно ознакомиться здесь
Оригинал здесь
Чертовски тяжелая часть
Поздравляю! Вы добрались реально далеко.
А теперь начнется треш, угар и содомия :).
Если мы с вами похожи, вы уже немного въехали в функциональный стиль. Вы поняли преимущества, которые дает ленивость по умолчанию. Но вы пока еще не совсем понимаете как можно написать реально полезную программу. В частности:
- Что делать с побочными эффектами?
- Зачем понадобился такой странный синтаксис для работы с вводом-выводом (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 baction2 x :: IO ()action3 :: IO caction4 x y :: IO ax :: 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 — прекрасный пример подобного подхода.
Эта функция похожа на функцию read5,
но если что-то пойдет не так, результатом будет 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
-2-2-2.jpg "Через тернии к Haskel (перевод). 2/2")
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
Но эта переменная доступна не всем функциям.
Функции, работающие с этой переменной не чистые.
Функции, которые не используют ее — являются чистыми6.
Haskell считает, что мир — это входной параметр функции main.
Но реальный тип этой функции больше похож на7:
main :: World -> ((),World)
Тип () — это пустой тип.
Пустота.
Давайте перепишем нашу функцию, не забывая о :
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
-2-2-3.jpg "Через тернии к Haskel (перевод). 2/2")
А теперь будет небольшой фокус.
Мы заставим “исчезнуть” переменную, хранящую состояние мира. Мы свяжем (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
Монады
-2-2-4.jpg "Через тернии к Haskel (перевод). 2/2")
А теперь раскроем секретный секрет: 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
Монада списков
-2-2-5.jpg "Через тернии к Haskel (перевод). 2/2")
Монада списка позволяет нам моделировать недетерминированные вычисления.
Например:
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,
- недетерминированных вычислений,
- генерации псевдослучайных чисел,
- хранения конфигурации,
- работы с состояниями,
- …
Если вы вы добрались до этого места, мои поздравления!
Теперь и вы знаете кунг-фу монады8!
03_Hell/02_Monads/13_Monads.lhs
Приложение
Этот раздел не относится напрямую к изучению Haskell. Мы просто уделим большее внимание некоторым деталям.
04_Appendice/01_More_on_infinite_trees/10_Infinite_Trees.lhs
Еще кое-что по поводу бесконечных деревьев
В разделеБесконечные структуры мы разобрали пару простых бесконечных структур. К сожалению, наше дерево лишилось двух свойств:
- отсутствие дубликатов в узлах дерева
- упорядоченное дерево
В данном разделе мы займемся первым свойством.
Касательно второго — мы немного ослабим его, но постараемся быть настолько близко к идеалу, насколько возможно.
Для начала давайте создадим список из набора псевдослучайных чисел:
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 за время, потраченное на корректировку моего английского текста. Спасибо, мужик.
- Даже если большинство языков пытается скрыть этот факт, он все равно остается фактом.↩
- Я жульничаю. В курсе. К вопросу о нестрогих вычислениях мы вернемся позже.↩
- Для самых смелых подробное описание сопоставление с образцом можно изучитьздесь.↩
- Обратите внимание, что
squareEvenSum''эффективнее двух других реализаций. Порядок(.)действительно имеет значение.↩ - Что очень похоже на javascript функцию
eval, которая обрабатывае JSON-строку.↩ - Из этого правила есть опасные исключения. Но в реальных программах оно вам не понадобится. Разве что в случае глубокой отладки.↩
- Для тех, кому интересно, тип выражения —
data IO a = IO {unIO :: State# RealWorld -> (# State# RealWorld, a #)}. Все#связаны с оптимизацией, и в примере я поменял местами несколько полей. Но в целом, идея не поменялась.↩ - Конечно, вам понадобится практика чтобы к ним привыкнуть. Напишите парочку своих. Но вы уже сделали огромный шаг в этом направлении.↩
Автор: mungobungo
