Учебник по Haskell - читать бесплатно онлайн полную версию книги автора Unknown (ч. 5)

0.0

CAF

GHC.Conc.Signal

0.0

CAF

Main

0.2

100.0

right

Main

0.0

left

Main

99.8

Мы видим, что почти всё время работы программа провела в функции concatL. Функция concatR была

вычислена мгновенно (time) и почти не потребовала ресусов памяти (alloc). У нас есть две пары колонок ре-

зультатов. individual указывает на время вычисления функции, а inherited – на время вычисления функции

и всех дочерних функций. Колонка entries указывает число вызовов функции. Если мы хотим проверить все

функции мы можем не указывать функции прагмами. Для этого при компиляции указывается флаг auto-all.

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

Они называются в отчёте как CAF. Для того чтобы вычислитель следил за каждой константой по отдельности

необходимо указать флаг caf-all. Попробуем на таком модуле:

module Main where

fun1 = test concatL - test concatR

fun2 = test concatL + test concatR

Статистика выполнения программы | 167

test f = last $ f $ map return [1 .. 1e4]

concatR = foldr (++) []

concatL = foldl (++) []

main = print fun1 >> print fun2

Скомпилируем:

$ ghc --make concat2.hs -rtsopts -prof -auto-all -caf-all -fforce-recomp

$ ./concat2 +RTS -p

0.0

20000.0

После этого можно открыть файл concat2. prof и посмотреть итоговую статистику по всем значениям.

Программа с включённым профилированием будет работать гораздо медленей, не исключено, что ей не

хватит памяти на стеке, в этом случае вы можете добавить памяти с помощью флага вычислителя K, впрочем

если это произойдёт GHC подскажет вам что делать.

Динамика изменения объёма кучи

В предыдущем разделе мы смотрели общее время и память затраченные на вычисление функции. В этом

мы научимся измерять динамику изменения расхода памяти на куче. По этому показателю можно понять

в какой момент в программе возникают утечки памяти. Мы увидим характерные горбы на картинках, ко-

гда GC будет активно запрашивать новую память. Для этого сначала нужно скомпилировать программу с

флагом prof как и в предыдущем разделе, а при выполнении программы добавить один из флагов hc, hm,

hd, hy или hr. Все они начинаются с буквы h, от слова heap (куча). Вторая буква указывает тип графика,

какими показателями мы интересуемся. Все они создают специальный файл имяПриложения. hp, который мы

можем преобразовать в график в формате PostScript с помощью программы hp2ps, она устанавливается

автоматически вместе с GHC.

Рассмотрим типичную утечку памяти (из упражнения к предыдущей главе):

module Main where

import System.Environment(getArgs)

main = print . sum2 . xs . read =<< fmap head getArgs

where xs n = [1 .. 10 ^ n]

sum2 :: [Int] -> (Int, Int)

sum2 = iter (0, 0)

where iter c

[]

= c

iter c

(x:xs) = iter (tick x c) xs

tick :: Int -> (Int, Int) -> (Int, Int)

tick x (c0, c1) | even x

= (c0, c1 + 1)

| otherwise = (c0 + 1, c1)

Скомпилируем с флагом профилирования:

$ ghc --make leak.hs -rtsopts -prof -auto-all

Статистика вычислителя показывает, что эта программа вызывала глубокую очистку 8 раз и выполняла

полезную работу лишь 40% времени.

$ ./leak 6 +RTS -K30m -sstderr

...

Tot time (elapsed)

Avg pause

Max pause

Gen

493 colls,

0 par

0.26s

0.0005s

0.0389s

Gen

8 colls,

0 par

0.14s

0.20s

0.0248s

0.0836s

...

Productivity

40.5% of total user, 35.6% of total elapsed

Теперь посмотрим на профиль кучи.

168 | Глава 10: Реализация Haskell в GHC

$ ./leak 6 +RTS -K30m -hc

(500000,500000)

$ hp2ps -e80mm -c leak.hp

В первой команде мы добавили флаг hc для того, чтобы создать файл с расширением . hp. Он содержит

таблицу с показателями размера кучи, которые вычислитель замеряет через равные промежутки времени. Мы

можем изменять интервал с помощью флага iN, где N – время в секундах. Второй командой мы преобразуем

профиль в картинку. Флаг c, говорит о том, что мы хотим получить цветную картинку, а флаг e80mm, говорит

о том, что мы собираемся вставить картинку в текст LaTeX. После e указан размер в миллиметрах. Мы видим

характерный горб (рис. 10.10).

leak 6 +RTS -K30m -hc

3,008,476 bytes x seconds

Fri Jun 1 21:17 2012

bytes

14M

12M

(103)tick/sum2.iter/sum2/m...

10M

(102)main.xs/main/Main.CAF

(101)sum2.iter/sum2/main/M...

0.0

0.1

0.2

seconds

Рис. 10.10: Профиль кучи для утечки памяти

В картинку не поместились имена функций мы можем увеличить строку флагом L. Теперь все имена

поместились (рис. 10.11).

$ ./leak 6 +RTS -K30m -hc -L45

(500000,500000)

$ hp2ps -e80mm -c leak.hp

С помощью флага hd посмотрим на объекты, которые застряли в куче (рис. 10.12):

$ ./leak 6 +RTS -K30m -hd -L45

(500000,500000)

$ hp2ps -e80mm -c leak.hp

Теперь куча разбита по типу объектов (замыканий) (рис. 10.12). BLACKHOLE это специальный объект, ко-

торый заменяет THUNK во время его вычисления. I# – это скрытый конструктор Int. sat_sUa и sat_sUd – это

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

бы запустили профилирование по функциям с флагом p и из файла leak. prof узнали бы в каких функциях

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

функций и после внесённых изменений снова посмотрели бы на графики кучи.

Если подумать, что мы делаем? Мы создаём отложенное вычисление, которое обещает построить большой

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

элементу пары, а если не чётным, то к другому. Проблема в том, что внутри пары происходит накопление

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

код:

{-# Language BangPatterns #-}

module Main where

import System.Environment(getArgs)

Статистика выполнения программы | 169

leak 6 +RTS -K30m -hc -L45

2,489,935 bytes x seconds

Fri Jun 1 23:11 2012

bytes

14M

12M

(103)tick/sum2.iter/sum2/main/Main.CAF

10M

(102)main.xs/main/Main.CAF

(101)sum2.iter/sum2/main/Main.CAF

0.0

0.1

0.2

seconds

Рис. 10.11: Профиль кучи для утечки памяти

leak 6 +RTS -K30m -hd -L45

3,016,901 bytes x seconds

Fri Jun 1 23:14 2012

bytes

14M

BLACKHOLE

12M

10M

0.0

0.1

0.2

seconds

Рис. 10.12: Профиль кучи для утечки памяти

main = print . sum2 . xs . read =<< fmap head getArgs

where xs n = [1 .. 10 ^ n]

sum2 :: [Int] -> (Int, Int)

sum2 = iter (0, 0)

where iter c

[]

= c

iter c

(x:xs) = iter (tick x c) xs

tick :: Int -> (Int, Int) -> (Int, Int)

tick x (! c0, ! c1) | even x

= (c0, c1 + 1)

| otherwise = (c0 + 1, c1)

Мы сделали функцию tick строгой. Теперь посмотрим на профиль:

$ ghc --make leak2.hs -rtsopts -prof -auto-all

$ ./leak2 6 +RTS -K30m -hc

(500000,500000)

170 | Глава 10: Реализация Haskell в GHC

$ hp2ps -e80mm -c leak2.hp

Не получилось (рис. 10.13). Как же так. Посмотрим на расход памяти отдельных функций. tick стала

строгой, но этого не достаточно, потому что в первом аргументе iter накапливаются вызовы tick. Сделаем

iter строгой по первому аргументу:

leak2 6 +RTS -K30m -hc

1,854,625 bytes x seconds

Fri Jun 1 21:38 2012

bytes

12M

10M

(102)main.xs/main/Main.CAF

(101)sum2.iter/sum2/main/M...

0.0

0.1

0.2

seconds

Рис. 10.13: Опять двойка

sum2 :: [Int] -> (Int, Int)

sum2 = iter (0, 0)

where iter ! c

[]

= c

iter ! c

(x:xs) = iter (tick x c) xs

Теперь снова посмотрим на профиль:

$ ghc --make leak2.hs -rtsopts -prof -auto-all

$ ./leak2 6 +RTS -K30m -hc

(500000,500000)

$ hp2ps -e80mm -c leak2.hp

Мы видим (рис. 10.14), что память резко подскакивает и остаётся постоянной. Но теперь показатели

измеряются не в мегабайтах, а в килобайтах. Мы справились. Остальные флаги hX позволяют наблюдать за

разными специфическими объектами в куче. Мы можем узнать сколько памяти приходится на разные модули

(hm), сколько памяти приходится на разные конструкторы (hd), на разные типы замыканий (hy).

Поиск источников внезапной остановки

case-выражения и декомпозиция в аргументах функции могут стать источником очень неприятных оши-

бок. Программа прошла проверку типов, завелась и вот уже работает-работает как вдруг мы видим на экране:

*** Exception: Prelude. head: empty list

или

*** Exception: Maybe. fromJust: Nothing

И совсем не понятно откуда эта ошибка. В каком модуле сидит эта функция. Может мы её импортировали

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

xc.

Посмотрим на выполнение такой программы:

Статистика выполнения программы | 171

leak2 6 +RTS -hc

5,944 bytes x seconds

Fri Jun 1 21:51 2012

bytes

30k

(51)PINNED

25k

20k

(72)GHC.IO.Encoding.CAF

15k

(59)GHC.IO.Handle.FD.CAF

10k

(58)GHC.Conc.Signal.CAF

0.0

0.1

0.2

seconds

Рис. 10.14: Профиль кучи без утечки памяти

module Main where

addEvens :: Int -> Int -> Int

addEvens a b

| even a && even b = a + b

q = zipWith addEvens [0, 2, 4, 6, 7, 8, 10] (repeat 0)

main = print q

Для того, чтобы воспользоваться флагом xc необходимо скомпилировать программу с возможностью про-

филирования:

$ ghc --make break.hs -rtsopts -prof

$ ./break +RTS -xc

*** Exception (reporting due to +RTS -xc): (THUNK_2_0), stack trace:

Main.CAF

break: break.hs:(4,1)-(5,30): Non-exhaustive patterns in function addEvens

Так мы узнали в каком месте кода проявился злосчастный вызов, это строки (4,1)-(5,30). Что соот-

ветствует определению функции addEvens. Не очень полезная информация. Мы и так бы это узнали. Нам

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

слились в один CAF для модуля. Так разделим их:

$ ghc --make break.hs -rtsopts -prof -caf-all -auto-all

$ ./break +RTS -xc

*** Exception (reporting due to +RTS -xc): (THUNK_2_0), stack trace:

Main.addEvens,

called from Main.q,

called from Main.CAF:q

--> evaluated by: Main.main,

called from :Main.CAF:main

break: break.hs:(4,1)-(5,30): Non-exhaustive patterns in function addEvens

Теперь мы видим путь к этому вызову, мы пришли в него из знчения q, которое было вызвано из main.

10.7 Оптимизация программ

В этом разделе мы поговорим о том этапе компиляции, на котором происходят преобразования Core ->

Core. Мы называли этот этап упрощением программы.

172 | Глава 10: Реализация Haskell в GHC

Флаги оптимизации

Мы можем задавать степень оптимизации программы специальными флагами. Самые простые флаги на-

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

Поэтому не стоит увлекаться оптимизацией на начальном этапе проектирования. Посмотрим какие возмож-

ности у нас есть:

• без -O – минимум оптимизаций, код компилируется как можно быстрее.

• -O0 – выключить оптимизацию полностью

• -O – умеренная оптимизация.

• O2 – активная оптимизация, код компилируется дольше, но пока O2 не сильно выигрывает у O по про-

дуктивности.

Для оптимизации мы компилируем программу с заданным флагом, например попробуйте скомпилиро-

вать самый первый пример с флагом O:

ghc --make sum.hs -O

и утечка памяти исчезнет.

Посмотреть описание конкретных шагов оптимизации можно в документации к GHC. Например при вклю-

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

памяти за нас. Стоит отметить оптимизацию -fexcess-precision, он может существенно ускорить програм-

мы, в которых много вычислений с Double. Но при этом вычисления могут потерять в точности, округление

становится непредсказуемым.

Прагма INLINE

Если мы посмотрим в исходный файл для модуля Prelude, то мы найдём такое определение для компо-

зиции функций:

-- | Function composition.

{-# INLINE (.) #-}

-- Make sure it has TWO args only on the left, so that it inlines

-- when applied to two functions, even if there is no final argument

(. )

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

(. ) f g = \x -> f (g x)

Помимо знакомого нам определения и комментариев мы видим новую прагму INLINE. Она указывает

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

часть. Этот процесс называют встраиванием функций. Замена будет произведена только в случае полного

применения функции, если синтаксическая арность (количество аргументов слева от знака равно) совпадает

с числом переданных в функцию аргументов. Поэтому для GHC есть существенная разница между определе-

ниями:

(. ) f g = \x -> f (g x)

(. ) f g x = f (g x)

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

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

встраивать, а когда – нет. По умолчанию GHC проводит встраивание только внутри модуля. Если мы компи-

лируем с флагом O, функции будут встраиваться между модулями. Для этого GHC сохраняет в интерфейсном

файле (с расширением . hi) не только типы функций, но и павые части достаточно кратких функций. Дли-

на функции определяется числом узлов в синтаксическом дереве кода её правой части. Директивой INLINE

мы приказываем GHC встроить функцию. Также есть более слабая версия этой прагмы –INELINABLE. Этой

прагмой мы рекомендуем произвести встраивание функции не смотря на её величину.

Задать порог величины функции для встраивания можно с помощью флага -funfolding-use-

threshold=16. Отметим, что если функция не является экспортируемой и используется лишь один раз,

то GHC втроит её в любом случае, поэтому стоит определять списки экспортируемых определений в шапке

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

Прагма INLINE может стоять в любом месте, где можно было бы объявить тип значения. Так например

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

Оптимизация программ | 173

instance Monad T where

{-# INLINE return #-}

return = ...

{-# INLINE (>>=) #-}

(>>=)

= ...

Встраивание значений может существенно ускорить программу. Но не стоит венчать каждую экспортиру-

емую функцию прагмой INLINE, возможно GHC встроит их автоматически. Посмотреть какие функции были

встроены можно по определениям, попавшим в файл . hi.

Например если мы скомпилируем такой код с флагом ddump-hi:

module Inline(f, g) where

g :: Int -> Int

g x = x + 2

f :: Int -> Int

f x = g $ g x

то среди прочих определений увидим:

ghc -c -ddump-hi -O Inline. hs

...

f :: GHC.Types.Int -> GHC.Types.Int

{- Arity: 1, HasNoCafRefs, Strictness: U(L)m,

Unfolding: InlineRule (1, True, False)

(\ x :: GHC.Types.Int ->

case x of wild { GHC.Types.I# x1 ->

GHC.Types.I# (GHC.Prim.+# (GHC.Prim.+# x1 2) 2) }) -}

...

В этом виде прочесть функцию не так просто. Ко всем именам добавлены имена модулей. Приведём

вывод к более простому виду с помощью флага dsuppress-all:

ghc -c -ddump-hi -dsuppress-all -O Inline. hs

...

f :: Int -> Int

{- Arity: 1, HasNoCafRefs, Strictness: U(L)m,

Unfolding: InlineRule (1, True, False)

(\ x :: Int -> case x of wild { I# x1 -> I# (+# (+# x1 2) 2) }) -}

...

Мы видим, что все вызовы функции g были заменены. Если вы всё же подозреваете, что GHC не справ-

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

INLINE, но при этом лучше узнать, привело ли это к росту производительности, проверить с помощью про-

филирования.

Отметим также прагму NOINLINE с её помощью мы можем запретить встраивание функции. Эта праг-

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

неконтролируемые побочные эффекты, может повлиять на её результат.

Прагма RULES

Разработчики GHC хотели, чтобы их компилятор был расширяемым и программист мог бы определять

специфические для его приложения правила оптимизации. Для этого была придумана прагма RULES. За счёт

чистоты функций мы можем в очень простом виде выражать инварианты программы. Инвариант – это неко-

торое свойство значения, которое остаётся постоянным при некоторых преобразованиях. Наиболее распро-

странённые инварианты имеют собственные имена. Например, это коммутативность сложения:

forall a b. a + b = b + a

Здесь мы пишем: для любых a и b изменение порядка следования аргументов у (+) не влияет на результат.

С ключевым словом forall мы уже когда-то встречались, когда говорили о типе ST. Помните тип функции

runST? Пример свойства функции map:

forall f g.

map f . map g = map (f . g)

174 | Глава 10: Реализация Haskell в GHC

Это свойство принято называть дистрибутивностью. Мы видим, что функция композиции дистрибутив-

на относительно функции map. Инварианты определяют скрытые закономерности значений. За счёт чистоты

функций мы можем безболезненно заменить в любом месте программы левую часть на правую или наобо-

рот. Оптимизация начинается тогда, когда мы понимаем, что одна из частей может быть вычислена гораздо

эффективнее другой. Так в примере с map выражение справа от знака равно гораздо эффективнее, поскольку

в нём мы не строим промежуточный список. Особенно ярко разница проявляется в энергичной стратегии

вычислений. Или посмотрим на такое совсем простое свойство:

map id = id

Если мы заменим левую часть на правую, то число сэкономленных усилий будет пропорционально длине

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

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

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

map f []

= []

map f (x:xs)

= f x : map f xs

map id a

= a

map f (map g x) = map (f . g) x

Словно теперь мы можем проводить сопоставление с образцом не только по конструкторам, но и по выра-

жениям самого языка и функция map стала конструктором. Что интересно, зависимости могут быть какими

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

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

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

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

Такие дополнительные правила пишутся в специальной прагме RULES:

{-# RULES

”map/compose”

forall f g x.

map f (map g x)

= map (f . g) x

”map/id”

map id

= id

#-}

Первым в кавычках идёт имя правила. Оно используется только для подсчёта статистики (например ес-

ли мы хотим узнать сколько правил сработало в данном прогоне программы). За именем правила пишут

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

переходом на другу строку. Все свободные переменные правила перечисляются в окружении forall (... )

. ~. Компилятор доверяет нам абсолютно. Производится только проверка типов. Никаких других проверок не

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

проще программы вычисления левой – известно только нам.

Отметим то, что прагма RULES применяется до тех пор пока есть возможность её применять, при этом мы

можем войти в бесконечный цикл:

{-# RULES

”infinite”

forall a b. f a b = f b a

#-}

С помощью прагмы RULES можно реализовать очень сложные схемы оптимизации. Так в Prelude реализу-

ется слияние (fusion) списков. За счёт этой оптимизации многие выражения вида свёртка/развёртка не будут

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

преобразуется серией функций map, filter и foldr промежуточные списки не строятся.

Посмотрим как работает прагма RULES, попробуем скомпилировать такой код:

module Main where

data List a = Nil | Cons a (List a)

deriving (Show)

foldrL :: (a -> b -> b) -> b -> List a -> b

foldrL cons nil x = case x of

Nil

-> nil

Cons a as

-> cons a (foldrL cons nil as)

Оптимизация программ | 175

mapL :: (a -> b) -> List a -> List b

mapL = undefined

{-# RULES

”mapL”

forall f xs.

mapL f xs = foldrL (Cons . f) Nil xs

#-}

main = print $ mapL (+100) $ Cons 1 $ Cons 2 $ Cons 3 Nil

Функция mapL не определена, вместо этого мы сделали косвенное определение в прагме RULES. Проверим,

для того чтобы RULES заработали, необходимо компилировать с одним из флагов оптимизаций O или O2:

$ ghc --make -O Rules.hs

$ ./Rules

Rules: Prelude.undefined

Что-то не так. Дело в том, что GHC слишком поторопился и заменил простую функцию mapL на её опре-

деление. Функция $ также очень короткая, если бы нам удалось задержать встраивание mapL, тогда $ превра-

тилось бы в обычное применение и наши правила сработали бы.

Фазы компиляции

Для решения этой проблемы в прагмы RULES и INLINE были введены ссылки на фазы компиляции. С по-

мощью них мы можем указать GHC в каком порядке реагировать на эти прагмы. Фазы пишутся в квадратных

скобках:

{-# INLINE [2] someFun #-}

{-# RULES

”fun” [0] forall ...

”fun” [1] forall ...

”fun” [~1] forall ...

#-}

Компиляция выполняется в несколько фаз. Фазы следуют некотрого заданного целого числа, например

трёх, до нуля. Мы можем сослаться на фазу двумя способами: просто номером и номером с тильдой. Ссылка

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

фаза, далее не применяй. Ссылка с тильдой говорит: подожди до наступления этой фазы. В нашем примере

мы задержим встраивание для mapL и foldrL так:

{-# INLINE [1] foldrL #-}

foldrL :: (a -> b -> b) -> b -> List a -> b

{-# INLINE [1] mapL #-}

mapL :: (a -> b) -> List a -> List b

Посмотреть какие правила сработали можно с помощью флага ddump-rule-firings. Теперь скомпилиру-

ем:

$ ghc --make -O Rules.hs -ddump-rule-firings

...

Rule fired: SPEC Main.$fShowList [GHC.Integer.Type.Integer]

Rule fired: mapL

Rule fired: Class op show

...

$ ./Rules

Cons 101 (Cons 102 (Cons 103 Nil))

Среди прочих правил, определённых в стандартных библиотеках, сработало и наше. Составим правила,

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

применение mapL на один mapL c композицией функций, также промежуточный список будет устранён в

связке foldrL/mapL.

176 | Глава 10: Реализация Haskell в GHC

Прагма UNPACK

Наш основной враг на этапе оптимизации программы это лишние объекты кучи. Чем меньше объектов

мы создаём на пути к результату, тем эффективнее наша программа. С помощью прагмы INLINE мы можем

избавиться от многих объектов, связанных с вызовом функции, это объекты типа FUN. Прагма UNPACK позволя-

ет нам бороться с лишними объектами типа CON. В прошлой главе мы говорили о том, что значения в Haskell

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

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

определённым значением (undefined). Такие значения называются запакованными (boxed). Незапакованное

значение, это примитивное значение, как оно представлено в памяти компьютера. Вспомним определение

целых чисел:

data Int = I# Int#

По традиции все незапакованные значения пишутся с решёткой на конце. Запакованные значения позво-

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

дится платить. Вспомним расход памяти в выражении [Pair 1 2]

nil = []

-- глобальный объект (не в счёт)

let x1

= I# 1

-- 2 слова

= I# 2

-- 2 слова

= Pair x1 x2

-- 3 слова

val = Cons p nil

-- 3 слова

val

------------

-- 10 слов

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

списка, который хранит такие пары будет зависеть от числа элементов N как 10 N. Тогда как полезная

нагрузка составляет 2 N. С помощью прагмы UNPACK мы можем отказаться от ленивой гибкости в пользу

меньшего расхода памяти. Эта прагма позволяет встраивать

один конструктор в поле другого. Это поле должно быть строгим (с пометкой ! ) и мономорфным (тип поля

должен быть конкретным типом, а не параметром), причём подчинённый тип должен содержать лишь один

конструктор (у него нет альтернатив):

data PairInt = PairInt

{-# UNPACK #-} !Int

Мы конкретизировали поля Pair и сделали их строгими с помощью восклицательных знаков. После этого

значения из конструктора Int будут храниться прямо в конструкторе PairInt:

nil = []

-- глобальный объект (не в счёт)

let p

= PairInt 1 2

-- 3 слова

val = Cons p nil

-- 3 слова

val

------------

-- 6 слов

Так мы сократим размер до 6 N. Но мы можем пойти ещё дальше. Если этот тип является ключевым

типом нашей программы и мы расчитываем на то, что в нём будет хранится много значений мы можем

создать специальный список для таких пар и распаковать значение списка:

data ListInt = ConsInt {-# UNPACK #-} !PairInt

| NilInt

nil = NilInt

let val = ConsInt 1 2 nil

-- 4 слова

val

-----------

-- 4 слова

Значение будет встроено дважды и получится, что у нашего нового конструктора Cons уже три поля.

Отметим, что эта прагма имеет смысл лишь при включённом флаге оптимизации -O или выше. Если мы

не включим этот флаг, то компилятор не будет проводить встраивание функций, поэтому при вычислении

функций вроде

Оптимизация программ | 177

sumPair :: PairInt -> Int

sumPair (Pair a b) = a + b

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

компилятор сначала запакует их в конструктор I# и затем применит функцию +, в которой опять распакует

их, сложит и затем, снова запаковав, вернёт результат.

Компилятор автоматически запаковывает все такие значения при передаче в ленивую функцию, это мо-

жет привести к снижению быстродействия даже при включённом флаге оптимизации, при недостаточном

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

оптимизация привела к повышению эффективности.

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

кортежи. Они пишутся с решётками:

newtype ST s a = ST (STRep s a)

type STRep s a = State# s -> (# State# s, a #)

Это определение типа ST. Специальные кортежи используются для возврата нескольких значений напря-

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

или на стеке. Для использования специальных значений необходимо активировать расширения MagicHash и

UnboxedTuples

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

версии и незапакованные. Например в ST-массив незапакованных значений STUArray s i a эквивалентен

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

10.8 Краткое содержание

Эта глава была посвящена компилятору GHC. Мы говорим Haskell подразумеваем GHC, говорим GHC

подразумеваем Haskell. К сожалению на данный момент у этого компилятора нет достойных конкурентов.

А может и к счастью, ведь если бы не было GHC, у нас была бы бурная конкуренция среди компиляторов

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

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

стракций приходится платить. Но есть GHC! Всё-таки это очень трудно: написать компилятор для ленивого

языка

Отметим другие компиляторы: Hugs разработан Марком Джонсом (написан на C), nhc98 основанный

Николасом Райомо (Niklas Röjemo) этот компилятор задумывался как легковесный и простой в установке, он

разрабатывался при поддержке NUTEK, Йоркского университета и Технического университета Чалмерса. От

этого компилятора отпочковался YHC, Йоркский компилятор. UHC – компилятор Утрехтского университета,

разработан для тестирования интересных идей в теории типов. JHC (Джон Мичэм, John Meacham) и LHC

(Дэвид Химмельступ и Остин Сипп, David Himmelstrup, Austin Seipp) компиляторы предназначенные для

проведения более сложных оптимизаций программ с помощью преобразований дерева программы.

В этой главе мы узнали как вычисляются программы в GHC. Мы узнали об этапах компиляции. Снача-

ла проводится синтаксический анализ программы и проверка типов, затем код Haskell переводится на язык

Core. Это сильно урезанная версия Haskell. После этого проводятся оптимизации, которые преобразуют де-

рево программы. На последнем этапе Core переводится на ещё более низкоуровневый, но всё ещё функцио-

нальный язык STG, который превращается в низкоуровневый код и исполняется вычислителем. Посмотреть

на текст вашей программы в Core и STG можно с помощью флагов ddump-simpl ddump-stg при этом лучше

воспользоваться флагом ddump-suppress-all для пропуска многочисленных деталей. Хардкорные разработ-

чики Haskell смотрят Core для того чтобы понять насколько строгой оказалась та или иная функция, как

аргументы размещаются в памяти. Но это уже высший пилотаж искусства оптимизации на Haskell.

Мы узнали о том как работает сборщик мусора и научились просматривать разные параметры работы

программы. У нас появилось несколько критериев оценки производительности программ: минимум глубоких

очисток и отсутствие горбов на графике изменения кучи. Мы потренировались в охоте за утечками памяти

и посмотрели как разные типы профилирования могут подсказать нам в каком месте затаилась ошибка.

Отметим, что не стоит в каждой медленной программе искать утечку памяти. Так в примере concat у нас не

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

узнали какой.

Также мы познакомились с новыми прагмами оптимизации программ. Это встраиваемые функции INLINE,

правила преобразования выражений RULE и встраиваемые конструкторы UNPACK. Разработчики GHC отмеча-

ют, что грамотное использование прагмы INLINE может существенно повысить скорость программы. Если

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

вычислений при её вызовах.

178 | Глава 10: Реализация Haskell в GHC

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

память, почему она висит в куче. При оптимизации программ предпочитайте изменение алгоритма перед

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

памяти под сборку мусора нам удалось вытянуть ленивую версию sum, но ведь строгая версия требовала в

100 раз меньше памяти, причём её запросы не зависели от величины списка. Если бы мы остановились на

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

аппетиты могли возрасти. И вдруг программа, так тщательно настроенная, взорвалась. За год мы, конечно,

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

включаем auto-all, caf-all с флагом prof и смотрим отчёт после флага p.

10.9 Упражнения

• Попытайтесь понять причину утечки памяти в примере с функцией sum2 на уровне STG. Не запоминайте

этот пример, вроде, ага, тут у нас копятся отложенные вычисления в аргументе. Переведите на STG и

посмотрите в каком месте происходит слишком много вызовов let-выражений. Переведите и пример

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

выразить энергичный образец через функцию seq.

Подсказка: За счёт семантики case-выражений нам не нужно специальных конструкций для того чтобы

реализовать seq в STG:

seq = FUN( a b ->

case a of

x -> b

)

При этом вызов функции seq будет встроен. Необходимо будет заменить в коде все вызовы seq на пра-

вую часть определения (без FUN). Также обратите внимание на то, что плюс не является примитивной

функцией:

plusInt = FUN( ma mb ->

case ma of

I# a -> case mb of

I# b -> case (primitivePlus a b) of

res -> I# res

)

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

то мы бы сразу вернули результат (I#(primitivePlus a b)), но мы пишем в STG и конструктор может

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

let-выражении:

-> let v = primitivePlus a b

I# v

Но это не правильное выражение в STG! Конструкция в правой части let-выражения должна быть объ-

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

выражение содержит вызов примитивной функции на незапакованных значениях. Эта операция выпол-

няется очень быстро. Было бы плохо создавать для неё специальный объект на куче. Поэтому мы сразу

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

все вызовы на определение.

• Набейте руку в профилировании, пусть это станет привычкой. Вы долго писали большую программу и

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

кода. Вернитесь к прошлой главе и попрофилируйте разные примеры. В конце главы мы рассматрива-

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

искали решение. Я говорил, что такие алгоритмы очень эффективны при ленивой стратегии вычис-

лений, но так ли это? Будьте критичны, не верьте на слово, ведь теперь у вас есть инструменты для

проверки моих туманных гипотез.

• Откройте документацию к GHC. Пролистайте её. Проникнитесь уважением к разработчикам GHC. Най-

дите исходники GHC и почитайте их. Посмотрите на Haskell-код, написанный профессионалами. Вы-

берите функцию наугад и попытайтесь понять как она строит свой результат.

Упражнения | 179

• Откройте документацию вновь. Нас интересует глава Profiling. Найдите в разделе профилирование

кучи как выполняется retainer profiling. Это специальный тип профилирования направленный на по-

иск данных, которые удерживают в памяти другие данные (типичный сценарий для утечек памяти).

Разберитесь с этим типом профилирования (флаг hr).

• Постройте систему правил, которая выполняет слияние для списков List, определённых в примере для

прагмы RULES. Сравните показатели производительности с правилами и без (для этого скомпилируйте

дважды с флагом O и без) на тестовом выражении:

main = print $ sumL $

mapL (\x -> x - 1000) $ mapL (+100) $ mapL (*2) $ genL 0 1e6

Функция sumL находит сумму элементов в списке, функция genL генерирует список чисел с единичным

шагом от первого аргумента до второго.

Подсказка: вам нужно воспользоваться такими свойствами (не забудьте о фазах компиляции)

mapL f (mapL g xs)

= ...

foldrL cons nil (mapL f xs)

= ...

• Откройте исходный код Prelude и присмотритесь к различным прагмам. Попытайтесь понять почему

они там используются.

180 | Глава 10: Реализация Haskell в GHC

Глава 11

Ленивые чудеса

В прошлой главе мы узнали, что такое ленивые вычисления. В этой главе мы посмотрим чем они хо-

роши. С ними можно делать невозможные вещи. Обращаться к ещё не вычисленным значениям, работать с

бесконечными данными.

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

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

задачи по-меньше, потом собираем из них решения, из этих решений собираем другие решения и вот уже

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

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

можем разбить программу на независимые подзадачи, если в том языке на котором мы собираемся объяснять

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

Об этом говорит Джон Хьюз (John Huges) в статье “Why functional programming matters”. Он приводит та-

кую метафору. Если мы делаем стул и у нас нет хорошего клея. Единственное что нам остаётся это вырезать

из дерева стул целиком. Это невероятно трудная задача. Гораздо проще сделать отдельные части и потом

собрать вместе. Функциональные языки программирования предоставляют два новых вида “клея”. Это функ-

ции высшего порядка и ленивые вычисления. В статье можно найти много примеров. Некоторые из них мы

рассмотрим в этой главе.

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

помощью мы можем параметризовать функцию другой функцией (поведением). Они дают нам возможность

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

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

выполнять это вручную.

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

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

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

букет решений, там где искали одно.

11.1 Численные методы

Рассмотрим несколько численных методов. Все эти методы построены на понятии сходимости. У нас есть

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

что промежуточные решения будут всё ближе и ближе к итоговому.

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

Так же как мы делали это в прошлой главе, когда искали корни уравнения методом неподвижной точки. Эти

примеры взяты из статьи “Why functional programming matters” Джона Хьюза.

Дифференцирование

Найдём производную функции в точке. Посмотрим на математическое определение производной:

f ( x + h) − f ( x)

f ( x) = lim

h→ 0

Производная это предел последовательности таких отношений, при h стремящемся к нулю. Если предел

сходится, то производная определена. Для того чтобы решить эту задачу мы начнём с небольшого значе-

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

перестанут сильно изменяться мы будем считать, что мы нашли предел последовательности

Этот процесс напоминает то, что мы делали при поиске корня уравнения методом неподвижной точки.

Мы можем взять из того решения функцию определения сходимости последовательности:

| 181

converge :: (Ord a, Num a) => a -> [a] -> a

converge eps (a:b:xs)

| abs (a - b) <= eps

= a

| otherwise

= converge eps (b:xs)

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

вычисляет промежуточные решения:

easydiff :: Fractional a => (a -> a) -> a -> a -> a

easydiff f x h = (f (x + h) - f x) / h

Мы возьмём начальное значение шага и будем последовательно уменьшать его вдвое:

halves = iterate (/2)

Соберём все части вместе:

diff :: (Ord a, Fractional a) => a -> a -> (a -> a) -> a -> a

diff h0 eps f x = converge eps $ map (easydiff f x) $ iterate (/2) h0

where easydiff f x h = (f (x + h) - f x) / h

Сохраним эти определения в отдельном модуле и найдём производную какой-нибудь функции. Проте-

стируем решение на экспоненте. Известно, что производная экспоненты равна самой себе:

*Numeric> let exp’ = diff 1 1e-5 exp

*Numeric> let test x = abs $ exp x - exp’ x

*Numeric> test 2

1.4093421286887065e-5

*Numeric> test 5

1.767240203776055e-5

Интегрирование

Теперь давайте поинтегрируем функции одного аргумента. Интеграл это площадь кривой под графиком

функции. Если бы кривая была прямой, то мы могли бы вычислить интеграл по формуле трапеций:

easyintegrate :: Fractional a => (a -> a) -> a -> a -> a

easyintegrate f a b = (f a + f b) * (b - a) / 2

Но мы хотим интегрировать не только прямые линии. Мы представим, что функция является ломаной

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

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

значение интеграла.

Проблема в том, что мы не знаем заранее насколько близки должны быть точки друг к другу. Это зависит

от функции, которую мы хотим проинтегрировать. Но мы можем построить последовательность решений.

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

расти вдвое. Как только решение перестанет меняться мы вернём ответ.

Построим последовательность решений:

integrate :: Fractional a => (a -> a) -> a -> a -> [a]

integrate f a b = easyintegrate f a b :

zipWith (+) (integrate a mid) (integrate mid b)

where mid = (a + b)/2

Первое решение является площадью под прямой, которая соединяет концы отрезка. Потом мы делим от-

резок пополам, строим последовательность приближений и складываем частичные суммы с помощью функ-

ции zipWith.

Эта версия функции хоть и наглядная, но не эффективная. Функция f вычисляется заново при каждом ре-

курсивном вызове. Было бы хорошо вычислять её только для новых значений. Для этого мы будем передавать

значения с предыдущего шага:

integrate :: Fractional a => (a -> a) -> a -> a -> [a]

integrate f a b = integ f a b (f a) (f b)

where integ f a b fa fb = (fa+fb)*(b-a)/2 :

zipWith (+) (integ f a m fa fm)

(integ f m b fm fb)

where m

= (a + b)/2

fm = f m

182 | Глава 11: Ленивые чудеса

В этой версии мы вычисляем значения в функции f лишь один раз для каждой точки. Запишем итоговое

решение:

int :: (Ord a, Fractional a) => a -> (a -> a) -> a -> a -> a

int eps f a b = converge eps $ integrate f a b

Мы опять воспользовались функцией converge, нам не нужно было её переписывать. Проверим решение.

Для проверки также воспользуемся экспонентой. В прошлой главе мы узнали, что

∫ x

ex = 1 +

etdt

Посмотрим, так ли это для нашего алгоритма:

*Numeric> let exp’ = int 1e-5 exp 0

*Numeric> let test x = abs $ exp x - 1 -

exp’ x

*Numeric> test 2

8.124102876649886e-6

*Numeric> test 5

4.576306736225888e-6

*Numeric> test 10

1.0683757864171639e-5

Алгоритм работает. В статье ещё рассмотрены методы повышения точности этих алгоритмов. Что инте-

ресно для улучшения точности не надо менять существующий код. Функция принимает последовательность

промежуточных решений и преобразует её.

11.2 Степенные ряды

Напишем модуль для вычисления степенных рядов. Этот пример взят из статьи Дугласа МакИлроя

(Douglas McIlroy) “Power Series, Power Serious”. Степенной ряд представляет собой функцию, которая опре-

деляется списком коэффициентов:

F ( x) = f 0 + f 1 x + f 2 x 2 + f 3 x 3 + f 4 x 4 + ...

Степенной ряд содержит бесконечное число слагаемых. Для вычисления нам потребуются функции сло-

жения и умножения. Ряд F ( x) можно записать и по-другому:

F ( x) = F 0( x)

= f 0 + xF 1( x)

= f 0 + x( f 1 + xF 2( x))

Это определение очень похоже на определение списка. Ряд есть коэффициент f 0 и другой ряд F 1( x)

умноженный на x. Поэтому для представления рядов мы выберем конструкцию похожую на список:

data Ps a = a :+: Ps a

deriving (Show, Eq)

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

просто f + xF 1, без скобок для аргумента.

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

p0 :: Num a => a -> Ps a

p0 x = x :+: p0 0

ps :: Num a => [a] -> Ps a

ps []

= p0 0

ps (a:as) = a :+: ps as

Обратите внимание на то, как мы дописываем бесконечный хвост нулей в конец ряда. Теперь давайте

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

eval :: Num a => Int -> Ps a -> a -> a

eval 0 _

_ = 0

eval n (a :+: p) x = a + x * eval (n-1) p x

В первом случае мы хотим вычислить ноль степеней ряда, поэтому мы возвращаем ноль, а во втором

случае значение ряда a+ xP складывается из числа a и значения ряда P умноженного на заданное значение.

Степенные ряды | 183

Арифметика рядов

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

Эти операции говорят о том, что мы можем сделать степенной ряд экземпляром класса Num.

Сложение

Рекурсивное представление ряда f + xF позволяет нам очень кратко выражать операции, которые мы

хотим определить. Теперь у нас нет бесконечного набора коэффициентов, у нас всего лишь одно число и ещё

один ряд. Операции существенно упрощаются. Так сложение двух бесконечных рядов имеет вид:

F + G = ( f + xF 1) + ( g + xG 1) = ( f + g) + x( F 1 + G 1)

Переведём на Haskell:

(f :+: fs) + (g :+: gs) = (f + g) :+: (fs + gs)

Умножение

Умножим два ряда:

F ∗ G = ( f + xF 1) ∗ ( g + xG 1) = f g + x( f G 1 + F 1 ∗ G)

Переведём:

(.*) :: Num a => a -> Ps a -> Ps a

k .* (f :+: fs) = (k * f) :+: (k .* fs)

(f :+: fs) * (g :+: gs) = (f * g) :+: (f .* gs + fs * (g :+: gs))

Дополнительная операция (.*) выполняет умножение всех коэффициентов ряда на число.

Класс Num

Соберём определения для методов класса Num вместе:

instance Num a => Num (Ps a) where

(f :+: fs) + (g :+: gs) = (f + g) :+: (fs + gs)

(f :+: fs) * (g :+: gs) = (f * g) :+: (f .* gs + fs * (g :+: gs))

negate (f :+: fs) = negate f :+: negate fs

fromInteger n = p0 (fromInteger n)

(.*) :: Num a => a -> Ps a -> Ps a

k .* (f :+: fs) = (k * f) :+: (k .* fs)

Методы abs и signum не определены для рядов. Обратите внимание на то, как рекурсивное определение

рядов приводит к рекурсивным определениям функций для рядов. Этот приём очень характерен для Haskell.

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

мы определяем, на “хвостовом” ряде.

Деление

Результат деления Q удовлетворяет соотношению:

F = Q ∗ G

Переписав F , G и Q в нашем представлении, получим

f + xF 1 = ( q + xQ 1) ∗ G = qG + xQ 1 ∗ G = q( g + xG 1) + xQ 1 ∗ G

= qg + x( qG 1 + Q 1 ∗ G)

Следовательно

= f / g

Q 1 = ( F 1 − qG 1)/ G

Если g = 0 деление имеет смысл только в том случае, если и f = 0. Переведём на Haskell:

184 | Глава 11: Ленивые чудеса

class Fractional a => Fractional (Ps a) where

(0 :+: fs) / (0 :+: gs) = fs / gs

(f :+: fs) / (g :+: gs) = q :+: ((fs - q .* gs)/(g :+: gs))

where q = f/g

fromRational x = p0 (fromRational x)

Производная и интеграл

Производная одного члена ряда вычисляется так:

d xn = nxn− 1

Из этого выражения по свойствам производной

( f ( x) + g( x)) =

f ( x) +

g( x)

d ( k ∗ f( x)) = k ∗ d f( x)

мы можем получить формулу для всего ряда:

d F( x) = f 1 + 2 f 2 x + 3 f 3 x 2 + 4 f 4 x 3 + ...

Для реализации нам понадобится вспомогательная функция, которая будет обновлять значение допол-

нительного множителя n в выражении nxn− 1:

diff :: Num a => Ps a -> Ps a

diff (f :+: fs) = diff’ 1 fs

where diff’ n (g :+: gs) = (n * g) :+: (diff’ (n+1) gs)

Также мы можем вычислить и интеграл степенного ряда:

int :: Fractional a => Ps a -> Ps a

int (f :+: fs) = 0 :+: (int’ 1 fs)

where int’ n (g :+: gs) = (g / n) :+: (int’ (n+1) gs)

Элементарные функции

Мы можем выразить элементарные функции через операции взятия производной и интегрирования. К

примеру уравнение для ex выглядит так:

dy = y

Проинтегрируем с начальным условием y(0) = 1:

∫ x

y( x) = 1 +

y( t) dt

Теперь переведём на Haskell:

expx = 1 + int expx

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

для синуса и косинуса:

d sin x = cos x,

sin(0) = 0 ,

d cos x = − sin x, cos(0) = 1

Что приводит нас к:

sinx = int cosx

cosx = 1 - int sinx

И это работает! Вычисление этих функций возможно за счёт того, что вне зависимости от аргумента

функция int вернёт ряд, у которого первый коэффициент равен нулю. Это значение подхватывается и ис-

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

Через синус и косинус мы можем определить тангенс:

tanx = sinx / cosx

Степенные ряды | 185

11.3 Водосборы

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

мемоизацией (memoization). Она заключается в том, что мы запоминаем все значения, с которыми вызывалась

функция и, если с данным значением функция уже вычислялась, просто используем значение из памяти, а

если значение ещё не вычислялось, вычисляем его и сохраняем.

В ленивых языках программирования для мемоизации функций часто используется такой приём. Мы со-

храняем все значения функции в некотором контейнере, а затем обращаемся к элементам. При этом значения

сохраняются в контейнере и не перевычисляются. Это происходит за счёт ленивых вычислений. Что интерес-

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

контейнера хотя бы один раз.

Посмотрим на такой классический пример. Вычисление чисел Фибоначчи. Каждое последующее число

ряда Фибоначчи равно сумме двух предыдущих. Наивное определение выглядит так:

fib :: Int -> Int

fib 0 = 0

fib 1 = 1

fib n = fib (n-1) + fib (n-2)

В этом определении число вычислений растёт экспоненциально. Для того чтобы вычислить fib n нам

нужно вычислить fib (n-1) и fib (n-2), для того чтобы вычислить каждое из них нам нужно вычислить

ещё два числа, и так вычисления удваиваются на каждом шаге. Если мы вызовем в интерпретаторе fib 40,

то вычислитель зависнет. Что интересно в этой функции вычисления пересекаются, они могут быть пере-

использованы. Например для вычисления fib (n-1) и fib (n-2) нужно вычислить fib (n-2) (снова), fib

(n-3), fib (n-3) (снова) и fib (n-4).

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

раз:

fib’ :: Int -> Int

fib’ n = fibs !! n

where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Попробуем вычислить для 40:

*Fib> fib’ 40

102334155

*Fib> fib’ 4040

700852629

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

и для вычисления последующих подзадач используются решения из предыдущих, стоит задуматься об ис-

пользовании мемоизации. Такие задачи называются задачами динамического программирования. Вычисление

чисел Фибоначчи яркий пример задачи динамического программирования.

Рассмотрим такую задачу. Дана прямоугольная “карта местности”, в каждой клетке целым числом ука-

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

• Из каждой клетки карты вода стекает не более чем в одном из четырёх возможных направлений (“се-

вер”, “юг”, “запад”, “восток”).

• Если у клетки нет ни одного соседа с высотой меньше её собственной высоты, то эта клетка – водосток,

и вода из неё никуда дальше не течёт.

• Иначе вода из текущей клетки стекает на соседнюю клетку с минимальной высотой.

• Если таких соседей несколько, то вода стекает по первому из возможных направлений из списка “на

север”, “на запад”, “на восток”, “на юг”.

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

ра. Необходимо отметить на карте все бассейны. Решение этой задачи встретилось мне в статье Дмитрия

Астапова “Рекурсия+мемоизация = динамическое программирование”. Здесь оно и приводится с незначи-

тельными изменениями.

Карта местности представлена в виде двумерного массива, в каждой клетке которого отмечена высота

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

водостоков. Мы будем отмечать их буквами латинского алфавита в том порядке, в котором они встречаются

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

186 | Глава 11: Ленивые чудеса

1 2 3 4 5 6

a a a b b b

7 8 9 2 4 5

a a b b b b

3 5 3 3 6 7

c c d b b e

6 4 5 5 3 1

f g d b e e

2 2 4 5 3 7

f g g h h e

Для представления двумерного массива мы воспользуемся типом Array из стандартного модуля

Data.Array. Тип Array имеет два параметра:

data Array i a

Первый указывает на индекс, а второй на содержание. Массивы уже встречались нам в главе о типе ST.

Напомню, что подразумевается, что этот тип является экземпляром класса Ix, который описывает целочис-

ленные индексы, вспомним его определение:

class Ord a => Ix a where

range

:: (a, a) -> [a]

index

:: (a, a) -> a -> Int

inRange

:: (a, a) -> a -> Bool

rangeSize

:: (a, a) -> Int

Первый аргумент у всех этих функций это пара, которая представляет верхнюю и нижнюю грань после-

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

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

import Data.Array

type Coord = (Int, Int)

type HeightMap = Array Coord Int

type SinkMap

= Array Coord Coord

Значение типа HeightMap хранит карту высот, значение типа SinkMap хранит в каждой координате, ту

точку, которая является водостоком для данной точки. Нам необходимо построить функцию:

flow :: HeightMap -> SinkMap

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

данной. Для каждой точки мы можем узнать в какую сторону из неё стекает вода. При этом водосток для

следующей точки такой же как и для текущей. Если же из данной точки вода никуда не течёт, то она сама

является водостоком. Мы определим эту функцию через комбинатор неподвижной точки fix.:

flow :: HeightMap -> SinkMap

flow arr = fix $ \result -> listArray (bounds arr) $

map (\x -> maybe x (result ! ) $ getSink arr x) $

range $ bounds arr

getSink :: HeightMap -> Coord -> Maybe Coord

Мы ищем решение в виде неподвижной точки функции, которая принимает карту стоков и возвращает

карту стоков. Функция getSink по данной точке на карте вычисляет соседнюю точку, в которую стекает вода.

Эта функция частично определена, поскольку для водостоков нет такой соседней точки, в которую бы утекала

вода. Функция listArray конструирует значение типа Array из списка значений. Первым аргументом она

принимает диапазон значений для индексов. Размеры массива совпадают с размерами карты высот, поэтому

первым аргументом мы передаём bounds arr.

Теперь разберёмся с тем как заполняются значения в список. Сначала мы создаём список координат

исходной карты высот с помощью выражения:

range $ bounds arr

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

в лямбда-функции:

\x -> maybe x (result ! ) $ getSink arr x

Водосборы | 187

Мы принимаем текущую координату и с помощью функции getSink находим соседнюю точку, в которую

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

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

Мы обратимся к результату (result ! ), посмотрим каким окажется водосток для соседней точки и вернём

это значение. Поскольку за счёт ленивых вычислений значения результирующего массива вычисляются лишь

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

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

Осталось только определить функцию поиска ближайшего стока и функцию разметки.

getSink :: HeightMap -> Coord -> Maybe Coord

getSink arr (x, y)

| null sinks = Nothing

| otherwise

= Just $ snd $ minimum $ map (\i -> (arr! i, i)) sinks

where sinks = filter p [(x+1, y), (x-1, y), (x, y-1), (x, y+1)]

p i

= inRange (bounds arr) i && arr ! i < arr ! (x, y)

В функции разметки мы воспользуемся ассоциативным массивом из модуля Data.Map. Функция nub из

модуля Data.List убирает из списка повторяющиеся элементы. Затем мы составляем список пар из коорди-

нат водостоков и меток и в самом конце размечаем исходный массив:

label :: SinkMap -> LabelMap

label a = fmap (m M.! ) a

where m = M. fromList $ flip zip [’a’ .. ] $ nub $ elems a

11.4 Ленивее некуда

Мы выяснили, что значение может редуцироваться только при сопоставлении с образцом и в специальной

функции seq. Функцию seq мы можем применять, а можем и не применять. Но кажется, что в декомпозиции

мы не можем уйти от необходимости проведения хотя бы одной редукции. Оказывается можем, в Haskell для

этого предусмотрены специальные ленивые образцы (lazy patterns). Они обозначаются знаком тильда:

lazyHead :: [a] -> a

lazyHead ~(x:xs) = x

Перед скобками сопоставления с образцом пишется символ тильда. Этим мы говорим вычислителю: до-

верься мне, здесь точно такой образец, можешь даже не проверять дальше. Он и правда дальше не пойдёт.

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

lazySafeHead :: [a] -> Maybe a

lazySafeHead ~(x:xs) = Just x

lazySafeHead []

= Nothing

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

доверился нам в первом уравнении, а мы его обманули. Сохраним в модуле Strict и проверим:

Prelude Strict> :! ghc --make Strict

[1 of 1] Compiling Strict

( Strict. hs, Strict. o )

Strict. hs:67:0:

Warning: Pattern match(es) are overlapped

In the definition of ‘lazySafeHead’: lazySafeHead [] = ...

Prelude Strict> :l Strict

Ok, modules loaded: Strict.

Prelude Strict> lazySafeHead [1,2,3]

Just 1

Prelude Strict> lazySafeHead []

Just *** Exception: Strict. hs:(67,0)-(68,29): Irrefutable

pattern failed for pattern (x : xs)

При компиляции нам даже сообщили о том, что образцы в декомпозиции пересекаются. Но мы были

упрямы и напоролись на ошибку, если мы поменяем образцы местами, то всё пройдёт гладко:

Prelude Strict> :! ghc --make Strict

[1 of 1] Compiling Strict

( Strict. hs, Strict. o )

Prelude Strict> :l Strict

Ok, modules loaded: Strict.

Prelude Strict> lazySafeHead []

Nothing

188 | Глава 11: Ленивые чудеса

Отметим, что сопоставление с образцом в let и where выражениях является ленивым. Функцию lazyHead

мы могли бы написать и так:

lazyHead a = x

where (x:xs) = a

lazyHead a =

let (x:xs) = a

Посмотрим как используются ленивые образцы при построении потоков, или бесконечных списков. Мы

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

ставлять непрерывные функции дискретными сигналами. Считаем, что шаг дискретизации (или шаг между

соседними точками) нам известен.

f : R → R ⇒ fn = f ( nτ ) ,

n = 0 , 1 , 2 , ...

Где τ – шаг дискретизации, а n пробегает все натуральные числа. Определим функцию решения диффе-

ренциальных уравнений вида:

dx = f( t)

x(0) = ˆ

Символ ˆ x означает начальное значение функции x. Перейдём к дискретным сигналам:

xn−xn− 1 = f

x 0 = ˆ

Где τ – шаг дискретизации, а x и f – это потоки чисел, индекс n пробегает от нуля до бесконечности

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

ных уравнений называют методом Эйлера. Теперь мы можем выразить следующий элемент сигнала через

предыдущий.

xn = xn− 1 + τ fn, x 0 = ˆ

Закодируем это уравнение:

-- шаг дискретизации

dt :: Fractional a => a

dt = 1e-3

-- метод Эйлера

int :: Fractional a => a -> [a] -> [a]

int x0 (f:fs) = x0 : int (x0 + dt * f) fs

Смотрите в функции int мы принимаем начальное значение x0 и поток всех значений функции пра-

вой части уравнения, поток значений функции f( t). Мы помещаем начальное значение в первый элемент

результата, а остальные значения получаем рекурсивно.

Определим две вспомогательные функции:

time :: Fractional a => [a]

time = [0, dt .. ]

dist :: Fractional a => Int -> [a] -> [a] -> a

dist n a b = ( / fromIntegral n) $

foldl’ (+) 0 $ take n $ map abs $ zipWith (-) a b

Функция time пробегает все значения отсчётов шага дискретизации по времени. Это тождественная функ-

ция представленная в виде потока с шагом dt.

Функция проверки результата dist принимает два потока и по ним считает расстояние между ними. Эта

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

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

число точек.

Также импортируем для удобства символьный синоним для fmap из модуля Control.Applicative.

Ленивее некуда | 189

import Control.Applicative((<$> ))

...

Проверим функцию int. Для этого сохраним все новые функции в модуле Stream. hs. Загрузим модуль

в интерпретатор и вычислим производную какой-нибудь функции. Найдём решение для правой части кон-

станты и проверим, что у нас получилась тождественная функция:

*Stream> dist 1000 time $ int 0 $ repeat 1

7.37188088351104e-17

Функции практически совпадают, порядок ошибки составляет 10 − 16. Так и должно быть для линейных

функций. Посмотрим, что будет если в правой части уравнения стоит тождественная функция:

*Stream> dist 1000 ((\t -> t^2/2) <$> time) $ int 0 time

2.497500000001403e-4

Решение этого уравнения равно функции t 2 . Здесь мы видим, что результаты уже не такие хорошие.

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

экспонента будет решением такого уравнения:

dx = x

∫ t

x( t) = x(0) +

x( τ ) dτ

Опишем это уравнение в Haskell:

e = int 1 e

Наше описание копирует исходное математическое определение. Добавим это уравнение в модуль Stream

и проверим результаты:

*Stream> dist 1000 (map exp time) e

^CInterrupted.

К сожалению вычисление зависло. Нажмём ctrl+c и разберёмся почему. Для этого распишем вычисление

потока чисел e:

-- раскроем e

int 1 e

-- раскроем int, во втором варгументе

-- int стоит декомпозиция,

int 1 e@(f:fs)

-- для того чтобы узнать какое уравнение

-- для int выбрать нам нужно раскрыть

-- второй аргумент, узнать корневой

-- конструктор, раскроем второй аргумент:

int 1 (int 1 e)

int 1 (int 1e@(f:fs))

-- такая же ситуация

int 1 (int 1 (int 1 e))

Проблема в том, что первый элемент решения мы знаем, мы передаём его первым аргументом и присо-

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

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

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

следующего элемента.

C помощью ленивых образцов мы можем отложить декомпозицию второго аргумента на потом:

int :: Fractional a => a -> [a] -> [a]

int x0 ~(f:fs) = x0 : int (x0 + dt * f) fs

Теперь мы видим:

*Stream> dist 1000 (map exp time) e

4.988984990735441e-4

190 | Глава 11: Ленивые чудеса

Вычисления происходят. С помощью взаимно-рекурсивных функций мы можем определить функции си-

нус и косинус:

sinx = int 0 cosx

cosx = int 1 (negate <$> sinx)

Эти функции описывают точку, которая бегает по окружности. Вот математическое определение:

−x

x(0)

y(0)

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

*Stream> dist 1000 (sin <$> time) sinx

1.5027460329809257e-4

*Stream> dist 1000 (cos <$> time) cosx

1.9088156807382827e-4

Так с помощью ленивых образцов нам удалось попасть в правую часть уравнения для функции int, не рас-

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

на значение, которое ещё не было вычислено.

11.5 Краткое содержание

Ленивые вычисления повышают модульность программ. Мы можем в одной части программы создать все

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

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

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

вычислениях. Мы узнали новую синтаксическую конструкцию. Оказывается мы можем не только бороться с

ленью, но и поощрять её. Лень поощряется ленивыми образцами. Они отменяют приведение к слабой заголо-

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

тильда:

lazyHead ~(x:xs) = x

Мы говорим вычислителю: поверь мне, это значение может иметь только такой вид, потом посмотришь

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

в любом случае.

Сопоставление с образцом в let и where выражениях является ленивым. Функцию lazyHead мы могли бы

написать и так:

lazyHead a = x

where (x:xs) = a

lazyHead a =

let (x:xs) = a

11.6 Упражнения

Мы побывали на выставке ленивых программ. Присмотритесь ещё раз к решениям задач этой главы и

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

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

числения по значению. Критически настроенные читатели могут с помощью профилирования проверить

эффективность программ из этой главы.

Краткое содержание | 191

Глава 12

Структурная рекурсия

Структурная рекурсия определяет способ построения и преобразования значений по виду типа (по со-

ставу его конструкторов). Функции, которые преобразуют значения мы будем называть свёрткой (fold), а

функции которые строят значения – развёрткой (unfold). Эта рекурсия встречается очень часто, мы уже поль-

зовались ею и не раз, но в этой главе мы остановимся на ней поподробнее.

12.1 Свёртка

Свёртку значения можно представить как процесс, который заменяет в дереве значения все конструкторы

на подходящие по типу функции.

Логические значения

Вспомним определение логических значений:

data Bool = True | False

У нас есть два конструктора-константы. Любое значение типа Bool может состоять либо из одного кон-

структора True, либо из одного конструктора False. Функция свёртки в данном случае принимает две кон-

станты одинакового типа a и возвращает функцию, которая превращает значение типа Bool в значение

типа a, заменяя конструкторы на переданные значения:

foldBool :: a -> a -> Bool -> a

foldBool true false = \b -> case b of

True

-> true

False

-> false

Мы написали эту функцию в композиционном стиле для того, чтобы подчеркнуть, что функция преобра-

зует значение типа Bool. Определим несколько знакомых функций через функцию свёртки, начнём с отри-

цания:

not :: Bool -> Bool

not = foldNat False True

Мы поменяли конструкторы местами, если на вход поступит True, то мы вернём False и наоборот. Теперь

посмотрим на “и” и “или”:

(||), (&& ) :: Bool -> Bool -> Bool

(||) = foldNat

(const True)

(&& ) = foldNat

(const False)

Определение функций “и” и “или” через свёртки подчёркивает, что они являются взаимно обратными.

Смотрите, эти функции принимают значение типа Bool и возвращают функцию Bool -> Bool. Фактически

функция свёртки для Bool является if-выражением, только в этот раз мы пишем условие в конце.

192 | Глава 12: Структурная рекурсия

Натуральные числа

У нас был тип для натуральных чисел Пеано:

data Nat = Zero | Succ Nat

Помните мы когда-то записывали определения типов в стиле классов:

data Nat where

Zero :: Nat

Succ :: Nat -> Nat

Если мы заменим конструктор Zero на значение типа a, то конструктор Succ нам придётся заменять на

функцию типа a -> a, иначе мы не пройдём проверку типов. Представим, что Nat это класс:

data Nat a where

zero :: a

succ :: a -> a

Из этого определения следует функция свёртки:

foldNat :: a -> (a -> a) -> (Nat -> a)

foldNat zero succ = \n -> case n of

Zero

-> zero

Succ m

-> succ (foldNat zero succ m)

Обратите внимание на рекурсивный вызов функции foldNat мы обходим всё дерево значения, заменяя

каждый конструктор. Определим знакомые функции через свёртку:

isZero :: Nat -> Bool

isZero = foldNat True (const False)

Посмотрим как вычисляется эта функция:

isZero Zero

True

-- заменили конструктор Zero

isZero (Succ (Succ (Succ Zero)))

const False (const False (const False True))

-- заменили и Zero и Succ

False

Что интересно за счёт ленивых вычислений на самом деле во втором выражении произойдёт лишь одна

замена. Мы не обходим всё дерево, нам это и не нужно, а смотрим лишь на первый конструктор, если там

Succ, то произойдёт замена на постоянную функцию, которая игнорирует свой второй аргумент и рекурсив-

ного вызова функции свёртки не произойдёт, совсем как в исходном определении!

even, odd :: Nat -> Bool

even

= foldNat True

not

odd

= foldNat False not

Эти функции определяют чётность числа, сдесь мы пользуемся тем свойством, что not (not a) == a.

Определим сложение и умножение:

add, mul :: Nat -> Nat -> Nat

add a

= foldNat a

Succ

mul a

= foldNat Zero

(add a)

Свёртка | 193

Maybe

Вспомним определение типа для результата частично определённых функций:

data Maybe a = Nothing | Just a

Перепишем словно это класс:

data Maybe a b where

Nothing :: b

Just

:: a -> b

Этот класс принимает два параметра, поскольку исходный тип Maybe принимает один. Теперь несложно

догадаться как будет выглядеть функция свёртки, мы просто получим стандартную функцию maybe. Дадим

определение экземпляра функтора и монады через свёртку:

instance Functor Maybe where

fmap f = maybe Nothing (Just . f)

instance Monad Maybe where

return

= Just

ma >>= mf

= maybe Nothing mf ma

Списки

Функция свёртки для списков это функция foldr. Выведем её из определения типа:

data [a] = a : [a] | []

Представим, что это класс:

class [a] b where

cons

:: a -> b -> b

nil

:: b

Теперь получить определение для foldr совсем просто:

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

foldr cons nil = \x -> case x of

a:as

-> a ‘cons‘ foldr cons nil as

[]

-> nil

Мы обходим дерево значения, заменяя конструкторы методами нашего воображаемого класса. Опреде-

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

Первый элемент списка:

head :: [a] -> a

head = foldr const (error ”empty list”)

Объединение списков:

(++) :: [a] -> [a] -> [a]

a ++ b = foldr (:) b a

В этой функции мы реконструируем заново первый список но в самом конце заменяем пустой список в

хвосте a на второй аргумент, так и получается объединение списков. Обратите внимание на эту особенность,

скорость выполнения операции (++) зависит от длины первого списка. Поэтому между двумя выражениями

((a ++ b) ++ c) ++ d

a ++ (b ++ (c ++ d))

Нет разницы в итоговом результате, но есть огромная разница по скорости вычисления! Второй гораздо

быстрее. Убедитесь в этом! Реализуем объединение списка списков в один список:

concat :: [[a]] -> [a]

concat = foldr (++) []

194 | Глава 12: Структурная рекурсия

Через свёртку можно реализовать и функцию преобразования списков:

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

map f = foldr ((:) . f) []

Если смысл выражения ((:) . f) не совсем понятен, давайте распишем его типы:

(:)

------->

([b] -> [b])

Напишем функцию фильтрации:

filter :: (a -> Bool) -> [a] -> [a]

filter p = foldr (\a as -> foldBool (a:as) as (p a)) []

Тут у нас целых две функции свёртки. Если значение предиката p истинно, то мы вернём все элементы

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

рекурсией foldl. Но это не так просто. Всё же попробуем. Для этого вспомним определение:

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

foldl f s []

= s

foldl f s (a:as)

= foldl f (f s a) as

Нам нужно привести это определение к виду foldr, нам нужно выделить два метода воображаемого

класса списка cons и nil:

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

foldr cons nil = \x -> case x of

a:as

-> a ‘cons‘ foldr cons nil as

[]

-> nil

Перенесём два последних аргумента определения foldl в правую часть, воспользуемся лямбда-

функциями и case-выражением:

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

foldl f = \x -> case x of

[]

-> \s -> s

a:as

-> \s -> foldl f as (f s a)

Мы поменяли местами порядок следования аргументов (второго и третьего). Выделим тождественную

функцию в первом уравнении case-выражения и функцию композиции во втором.

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

foldl f = \x -> case x of

[]

-> id

a:as

-> foldl f as . (flip f a)

Теперь выделим функции cons и nil:

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

foldl f = \x -> case x of

[]

-> nil

a:as

-> a ‘cons‘ foldl f as

where nil

= id

cons

= \a b -> b . flip f a

= \a

-> ( . flip f a)

Теперь запишем через foldr:

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

foldl f s xs = foldr (\a -> ( . flip f a)) id xs s

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

foldr мы сворачиваем списки в функции, последний аргумент предназначен как раз для результирующей

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

flip.

Свёртка | 195

Вычислительные особенности foldl и foldr

Если посмотреть на выражение, которое получается в результате вычисления foldr и foldl можно понять

почему они так называются.

В левой свёртке foldl скобки группируются влево, поэтому на конце l (left):

foldl f s [a1, a2, a3, a4] =

(((s ‘f‘ a1) ‘f‘ a2) ‘f‘ a3) ‘f‘ a4

В правой свёртке foldr скобки группируются вправо, поэтому на конце r (right):

foldr f s [a1, a2, a3, a4]

a1 ‘f‘ (a2 ‘f‘ (a3 ‘f‘ (a4 ‘f‘ s)))

Кажется, что если функция f ассоциативна

(a ‘f‘ b) ‘f‘ c

= a ‘f‘ (b ‘f‘ c)

то нет разницы какую свёртку применять. Разницы нет по смыслу, но может быть существенная разница

в скорости вычисления. Рассмотрим функцию concat, ниже два определения:

concat

= foldl (++) []

concat

= foldr (++) []

Какое выбрать? Результат и в том и в другом случае одинаковый (функция ++ ассоциативна). Стоит вы-

брать вариант с правой свёрткой. В первом варианте скобки будут группироваться влево, это чудовищно

скажется на производительности. Особенно если в конце небольшие списки:

Prelude> let concatl

= foldl (++) []

Prelude> let concatr

= foldr (++) []

Prelude> let x = [1 .. 1000000]

Prelude> let xs = [x,x,x] ++ map return x

Последним выражением мы создали список списков, в котором три списка по миллиону элементов, а в

конце миллион списков по одному элементу. Теперь попробуйте выполнить concatl и concatr на списке xs.

Вы заметите разницу по скорости печати. Также для сравнения можно установить флаг: :set +s.

Также интересной особенностью foldr является тот факт, что за счёт ленивых вычислений foldr не нужно

знать весь список, правая свёртка может работать и на бесконечных списках, в то время как foldl не вернёт

результат, пока не составит всё выражение. Например такое выражение будет вычислено:

Prelude> foldr (&& ) undefined $ True : True : repeat False

False

За счёт ленивых вычислений мы отбросили оставшуюся (бесконечную) часть списка. По этим примерам

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

но собирать результат в обратном порядке, например так в Prelude определена функция reverse, которая

переворачивает список:

reverse :: [a] -> [a]

reverse = foldl (flip (:)) []

Деревья

Мы можем определить свёртку и для деревьев. Вспомним тип:

data Tree a = Node a [Tree a]

Запишем в виде класса:

data Tree a b where

node :: a -> [b] -> b

В этом случае есть одна тонкость. У нас два рекурсивных типа: само дерево и внутри него – список. Для

преобразования списка мы воспользуемся функцией map:

196 | Глава 12: Структурная рекурсия

foldTree :: (a -> [b] -> b) -> Tree a -> b

foldTree node = \x -> case x of

Node a as -> node a (map (foldTree node) as)

Найдём список всех меток:

labels :: Tree a -> [a]

labels = foldTree $ \a bs -> a : concat bs

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

Сделаем дерево экземпляром класса Functor:

instance Functor Tree where

fmap f = foldTree (Node . f)

Очень похоже на map для списков. Вычислим глубину дерева:

depth :: Tree a -> Int

depth = foldTree $ \a bs -> 1 + foldr max 0 bs

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

среди всех поддеревьев.

12.2 Развёртка

С помощью развёртки мы постепенно извлекаем значение рекурсивного типа из значения какого-нибудь

другого типа. Этот процесс очень похож на процесс вычисления по имени. Сначала у нас есть отложенное

вычисление или thunk. Затем мы применяем к нему функцию редукции и у нас появляется корневой кон-

структор. А в аргументах конструктора снова сидят thunk’и. Мы применяем редукцию к ним. И так пока не

“развернём” всё значение.

Списки

Для разворачивания списков в Data.List есть специальная функция unfoldr. Присмотримся сначала к

её типу:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

Функция развёртки принимает стартовый элемент, а возвращает значение типа пары от Maybe. Типом

Maybe мы кодируем конструкторы списка:

data [a] b where

(:)

:: a -> b -> b

-- Maybe (a, b)

[]

:: b

-- Nothing

Конструктор пустого списка не нуждается в аргументах, поэтому его мы кодируем константой Nothing.

Объединение принимает два аргумента голову и хвост, поэтому Maybe содержит пару из головы и следующего

элемента для разворачивания. Закодируем это определение:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

unfoldr f = \b -> case (f b) of

Just (a, b’) -> a : unfoldr f b’

Nothing

-> []

Или мы можем записать это более кратко с помощью свёртки maybe:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

unfoldr f = maybe [] (\(a, b) -> a : unfoldr f b)

Смотрите, перед нами коробочка (типа b) с подарком (типа a), мы разворачиваем, а там пара: подарок

(типа a) и ещё одна коробочка. Тогда мы начинаем разворачивать следующую коробочку и так далее по

цепочке, пока мы не развернём не обнаружим Nothing, это означает что подарки кончились.

Типичный пример развёртки это функция iterate. У нас есть стартовое значение типа a и функция по-

лучения следующего элемента a -> a

Развёртка | 197

iterate :: (a -> a) -> a -> [a]

iterate f = unfoldr $ \s -> Just (s, f s)

Поскольку Nothing не используется цепочка подарков никогда не оборвётся. Если только нам не будет

лень их разворачивать. Ещё один характерный пример это функция zip:

zip :: [a] -> [b] -> [(a, b)]

zip = curry $ unfoldr $ \x -> case x of

([]

, _)

-> Nothing

, [])

-> Nothing

(a:as

, b:bs)

-> Just ((a, b), (as, bs))

Если один из списков обрывается, то прекращаем разворачивать. А если оба содержат голову и хвост, то

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

Потоки

Для развёртки хорошо подходят типы у которых, всего один конструктор. Тогда нам не нужно кодировать

альтернативы. Например рассмотрим потоки:

data Stream a = a :& Stream a

Они такие же как и списки, только без конструктора пустого списка. Функция развёртки для потоков

имеет вид:

unfoldStream :: (b -> (a, b)) -> b -> Stream a

unfoldStream f

= \b -> case f b of

(a, b’) -> a :& unfoldStream f b’

И нам не нужно пользоваться Maybe. Напишем функции генерации потоков:

iterate :: (a -> a) -> a -> Stream a

iterate f = unfoldStream $ \a -> (a, f a)

repeat :: a -> Stream a

repeat = unfoldStream $ \a -> (a, a)

zip :: Stream a -> Stream b -> Stream (a, b)

zip = curry $ unfoldStream $ \(a :& as, b :& bs) -> ((a, b), (as, bs))

Натуральные числа

Если присмотреться к натуральным числам, то можно заметить, что они очень похожи на списки. Списки

без элементов. Это отражается на функции развёртки. Для натуральных чисел мы будем возвращать не пару

а просто слкедующий элемент для развёртки:

unfoldNat :: (a -> Maybe a) -> a -> Nat

unfoldNat f = maybe Zero (Succ . unfoldNat f)

Напишем функцию преобразования из целых чисел в натуральные:

fromInt :: Int -> Nat

fromInt = unfoldNat f

where f n

| n == 0

= Nothing

| n >

= Just (n-1)

| otherwise = error ”negative number”

Обратите внимание на то, что в этом определении не участвуют конструкторы для Nat, хотя мы и строим

значение типа Nat. Конструкторы для Nat как и в случае списков кодируются типом Maybe. Развёртка ис-

пользуется гораздо реже свёртки. Возможно это объясняется необходимостью кодирования типа результата

некоторым промежуточным типом. Определения теряют в наглядности. Смотрим на функцию, а там Maybe

и не сразу понятно что мы строим: натуральные числа, списки или ещё что-то.

198 | Глава 12: Структурная рекурсия

12.3 Краткое содержание

В этой главе мы познакомились с особым видом рекурсии. Мы познакомились со структурной рекурсией.

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

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

структурной рекурсии в подарок. Есть языки, в которых структурная рекурсия является единственным воз-

можным способом составления рекурсивных функций.

Обратите внимание на то, что в этой главе мы определяли рекурсивные функции, но рекурсия встреча-

лась лишь в определении для функции свёртки и развёртки. Все остальные функции не содержали рекурсии,

более того почти все они определялись в бесточечном стиле. Структурная рекурсия это своего рода комби-

натор неподвижной точки, но не общий, а специфический для данного рекурсивного типа.

Структурная рекурсия бывает свёрткой и развёрткой.

Cвёрткой (fold) мы получаем значение некоторого произвольного типа из данного рекурсивного типа. При

этом все конструкторы заменяются на функции, которые возвращают новый тип.

Развёрткой (unfold) мы получаем из произвольного типа значение данного рекурсивного типа. Мы словно

разворачиваем его из значения, этот процесс очень похож на ленивые вычисления.

Мы узнали некоторые стандартные функции структурной рекурсии: cond или if-выражения, maybe, foldr,

unfoldr.

12.4 Упражнения

• Определите развёртку для деревьев из модуля Data.Tree.

• Определите с помощью свёртки следующие функции:

sum, prod

:: Num a => [a] -> a

or,

and

:: [Bool] -> Bool

length

:: [a] -> Int

cycle

:: [a] -> [a]

unzip

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

unzip3

:: [(a,b,c)] -> ([a],[b],[c])

• Определите с помощью развёртки следующие функции:

infinity

:: Nat

map

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

iterateTree :: (a -> [a]) -> a -> Tree a

zipTree

:: Tree a -> Tree b -> Tree (a, b)

• Поэкспериментируйте в интерпретаторе с только что определёнными функциями и теми функциями,

что мы определяли в этой главе.

• Рассмотрим ещё один стандартный тип. Он определён в Prelude. Это тип Either (дословно – один из

двух). Этот тип принимает два параметра:

data Either a b = Left a | Right b

Значение может быть либо значением типа a, либо значением типа b. Часто этот тип используют как

Maybe с информацией об ошибке. Конструктор Left хранит сообщение об ошибке, а конструктор Right

значение, если его удалось вычислить.

Например мы можем сделать такие определения:

headSafe :: [a] -> Either String a

headSafe []

= Left ”Empty list”

headSafe (x:_)

= Right x

divSafe :: Fractional a => a -> a -> Either String a

divSafe a 0 = Left ”division by zero”

divSafe a b = Right (a/b)

Для этого типа также определена функция свёртки она называется either. Не подглядывая в Prelude,

определите её.

Краткое содержание | 199

• Список является частным случаем дерева. Список это дерево, в каждом узле которого, лишь однин

дочерний узел. Деревья из модуля Data.Tree похожи на списки, но есть в них одно существенное

отличие. Они всегда содержат хотя бы один элемент. Пустой список не может быть представлен в виде

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

takeWhile для деревьев.

Определите деревья, которые не страдают от этого недостатка. Определите для них функции свёрт-

ки/развёртки, а также функции, которые мы определили для стандартных деревьев. Определите функ-

цию takeWhile (в рекурсивном виде и в виде развёртки) и сделайте их экземпляром класса Monad,

похожий на экземпляр для списков.

200 | Глава 12: Структурная рекурсия

Глава 13

Поиграем

Вот и закончилась первая часть книги. Мы узнали основные конструкции языка Haskell. В этой главе

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

упражнениями.

13.1 Стратегия написания программ

Описание задачи

Решение задачи начинается с описания проблемы и наброска решения. Мы хотим создать программу,

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

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

исходное положение. Каждым ходом мы двигаем одну фишку на пустое поле. В исходном положении фишки

идут по порядку.

10 11 12

15 14 12

13 14 15

Рис. 13.1: Случайное и конечное состояние игры пятнашки

Программа будет перемешивать фишки и отображать поле для игры. Она будет спрашивать следующий

ход и обновлять поле после хода. Если мы расставим все фишки по порядку, программа сообщит нам об этом

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

начать всё заново. Известно, что не из любого положения можно расставить фишки по порядку. Поэтому наш

алгоритм перемешивания должен генерировать только такие позиции, для которых решение возможно.

Набросок решения

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

игры и спрашивает следующий ход. Потом она распознаёт ход, и показывает обновлённое поле. И так далее.

Нам нужно как-то организовать этот диалог.

При этом в программе можно выделить две независимые части. Одна отвечает за сам диалог. Она прини-

мает реплики пользователя и отображает поле для игры. А другая часть отвечает за правила игры пятнашки:

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

| 201

У нас будет два отдельных модуля: один для описания игры, назовём его Game, а другой для описания

диалога с пользователем. Мы назовём его Loop (петля или цикл), поскольку диалог это зацикленная проце-

дура получения реплики и реакции на реплику.

Такой вот набросок-ориентир. После этого можно приступать к реализации. Но с чего начать?

Каркас. Типы и классы

В Haskell программы обычно начинают строить с каркаса – с типов и классов. Нам нужно выделить ос-

новные сущности и подумать какие типы подходят для их описания лучше всего.

В нашей задаче есть поле с фишками и ходы. Мы делаем ходы и фишки двигаются. Поле – это матрица

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

ячейке массива хранятся фишки. Фишки обозначаются целыми числами:

type Pos

= (Int, Int)

type Label

= Int

type Board

= Array Pos Label

Пустую фишку мы будем также обозначать числом. Физически когда мы ходим, мы меняем положение

одной фишки. Но в нашем описании мы меняем местами две фишки, поскольку пустая фишка также обозна-

чается номером. Когда мы ходим, мы меняем положение пустой фишки, одним ходом мы можем сместить

её вверх, вниз, влево или вправо. Введём специальный тип для обозначения ходов:

data Move = Up | Down | Left | Right

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

Game будет содержать текущее положение пустой клетки и положение фишек:

data Game = Game {

emptyField

:: Pos,

gameBoard

:: Board }

Вот и все типы для описания игры. Сохраним их в модуле Game. Теперь подумаем о типах для диалога

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

взаимодействие с игроком. Но, что является каркасом для диалога?

Если мы хотим с кем-нибудь общаться, необходимо чтобы у нас был с собеседником общий язык, он и

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

• Сделать ход

• Начать новую игру

• Выйти из игры

Если пользователь делает ход мы показываем новое положение поля, если он начинает новую игру мы

показываем ему новую перемешанную позицию, давайте у нас будет разная степень перемешанности фи-

гур. При перемешивании мы стартуем из победного положения и начинаем случайным образом делать хо-

ды. Чем больше ходов мы сделаем тем сложнее будет собрать игру. Поэтому пользователь будет указывать

число шагов для перемешивания при запросе новой игры. Если пользователь попросит закончить игру мы

попрощаемся и выйдем из игры.

На основе этих рассуждений вырисовывается следующий тип для сообщений:

data Query = Quit | NewGame Int | Play Move

Значение типа Query (запрос) может быть константа Quit (выход), запрос новой игры NewGame с числом,

которое указывает на сложность новой игры, также игрок может просто сделать ход Play Move.

А каков формат наших ответов? Все наши ответы на самом деле будут вызовами функции putStrLn мы

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

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

модуль Loop:

module Loop where

import Game

data Query = Quit | NewGame Int | Play Move

202 | Глава 13: Поиграем

И модуль Game:

module Game where

import Data.Array

data Move = Up | Down | Left | Right

deriving (Enum)

type Label = Int

type Pos = (Int, Int)

type Board = Array Pos Label

data Game = Game {

emptyField

:: Pos,

gameBoard

:: Board }

Ленивое программирование

Мы уже знаем как происходят ленивые вычисления. Мы принимаем выражение и начинаем очищать его

от синонимов от корня к листьям или сверху вниз. Оказывается таким способом можно писать программы.

Более того в функциональном программировании это очень распространённый подход. Мы начинаем со

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

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

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

всю программу.

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

шем её целиком. На каждом промежуточном шаге у нас есть неопределённые подвыражения. Получается,

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

Оказывается, что в Haskell есть решение этой проблемы. Нам поможет значение undefined. Мы будем

писать только тип функции (и мысленно будем говорить, пусть она делает то-то), а вместо определения

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

на первом же значении, но мы сможем узнать осмысленна ли наша программа с точки зрения компилятора,

проходит ли она проверку типов. В Haskell это большой плюс. Если программа прошла проверку типов, то

скорее всего она будет работать.

Такой подход написания программ называется написанием сверху вниз. Мы начинаем с самой верхней

функции и потихоньку вычищаем все undefined. Если вспомнить ленивые вычисления, то там роль undefined

выполняли отложенные вычисления.

В чём преимущества такого подхода? Посмотрим на дерево (рис. ?? ). Если мы идём сверху вниз, то в

самом начале у нас лишь одна задача, потом их становится всё больше и больше. Они дробятся, но источ-

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

подвыражение. Беда только в том, что это подвыражение содержит ещё больше подвыражений. Но сложные

подвыражения мы можем оставить на потом и заняться другими. А потом, когда мы их доделаем может вдруг

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

Рис. 13.2: Дерево задач

Стратегия написания программ | 203

Если же мы начинаем идти из листьев, то у нас много отправных точек, которые должны сойтись в одной

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

времени. И на остальные задачи у нас не хватит сил или мы можем потратить много времени на решение

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

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

малая часть.

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

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

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

мами, достаточными для тестирования приложения, оставив отрисовку деталей на потом. Мы не тратим

время на реализацию, а смотрим как программа выглядит “вцелом”. Если общий набросок нас устраивает

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

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

сменить реализацию некоторых частей. Но общая схема останется прежней, она уже устоялась на уровне ти-

пов. Часто такую стратегию разработки называют разработкой через прототипы (developing by prototyping).

При этом процесс написания приложения можно представить как процесс сходимости, приближения к преде-

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

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

исходит естественно, в ходе детализации, мы можем распределить нагрузку, распределив разные undefined

между участниками проекта.

Слово undefined будет встречаться очень часто, буквально в каждом значении. Оно очень длинное, и

часто писать его будет слишком утомительно. Определим удобный синоним. Я обычно использую un или

lol (что-нибудь краткое и удобное для автоматического поиска):

un :: a

un = undefined

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

Назовём её play. Это функция взаимодействия с пользователем она ведёт диалог, поэтому её тип будет IO

():

play :: IO ()

play = un

Итак у нас появилась корневая функция. Что мы будем в ней делать? Для начала мы поприветствуем игро-

ка (функция greetings). Затем предложим ему начать игру (функция setup), после чего запустим цикл игры

(функция gameLoop). Приветствие это просто надпись на экране, поэтому тип у него будет IO (). Предложе-

ние игры вернёт стартовую позицию для игры, поэтому тип будет IO Game. Цикл игры принимает состояние

и продолжает диалог. В типах это выражается так:

play :: IO ()

play = greetings >> setup >>= gameLoop

greetings :: IO ()

greetings = un

setup :: IO Game

setup = un

gameLoop :: Game -> IO ()

gameLoop = un

Сохраним эти определения в модуле Loop и загрузим модуль с программой в интерпретатор:

Prelude> :l Loop

[1 of 2] Compiling Game

( Game. hs, interpreted )

[2 of 2] Compiling Loop

( Loop. hs, interpreted )

Ok, modules loaded: Game, Loop.

*Loop>

Модуль загрузился. Он потянул за собой модуль Game, потому что мы воспользовались типом Move из

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

У нас три варианта дальнейшей детализации это функции greetings, setup и gameLoop. Мы пока пропу-

стим greetings там мы напишем какое-нибудь приветствие и сообщим игроку куда он попал и как ходить.

204 | Глава 13: Поиграем

В функции setup нам нужно начать первую игру. Для начала игры нам нужно узнать её сложность, на

сколько ходов перемешивать позицию. Это значит, что нам нужно спросить у игрока целое число. Мы спро-

сим число функцией getLine, а затем попробуем его распознать. Если пользователь ввёл не число, то мы

попросим его повторить ввод. Функция readInt :: String -> Maybe Int распознаёт число. Она возвращает

целое число завёрнутое в Maybe, потому что строка может оказаться не числом. Затем это число мы исполь-

зуем в функции shuffle (перемешать), которая будет возвращать позицию, которая перемешана с заданной

глубиной.

-- в модуль Loop

setup :: IO Game

setup = putStrLn ”Начнём новую игру?” >>

putStrLn ”Укажите сложность (положительное целое число): ” >>

getLine >>= maybe setup shuffle . readInt

readInt :: String -> Maybe Int

readInt = un

-- в модуль Game:

shuffle :: Int -> IO Game

shuffle = un

Функция shuffle возвращает состояние игры Game, которое завёрнуто в IO. Оно завёрнуто в IO, потому

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

модуля Random. Мы хотим чтобы каждая новая игра начиналась с новой позиции, поэтому скорее всего где-то

в недрах функции shuffle мы воспользуемся newStdGen, которая и потянет за собой тип IO.

Игра перемешивается согласно правилам, поэтому функцию shuffle мы поселим в модуле Game. А функ-

ция readInt это скорее элемент взаимодействия с пользователем, ведь в ней мы распознаём число в строчном

ответе, она останется в модуле Loop.

Проверим работает ли наша программа:

*Loop> :r

[1 of 2] Compiling Game

( Game. hs, interpreted )

[2 of 2] Compiling Loop

( Loop. hs, interpreted )

Ok, modules loaded: Game, Loop.

*Loop>

Работает! Можно спускаться по дереву выражения ниже. Сейчас нам предстоит написать одну из самых

сложных функций, это функция gameLoop.

13.2 Пятнашки

Цикл игры

Функция цикла игры принимает текущую позицию. При этом у нас два варианта. Возможно игра пришла

в конечное положение (isGameOver) и мы можем сообщить игроку о том, что он победил (showResults), если

это не так, то мы покажем текущее положение (showGame), спросим ход (askForMove) и среагируем на ход

(reactOnMove).

-- в модуль Loop

gameLoop :: Game -> IO ()

gameLoop game

| isGameOver game

= showResults game >> setup >>= gameLoop

| otherwise

= showGame game >> askForMove >>= reactOnMove game

showResults :: Game -> IO ()

showResults = un

showGame :: Game -> IO ()

showGame = un

Пятнашки | 205

askForMove :: IO Query

askForMove = un

reactOnMove :: Game -> Query -> IO ()

reactOnMove = un

-- в модуль Game

isGameOver :: Game -> Bool

isGameOver = un

Как определить закончилась игра или нет это скорее дело модуля Game. Все остальные функции принадле-

жат модулю Loop. Функция askForMove возвращает реплику пользователя и тут же направляет её в функцию

reactOnMove. Функции showGame и showResults ничего не возвращают, они только меняют состояния экрана.

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

Обратите внимание на то, как даже не дав определение функции, мы всё же очерчиваем её смысл в

объявлении типа. Так посмотрев на функцию askForMove и сопоставив тип с именем, мы можем понять, что

эта функция предназначена для запроса значения типа Query, для запроса реплики пользователя. А по типу

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

показывает, из типа видно что показывает значение типа Game или текущую позицию.

Отображение позиции

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

положение и объявим результат.

showResults :: Game -> IO ()

showResults g = showGame g >> putStrLn ”Игра окончена.”

Теперь определим функцию showGame. Если тип Game является экземпляром класса Show, то определение

окажется совсем простым:

-- в модуль Loop

showGame :: Game -> IO ()

showGame = putStrLn . show

-- в модуль Game

instance Show Game where

show = un

Реакция на реплики пользователя

Теперь нужно определить функции askForMove и reactOnMove. Первая функция требует установить про-

токол реплик пользователя, в каком виде он будет набирать значения типа Query. Нам пока лень об этом

думать и мы перейдём к функции reactOnMove. Вспомним её тип:

reactOnMove :: Game -> Query -> IO ()

Функция принимает текущее положение и запрос пользователя. И ничего не возвращает, она продолжает

игру. В любом случае в этой функции будет сопоставление с образцом по запросам пользователя так что

можно написать:

reactOnMove :: Game -> Query -> IO ()

reactOnMove game query = case query of

Quit

NewGame n

Play

Рассмотрим каждый из случаев. В первом случае пользователь говорит, что ему надоело и он уже наиг-

рался. Чтож попрощаемся и вернём значение единичного типа.

206 | Глава 13: Поиграем

...

Quit

-> quit

...

quit :: IO ()

quit = putStrLn ”До встречи.” >> return ()

В следующем варианте пользователь хочет начать всё заново. Так начнём!

NewGame n

-> gameLoop =<< shuffle n

Мы вызвали функцию перемешивания shuffle с заданным уровнем сложности. И рекурсивно вызвали

цикл игры с новой позицией. Всё началось по новой. В третьей альтернативе пользователь делает ход, на это

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

-- в модуль Loop

Play

-> gameLoop $ move m game

-- в модуль Game

move :: Move -> Game -> Game

move = un

Функция move обновляет согласно правилам текущую позицию. Соберём все определения вместе:

reactOnMove :: Game -> Query -> IO ()

reactOnMove game query = case query of

Quit

-> quit

NewGame n

-> gameLoop =<< shuffle n

Play

-> gameLoop $ move m game

Слушаем игрока

Теперь всё же вернёмся к функции askForMove, научимся слушать пользователя. Сначала мы скажем

какую-нибудь вводную фразу, предложение ходить (showAsk) затем запросим строку стандартной функцией

getLine, потом нам нужно будет распознать (parseQuery) в строке значение типа Query. Если распознать его

нам не удастся, мы напомним пользователю как с нами общаться (remindMoves) и попросим сходить вновь:

askForMove :: IO Query

askForMove = showAsk >>

getLine >>= maybe askAgain return . parseQuery

where askAgain = wrongMove >> askForMove

parseQuery :: String -> Maybe Query

parseQuery = un

wrongMove :: IO ()

wrongMove = putStrLn ”Не могу распознать ход.” >> remindMoves

showAsk :: IO ()

showAsk = un

remindMoves :: IO ()

remindMoves = un

Механизм распознавания похож на случай с распознаванием числа. Значение завёрнуто в тип Maybe. И в

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

Функции parseQuery и remindMoves тесно связаны. В первой мы распознаём ввод пользователя, а во вто-

рой напоминаем пользователю как мы закодировали его запросы. Тут стоит остановиться и серьёзно поду-

мать. Как закодировать значения типа Query, чтобы пользователю было удобно набирать их? Но давайте

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

слишком далеко, возможно наша программа потеряла смысл. Проверим типы!

*Loop> :r

[1 of 2] Compiling Game

( Game. hs, interpreted )

[2 of 2] Compiling Loop

( Loop. hs, interpreted )

Ok, modules loaded: Game, Loop.

Пятнашки | 207

Приведём код в порядок

Нам осталось дописать функции распознавания запросов и несколько маленьких функций с фразами и

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

лилось несколько задач по типу общения с пользователем. У нас есть задачи, в которых мы что-то показываем

пользователю, меняем состояние экрана и есть задачи, в которых мы просим от пользователя какие-то дан-

ные, ожидаем запросы функцией getLine. Также в самом верху выражения программы у нас расположены

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

принципу.

Основные функции

play :: IO ()

play = greetings >> setup >>= gameLoop

gameLoop :: Game -> IO ()

gameLoop game

| isGameOver game

= showResults game >> setup >>= gameLoop

| otherwise

= showGame game >> askForMove >>= reactOnMove game

setup :: IO Game

setup = putStrLn ”Начнём новую игру?” >>

putStrLn ”Укажите сложность (положительное целое число): ” >>

getLine >>= maybe setup shuffle . readInt

Запросы от пользователя (getLine)

reactOnMove :: Game -> Query -> IO ()

reactOnMove game query = case query of

Quit

-> quit

NewGame n

-> gameLoop =<< shuffle n

Play

-> gameLoop $ move m game

askForMove :: IO Query

askForMove = showAsk >>

getLine >>= maybe askAgain return . parseQuery

where askAgain = wrongMove >> askForMove

parseQuery :: String -> Maybe Query

parseQuery = un

readInt :: String -> Maybe Int

readInt = un

Ответы пользователю (putStrLn)

greetings :: IO ()

greetings = un

showResults :: Game -> IO ()

showResults g = showGame g >> putStrLn ”Игра окончена.”

showGame :: Game -> IO ()

showGame = putStrLn . show

showAsk :: IO ()

showAsk = un

quit :: IO ()

quit = putStrLn ”До встречи.” >> return ()

По этим функциям видно, что нам немного осталось. Теперь вернёмся к запросам пользователя.

Формат запросов

Можно вывести с помощью deriving экземпляр класса Read для типа Query и читать их функцией read.

Но это плохая идея, потому что пользователь нашей программы может и не знать Haskell. Лучше введём

сокращённые имена для всех значений. Например такие:

208 | Глава 13: Поиграем

left

-- Play Left

right

-- Play Rigth

-- Play Up

down

-- Play Down

quit

-- Quit

new n

-- NewGame n

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

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

функций разбора значения и напоминания ходов:

parseQuery :: String -> Maybe Query

parseQuery x = case x of

”up”

-> Just $ Play Up

”u”

-> Just $ Play Up

”down”

-> Just $ Play Down

”d”

-> Just $ Play Down

”left”

-> Just $ Play Left

”l”

-> Just $ Play Left

”right” -> Just $ Play Right

”r”

-> Just $ Play Right

”quit”

-> Just $ Quit

”q”

-> Just $ Quit

’n’:’e’:’w’:’ ’:n

-> Just . NewGame =<< readInt n

’n’:’ ’:n

-> Just . NewGame =<< readInt n

-> Nothing

remindMoves :: IO ()

remindMoves = mapM_ putStrLn talk

where talk = [

”Возможные ходы пустой клетки:”,

”

left

или l

-- налево”,

”

right

или r

-- направо”,

”

или u

-- вверх”,

”

down

или d

-- вниз”,

”Другие действия:”,

”

new int

или n int -- начать новую игру, int - целое число,”,

”указывающее на сложность”,

”

quit

или q

-- выход из игры”]

Проверим работоспособность:

Prelude> :l Loop

[1 of 2] Compiling Game

( Game. hs, interpreted )

[2 of 2] Compiling Loop

( Loop. hs, interpreted )

Loop. hs:46:28:

Ambiguous occurrence ‘Left’

It could refer to either ‘Prelude.Left’,

imported from ‘Prelude’ at Loop. hs:1:8-11

(and originally defined in ‘Data.Either’)

< Назад Далее >

Канал с обзорами, анонсами новинок и книжными подборками

Книжный Вестник

Бот для удобного поиска книг (если не нашлось на сайте)

Поиск книг

Свежие любовные романы в удобных форматах

Любовные романы

О психологии, саморазвитии и личностном росте

Саморазвитие

Детективы и триллеры, все новинки

Детективы

Фантастика и фэнтези, все новинки

Фантастика

Отборные классические книги

Классика

Библиотека с любовными романами, которая наверняка придётся по вкусу женской части аудитории

Любовные романы

Библиотека с фантастикой и фэнтези, а также смежных жанров

Фантастика

Самые популярные книги в формате фб2

Топ фб2 книги