Учебник по Haskell

записи. Мы можем определять переменные доступные только для чтения (GettableStateVar a), только для

записи (SettableStateVar a) или обычные изменяемые переменные (SetVar a).

Операции чтения и записи описываются с помощью классов:

class HasGetter s where

get :: s a -> IO a

class HasSetter s where

($=) :: s a -> a -> IO ()

Основные библиотеки | 289

Тип IORef принадлежит и тому, и другому классу:

main = do

var <- newIORef 2

x

<- get var

print x

var $= 4

x

<- get var

print x

OpenGL

OpenGL является ярким примером библиотеки построенной на изменяемых переменных. OpenGL можно

представить как большой конечный автомат. Каждая строчка кода – это запрос на изменение состояния. При-

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

дущих команд. Параметры рисования задаются глобальными переменными (тип StateVar).

OpenGL не зависит от конкретной оконной системы, она отвечает лишь за рисование. Для того чтобы

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

этого мы воспользуемся GLFW, это библиотека также пришла в Haskell из С. Интерфейсы GLFW и OpenGL очень

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

окно и закрасим фон белым цветом:

module Main where

import Graphics.UI.GLFW

import Graphics.Rendering.OpenGL

import System.Exit

title = ”Hello OpenGL”

width

= 700

height

= 600

main = do

initialize

openWindow (Size width height) [] Window

windowTitle $= title

clearColor $= Color4 1 1 1 1

windowCloseCallback $= exitWith ExitSuccess

loop

loop = do

display

loop

display = do

clear [ColorBuffer]

swapBuffers

Мы инициализируем GLFW, задаём параметры окна. Устанавливаем цвет фона. Цвет имеет четыре пара-

метра это RGB-цвета и параметр прозрачности. Затем мы говорим, что программе делать при закрытии окна.

Мы устанавливаем функцию обратного вызова (callback) windowCloseCallback. В самом конце мы входим в

цикл, который только и делает, что стирает окно цветом фона и делает рабочий буфер видимым. Что такое

буфер? Буфер – это место в котором мы рисуем. У нас есть два буфера. Один мы показываем пользователю,

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

командой swapBuffers.

Посмотрим, что у нас получилось:

$ ghc --make HelloOpenGL.hs

$ ./HelloOpenGL

Нарисуем упрощённое начальное положение нашей игры: прямоугольную рамку и в ней – красный шар:

290 | Глава 20: Императивное программирование

module Main where

import Graphics.UI.GLFW

import Graphics.Rendering.OpenGL

import System.Exit

title = ”Hello OpenGL”

width, height :: GLsizei

width

= 700

height

= 600

w2, h2 :: GLfloat

w2 = (fromIntegral $ width) / 2

h2 = (fromIntegral $ height)

/ 2

dw2, dh2 :: GLdouble

dw2 = fromRational $ toRational w2

dh2 = fromRational $ toRational h2

main = do

initialize

openWindow (Size width height) [] Window

windowTitle $= title

clearColor $= Color4 1 1 1 1

ortho (-dw2-50) (dw2+50) (-dh2-50) (dh2+50) (-1) 1

windowCloseCallback $= exitWith ExitSuccess

windowSizeCallback

$= (\size -> viewport $= (Position 0 0, size))

loop

loop = do

display

loop

display = do

clear [ColorBuffer]

color black

line (-w2) (-h2) (-w2) h2

line (-w2) h2

w2

h2

line w2

h2

w2

(-h2)

line w2

(-h2)

(-w2) (-h2)

color red

circle 0 0 10

swapBuffers

vertex2f :: GLfloat -> GLfloat -> IO ()

vertex2f a b = vertex (Vertex3 a b 0)

-- colors

white = Color4 (0::GLfloat)

black = Color4 (0::GLfloat) 0 0 1

red

= Color4 (1::GLfloat) 0 0 1

-- primitives

line :: GLfloat -> GLfloat -> GLfloat -> GLfloat -> IO ()

Основные библиотеки | 291

line ax ay bx by = renderPrimitive Lines $ do

vertex2f ax ay

vertex2f bx by

circle :: GLfloat -> GLfloat -> GLfloat -> IO ()

circle cx cy rad =

renderPrimitive Polygon $ mapM_ (uncurry vertex2f) points

where n = 50

points = zip xs ys

xs = fmap (\x -> cx + rad * sin (2*pi*x/n)) [0 .. n]

ys = fmap (\x -> cy + rad * cos (2*pi*x/n)) [0 .. n]

Рис. 20.1: Начальное положение

Мы рисуем с помощью функции renderPrimitive. Она принимает метку элемента, который мы собира-

емся рисовать и набор вершин. Так метка Lines обозначает линии, а метка Polygon – закрашенные много-

угольники. В OpenGL нет специальной операции для рисования окружностей, поэтому нам придётся предста-

вить окружность в виде многоугольника (circle). Функция ortho устанавливает область видимости рисунка,

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

передаются не списком а в специальном do-блоке. За счёт этого мы можем изменить какие-нибудь парамет-

ры OpenGL во время рисования. Обратите внимание на то, как мы изменяем цвет примитива. Перед тем как

рисовать примитив мы устанавливаем значение цвета (color).

Анимация

Оживим нашу картинку. При клике мышкой шарик игрока последует в направлении курсора. Для того

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

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

программы (время измеряется в секундах):

sleep :: Double -> IO ()

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

getMouseButton

:: MouseButton -> IO KeyButtonState

mousePos

:: StateVar Position

Функция getMouseButton сообщает текущее состояние кнопок мыши, мы будем перехватывать положение

мыши во время нажатия левой кнопки:

292 | Глава 20: Императивное программирование

onMouse ball = do

mb <- getMouseButton ButtonLeft

when (mb == Press) (get mousePos >>= updateVel ball)

Стандартная функция when из модуля Control.Monad выполняет действие только в том случае, если пер-

вый аргумент равен True. Для обновления положения и направления скорости шарика нам придётся вос-

пользоваться глобальной переменной типа IORef Ball:

data Ball = Ball

{ ballPos :: Vec2d

, ballVel :: Vec2d

}

Код программы:

module Main where

import Control.Applicative

import Data.IORef

import Graphics.UI.GLFW

import Graphics.Rendering.OpenGL

import System.Exit

import Control.Monad

type Time = Double

title = ”Hello OpenGL”

width, height :: GLsizei

fps :: Int

fps = 60

frameTime :: Time

frameTime = 1000 * ((1::Double) / fromIntegral fps)

width

= 700

height

= 600

w2, h2 :: GLfloat

w2 = (fromIntegral $ width) / 2

h2 = (fromIntegral $ height)

/ 2

dw2, dh2 :: GLdouble

dw2 = fromRational $ toRational w2

dh2 = fromRational $ toRational h2

type Vec2d = (GLfloat, GLfloat)

data Ball = Ball

{ ballPos :: Vec2d

, ballVel :: Vec2d

}

initBall = Ball (0, 0) (0, 0)

dt :: GLfloat

dt = 0.3

minVel = 10

main = do

initialize

openWindow (Size width height) [] Window

windowTitle $= title

Основные библиотеки | 293

clearColor $= Color4 1 1 1 1

ortho (-dw2) (dw2) (-dh2) (dh2) (-1) 1

ball <- newIORef initBall

windowCloseCallback $= exitWith ExitSuccess

windowSizeCallback

$= (\size -> viewport $= (Position 0 0, size))

loop ball

loop :: IORef Ball -> IO ()

loop ball = do

display ball

onMouse ball

sleep frameTime

loop ball

display ball = do

(px, py) <- ballPos <$> get ball

(vx, vy) <- ballVel <$> get ball

ball $= Ball (px + dt*vx, py + dt*vy) (vx, vy)

clear [ColorBuffer]

color black

line (-ow2) (-oh2) (-ow2) oh2

line (-ow2) oh2

ow2

oh2

line ow2

oh2

ow2

(-oh2)

line ow2

(-oh2)

(-ow2) (-oh2)

color red

circle px py 10

swapBuffers

where ow2 = w2 - 50

oh2 = h2 - 50

onMouse ball = do

mb <- getMouseButton ButtonLeft

when (mb == Press) (get mousePos >>= updateVel ball)

updateVel ball pos = do

(p0x, p0y) <- ballPos <$> get ball

v0

<- ballVel <$> get ball

size <- get windowSize

let (p1x, p1y) = mouse2canvas size pos

v1 = scaleV (max minVel $ len v0) $ norm (p1x - p0x, p1y - p0y)

ball $= Ball (p0x, p0y) v1

where norm v@(x, y) = (x / len v, y / len v)

len

(x, y) = sqrt (x*x + y*y)

scaleV k (x, y) = (k*x, k*y)

mouse2canvas :: Size -> Position -> (GLfloat, GLfloat)

mouse2canvas (Size sx sy) (Position mx my) = (x, y)

where d a b

= fromIntegral a / fromIntegral b

x

= fromIntegral width * (d mx sx - 0.5)

y

= fromIntegral height * (negate $ d my sy - 0.5)

vertex2f :: GLfloat -> GLfloat -> IO ()

vertex2f a b = vertex (Vertex3 a b 0)

-- colors

... white, black, red

-- primitives

line

:: GLfloat -> GLfloat -> GLfloat -> GLfloat -> IO ()

circle

:: GLfloat -> GLfloat -> GLfloat -> IO ()

294 | Глава 20: Императивное программирование

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

шарика. Функция mouse2canvas переводит координаты в окне GLFW в координаты OpenGL. В GLFW начало ко-

ординат лежит в левом верхнем углу окна и ось Oy направлена вниз. Мы же переместили начало координат

в центр окна и ось Oy направлена вверх.

Посмотрим что у нас получилось:

$ ghc --make Animation.hs

$ ./Animation

Chipmunk

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

грамму немного физики. Воспользуемся библиотекой Hipmunk

cabal install Hipmunk

Она даёт возможность вызывать из Haskell функции С-библиотеки Chipmunk. Эта библиотека позволя-

ет строить двухмерные физические модели. Основным элементом модели является пространство (Space).

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

(Shape). Тело отвечает за такие физические характеристики как масса, момент инерции, восприимчивость к

силам. По форме определяются моменты столкновения тел. Форма может состоять из нескольких примити-

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

(Constraint) они имитируют пружинки, шарниры. Мы можем назначать выполнение IO-действий на столк-

новения.

Опишем в Hipmunk модель шарика бегающего в замкнутой коробке:

module Main where

import Data.StateVar

import Physics.Hipmunk

main = do

initChipmunk

space <- newSpace

initWalls space

ball <- initBall space initPos initVel

loop 100 space ball

loop :: Int -> Space -> Body -> IO ()

loop 0 _

_

= return ()

loop n space ball = do

showPosition ball

step space 0.5

loop (n-1) space ball

showPosition :: Body -> IO ()

showPosition ball = do

pos <- get $ position ball

print pos

initWalls :: Space -> IO ()

initWalls space = mapM_ (uncurry $ initWall space) wallPoints

initWall :: Space -> Position -> Position -> IO ()

initWall space a b = do

body

<- newBody infinity infinity

shape

<- newShape body (LineSegment a b wallThickness) 0

elasticity shape $= nearOne

spaceAdd space body

spaceAdd space shape

initBall :: Space -> Position -> Velocity -> IO Body

initBall space pos vel = do

body

<- newBody ballMass ballMoment

shape

<- newShape body (Circle ballRadius) 0

Основные библиотеки | 295

position body $= pos

velocity body $= vel

elasticity shape $= nearOne

spaceAdd space body

spaceAdd space shape

return body

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

-- inits

nearOne = 0.9999

ballMass = 20

ballMoment = momentForCircle ballMass (0, ballRadius) 0

ballRadius = 10

initPos = Vector 0 0

initVel = Vector 10 5

wallThickness = 1

wallPoints = fmap (uncurry f) [

((-w2, -h2), (-w2, h2)),

((-w2, h2),

(w2, h2)),

((w2, h2),

(w2, -h2)),

((w2, -h2),

(-w2, -h2))]

where f a b = (g a, g b)

g (a, b) = H.Vector a b

h2 = 100

w2 = 100

Функция initChipmunk инициализирует библиотеку Chipmunk. Она должна быть вызвана один раз до

любой из функций библиотеки Hipmunk. Функции new[Body|Shape|Space] создают объекты модели. Мы сде-

лали стены неподвижными, присвоив им бесконечную массу и момент инерции (initWall). Упругость удара

определяется переменной elasticity, она не может быть больше единицы. Единица обозначает абсолютно

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

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

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

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

рамки.

Теперь объединим OpenGL и Hipmunk:

module Main where

import Control.Applicative

import Control.Applicative

import Data.StateVar

import Data.IORef

import Graphics.UI.GLFW

import System.Exit

import Control.Monad

import qualified Physics.Hipmunk

as H

import qualified Graphics.UI.GLFW as G

import qualified Graphics.Rendering.OpenGL as G

title = ”in the box”

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

-- inits

type Time = Double

-- frames per second

fps :: Int

fps = 60

296 | Глава 20: Императивное программирование

-- frame time in milliseconds

frameTime :: Time

frameTime = 1000 * ((1::Double) / fromIntegral fps)

nearOne = 0.9999

ballMass = 20

ballMoment = H. momentForCircle ballMass (0, ballRadius) 0

ballRadius = 10

initPos = H.Vector 0 0

initVel = H.Vector 0 0

wallThickness = 1

wallPoints = fmap (uncurry f) [

((-ow2, -oh2), (-ow2, oh2)),

((-ow2, oh2),

(ow2, oh2)),

((ow2, oh2),

(ow2, -oh2)),

((ow2, -oh2),

(-ow2, -oh2))]

where f a b = (g a, g b)

g (a, b) = H.Vector a b

dt :: Double

dt = 0.5

minVel :: Double

minVel = 10

width, height :: Double

height = 500

width = 700

w2, h2 :: Double

h2 = height / 2

w2 = width / 2

ow2, oh2 :: Double

ow2 = w2 - 50

oh2 = h2 - 50

data State = State

{ stateBall

:: H.Body

, stateSpace

:: H.Space

}

ballPos :: State -> StateVar H.Position

ballPos = H. position . stateBall

ballVel :: State -> StateVar H.Velocity

ballVel = H. velocity . stateBall

main = do

H. initChipmunk

initGLFW

state <- newIORef =<< initState

loop state

loop :: IORef State -> IO ()

loop state = do

display state

onMouse state

sleep frameTime

Основные библиотеки | 297

loop state

simulate :: State -> IO Time

simulate a = do

t0 <- get G. time

H. step (stateSpace a) dt

t1 <- get G. time

return (t1 - t0)

initGLFW :: IO ()

initGLFW = do

G. initialize

G. openWindow (G.Size (d2gli width) (d2gli height)) [] G.Window

G. windowTitle $= title

G. windowCloseCallback $= exitWith ExitSuccess

G. windowSizeCallback

$= (\size -> G. viewport $= (G.Position 0 0, size))

G. clearColor $= G.Color4 1 1 1 1

G. ortho (-dw2) (dw2) (-dh2) (dh2) (-1) 1

where dw2 = realToFrac w2

dh2 = realToFrac h2

initState :: IO State

initState = do

space <- H. newSpace

initWalls space

ball <- initBall space initPos initVel

return $ State ball space

initWalls :: H.Space -> IO ()

initWalls space = mapM_ (uncurry $ initWall space) wallPoints

initWall :: H.Space -> H.Position -> H.Position -> IO ()

initWall space a b = do

body

<- H. newBody H. infinity H. infinity

shape

<- H. newShape body (H.LineSegment a b wallThickness) 0

H. elasticity shape $= nearOne

H. spaceAdd space body

H. spaceAdd space shape

initBall :: H.Space -> H.Position -> H.Velocity -> IO H.Body

initBall space pos vel = do

body

<- H. newBody ballMass ballMoment

shape

<- H. newShape body (H.Circle ballRadius) 0

H. position body $= pos

H. velocity body $= vel

H. elasticity shape $= nearOne

H. spaceAdd space body

H. spaceAdd space shape

return body

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

-- graphics

display state = do

drawState =<< get state

simTime <- simulate =<< get state

sleep (max 0 $ frameTime - simTime)

drawState :: State -> IO ()

drawState st = do

pos <- get $ ballPos st

G. clear [G.ColorBuffer]

drawWalls

drawBall pos

G. swapBuffers

drawBall :: H.Position -> IO ()

298 | Глава 20: Императивное программирование

drawBall pos = do

G. color red

circle x y $ d2gl ballRadius

where (x, y) = vec2gl pos

drawWalls :: IO ()

drawWalls = do

G. color black

line (-dow2) (-doh2) (-dow2) doh2

line (-dow2) doh2

dow2

doh2

line dow2

doh2

dow2

(-doh2)

line dow2

(-doh2)

(-dow2) (-doh2)

where dow2 = d2gl ow2

doh2 = d2gl oh2

onMouse state = do

mb <- G. getMouseButton ButtonLeft

when (mb == Press) (get G. mousePos >>= updateVel state)

updateVel state pos = do

size <- get G. windowSize

st <- get state

p0 <- get $ ballPos st

v0 <- get $ ballVel st

let p1 = mouse2canvas size pos

ballVel st $=

H. scale (H. normalize $ p1 - p0) (max minVel $ H. len v0)

mouse2canvas :: G.Size -> G.Position -> H.Vector

mouse2canvas (G.Size sx sy) (G.Position mx my) = H.Vector x y

where d a b

= fromIntegral a / fromIntegral b

x

= width * (d mx sx - 0.5)

y

= height * (negate $ d my sy - 0.5)

vertex2f :: G.GLfloat -> G.GLfloat -> IO ()

vertex2f a b = G. vertex (G.Vertex3 a b 0)

vec2gl :: H.Vector -> (G.GLfloat, G.GLfloat)

vec2gl (H.Vector x y) = (d2gl x, d2gl y)

d2gl :: Double -> G.GLfloat

d2gl = realToFrac

d2gli :: Double -> G.GLsizei

d2gli = toEnum . fromEnum . d2gl

...

Функции не претерпевшие особых изменений пропущены. Теперь наше глобальное состояние (State)

содержит тело шара (оно пригодится нам для вычисления его положения) и пространство, в котором живёт

наша модель. Стоит отметить функцию simulate. В ней происходит обновление состояния модели. При

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

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

потратить на один кадр (frameTime).

20.2 Боремся с IO

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

предыдущим главам. Столько do и IO разбросано по всему коду. И такой примитивный результат в итоге.

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

Не отчаивайтесь!

Давайте лучше подумаем как свести этот псевдо-Haskell к минимуму. Подумаем какие источники IO

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

Боремся с IO | 299

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

новые шары, добавляя их к пространству модели. Также в IO происходит отрисовка игры. Hipmunk будет кон-

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

Сколько всего! Голова идёт кругом.

Но помимо всего этого у нас есть логика игры. Логика игры отвечает за реакцию игрового мира на раз-

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

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

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

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

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

программы. За обновление объектов отвечает насыщенная IO библиотека Hipmunk.

Мы постараемся побороться с IO-кодом так. Сначала мы выделем те параметры, которые могут быть

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

наш мир на два лагеря: “чистый” и “грязный”:

data World = World

{ worldPure

:: Pure

, worldDirty

:: Dirty }

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

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

которых чистый и грязный мир общаются между собой:

data Query = Remove Ball | HeroVelocity H.Velocity | MakeBall Freq

data Event = Touch Ball | UserClick H.Position

data Sense = Sense

{ senseHero

:: HeroBall

, senseBalls

:: [Ball]

}

Через Query чистые данные могут рассказать грязным о том, что необходимо удалить шар из игры, об-

новить скорость шара игрока или создать новый шар (Freq отвечает за параметры создания шара). Грязные

данные могут рассказать чистым на языке Event и Sense о том, что один из шаров коснулся до шара иг-

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

параметры шаров в типе Sense. Тип Event отвечает за события, которые происходят иногда, а тип Sense за

те параметры, которые мы наблюдаем непрерывно (это типы глазарук), Query – это язык действий (это тип

руконог). Нам понадобится ещё один маленький язык, на котором мы будем объясняться с OpenGL.

data Picture = Prim Color Primitive

| Join Picture Picture

data Primitive = Line Point Point | Circle Point Radius

data Point

= Point Double Double

type Radius = Double

data Color = Color Double Double Double

Эти три языка станут барьером, которым мы ограничим влияние IO. У нас будут функции:

percept

:: Dirty -> IO (Sense, [Event])

updatePure

:: Sense -> [Event] -> Pure -> (Pure, [Query])

react

:: [Query] -> Dirty -> IO Dirty

updateDirty :: Dirty -> IO Dirty

picture

:: Pure -> Picture

draw

:: Picture -> IO ()

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

updateDirty. Давайте опять начнём проектироваание сверху-вниз. С этими функциями мы уже можем напи-

сать основную функцию цикла игры:

loop :: IORef World -> IO ()

loop worldRef = do

world <- get worldRef

300 | Глава 20: Императивное программирование

drawWorld world

(world, dt) <- updateWorld world

worldRef $= world

G. addTimerCallback (max 0 $ frameTime - dt) $ loop worldRef

updateWorld :: World -> IO (World, Time)

updateWorld world = do

t0 <- get G. elapsedTime

(sense, events) <- percept dirty

let (pure’, queries) = updatePure sense events pure

dirty’ <- updateDirty =<< react queries dirty

t1 <- get G. elapsedTime

return (World pure’ dirty’, t1 - t0)

where dirty = worldDirty world

pure

= worldPure

world

drawWorld :: World -> IO ()

drawWorld = draw . picture . worldPure

20.3 Определяемся с типами

Давайте подумаем, из чего состоят типы Dirty и Pure. Начнём с Pure. Там точно будет вся информация

необходимая нам для рисования картинки (ведь функция picture определена на Pure). Для рисования нам

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

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

шаров. Так мы приходим к типу:

data Pure = Pure

{ pureScores

:: Scores

, pureHero

:: HeroBall

, pureBalls

:: [Ball]

, pureStat

:: Stat

, pureCreation

:: Creation

}

Что нам нужно знать о шаре героя? Нам нужно его положение для отрисовки и модуль вектора скорости

(он понадобится нам при обновлении вектора скорости шара игрока):

data HeroBall = HeroBall

{ heroPos

:: H.Position

, heroVel

:: H.CpFloat

}

Для остальных шаров нам нужно знать только тип шара, его положение и идентификатор шара. По иден-

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

data Ball = Ball

{ ballType

:: BallType

, ballPos

:: H.Position

, ballId

:: Id

}

data BallType = Hero | Good | Bad | Bonus

deriving (Show, Eq, Enum)

type Id = Int

Статистика игры состоит из числа жизней и бонусных очков:

data Scores = Scores

{ scoresLives :: Int

, scoresBonus :: Int

}

Определяемся с типами | 301

Как будет происходить создание новых шаров? Если плохих шаров будет слишком много, то играть будет

не интересно, игрок слишком быстро проиграет. Если хороших шаров будет слишком много, то игроку также

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

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

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

то скорее всего мы создадим хороший шар и наоборот. Если общее число шаров велико, то мы не будем

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

не будут уничтожены игроком. Эти рассуждения приводят нас к типам:

data Creation = Creation

{ creationStat

:: Stat

, creationGoalStat

:: Stat

, creationTick

:: Int

}

data Stat = Stat

{ goodCount

:: Int

, badCount

:: Int

, bonusCount

:: Int

}

data Freq = Freq

{ freqGood

:: Float

, freqBad

:: Float

, freqBonus

:: Float

}

Поле creationStat содержит текущее число шаров на поле, поле creationGoalStat – число шаров, к ко-

торому мы стремимся. Значение типа Freq содержит веса вероятностей создания нового шара определённого

типа. На каждом шаге мы будем прибавлять единицу к creationTiсk, как только оно достигнет определён-

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

Перейдём к грязным данным. Там мы будем хранить информацию, необходимую для обновления модели

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

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

data Dirty = Dirty

{ dirtyHero

:: Obj

, dirtyObjs

:: IxMap Obj

, dirtySpace

:: H.Space

, dirtyTouchVar :: Sensor H.Shape

, dirtyMouse

:: Sensor H.Position

}

data Obj = Obj

{ objType

:: BallType

, objShape

:: H.Shape

, objBody

:: H.Body

}

type Sensor a = IORef (Maybe a)

Особая структура IxMap отвечает за хранение значений вместе с индексами. Пока остановимся на самом

простом представлении:

type IxMap a = [(Id, a)]

20.4 Структура проекта

Наметим структуру проекта. У нас уже есть модуль Types. hs. Основной цикл игры будет описан в модуле

Loop. hs. Общие функции обновления состояния будут определены в World. hs, также у нас будет два модуля

отвечающие за обновление чистых и грязных данных – Pure. hs и Dirty. hs. Мы выделим отдельный модуль

для описания всех констант игры (Inits. hs). Так нам будет удобно настроить игру, когда мы закончим с

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

типами OpenGL и Hipmunk.

302 | Глава 20: Императивное программирование

20.5 Детализируем функции обновления состояния игры

Начнём с восприятия:

module World where

import qualified Physics.Hipmunk as H

import Data.Maybe

import Types

import Utils

import Pure

import Dirty

percept :: Dirty -> IO (Sense, [Event])

percept a = do

hero

<- obj2hero $ dirtyHero a

balls

<- mapM (uncurry obj2ball) $ setIds dirtyObjs a

evts1

<- fmap maybeToList $ getTouch (dirtyTouchVar a) $ dirtyObjs a

evts2

<- fmap maybeToList $ getClick $ dirtyMouse a

return $ (Sense hero balls, evts1 ++ evts2)

where setIds = zip [0.. ]

-- в Dirty.hs

obj2hero

:: Obj -> IO HeroBall

obj2ball

:: Id -> Obj -> IO Ball

getTouch

:: Sensor H.Shape -> IxMap Obj -> IO (Maybe Event)

getClick

:: Sensor H.Position -> IO (Maybe Event)

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

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

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

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

updatePure :: Sense -> [Event] -> Pure -> (Pure, [Query])

updatePure s evts = updateEvents evts . updateSenses s

-- в Pure.hs

updateSenses :: Sense -> Pure -> Pure

updateEvents :: [Event] -> Pure -> (Pure, [Query])

В функции react мы предполагаем, что реакции мира на события независимы друг от друга. foldQuery~–

функция свёртки для типа Query.

import Control.Monad

...

react :: [Query] -> Dirty -> IO Dirty

react = foldr (<=< ) return

. fmap (foldQuery removeBall heroVelocity makeBall)

-- в Dirty.hs

removeBall

:: Ball

-> Dirty -> IO Dirty

heroVelocity

:: H.Velocity

-> Dirty -> IO Dirty

makeBall

:: Freq

-> Dirty -> IO Dirty

Обратите внимание на то, как мы воспользовались функциями foldr, return и <=< для того чтобы нани-

зать друг на друга функции типа Dirty -> IO Dirty. Напомню, что функция <=< ~– это аналог композиции

для монадных функций.

Обновление модели:

updateDirty :: Dirty -> IO Dirty

updateDirty = stepDirty dt

-- в Dirty.hs

Детализируем функции обновления состояния игры | 303

stepDirty :: H.Time -> Dirty -> IO Dirty

-- в Inits.hs

dt :: H.Time

dt = 0.5

Функции рисования поместим в отдельный модуль Graphics. hs

-- переместим из Loop.hs в World.hs

drawWorld :: World -> IO ()

drawWorld = draw . picture . worldPure

-- в Graphics.hs

draw :: Picture -> IO ()

-- в Pure.hs

picture

:: Pure -> Picture

Добавим функцию инициализации игры:

initWorld :: IO World

initWorld = do

dirty

<- initDirty

(sense, events) <- percept dirty

return $ World (initPure sense events) dirty

-- в Dirty.hs

initDirty :: IO Dirty

-- в Pure.hs

initPure :: Sense -> [Event] -> Pure

20.6 Детализируем дальше

Вот так на самом интересном месте… Мы вынуждены прерваться. Я надеюсь, что вы уловили основную

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

Причём в этом модуле будут только чистые функции. Осталось примерно 1000 строк кода. Я не буду выпи-

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

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

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

В этой главе мы посмотрели на две интересные библиотеки. Физический движок Hipmunk и графическую

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

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

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

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

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

собой на специальных маленьких языках, которые закодированы в типах. Это язык наблюдений (Event), язык

реакций (Query) и язык отрисовки игрового мира (Picture).

20.8 Упражнения

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

роятной динамикой. Ещё лучше! Напишите её. При этом продумайте проект игры так, чтобы IO-типы не

разбежались по всей программе.

304 | Глава 20: Императивное программирование

Глава 21

Музыкальный пример

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

помощью библиотеки HCodecs. Она предоставляет возможность создания midi-файлов по описанию в Haskell.

При этом описание напоминает описание самого формата midi. Мы же хотим подняться уровнем выше и

описывать музыку нотами и композицией нот.

21.1 Музыкальная нотация

Для начала зададимся выясним: а что же такое музыка с точки зрения нашего секвенсора? Мы ищем

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

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

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

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

истории.

Нотная запись в европейской традиции

В европейской традиции принято описывать музыку в виде нотной записи. Нотный лист состоит из серии

нотных станов. Нотный стан состоит из пяти линеек. Каждая линейка обозначает определённую высоту. Нота

состоит из обозначения длительности и высоты. Разные длительности обозначаются штрихами и цветом

ноты, а высоте соответствует расположение на нотном стане.

Рис. 21.1: Буквенные обозначения высоты ноты

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

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

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

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

ступеней. Их обозначают разными именами. Например в латинской нотации их обозначают так:

0

1

2

3

4

5

6

7

8

9

10

11

C

C

D

D

E

F

F

G

G

A

A

B

C

D

D

E

E

F

G

G

A

A

B

B

do

re

mi

f a

sol

la

ti

В самом нижнем ряду расположены имена нот. Во втором и четвёртом – обозначения нот с диезами и

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

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

диез или понижением на один шаг с помощью знака бемоль b.

| 305

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

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

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

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

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

Теперь давайте посмотрим крупным планом на протокол midi.

Протокол midi

Протокол midi появился в ответ на бурное развитие синтезаторов. Каждый из синтезаторов предлагал

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

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

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

одинаковых клавиатур. Для того чтобы отделить тембр от управления (нажатия на клавиши игроком) был

придуман протокол midi. Протокол midi описывает специфическую для нажатия на клавиши информацию.

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

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

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

с помощью одной клавиатуры. Такие клавиатуры называют midi-клавиатурами.

Познакомимся с терминологией midi. Протокол midi рассчитан на управление синтезаторами в режиме

реального времени. Можно сказать, что midi-файл – это история концерта или выступления, низкоуровневая

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

клавиши, сила давления на клавишу в определённый момент времени, нажатие педали, поворот реле или

смена тэмбра.

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

имеет возможность добавить какие-то особенные настройки. При этом те сообщения, которые данный ге-

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

на клавишу и отпускание клавиши. Также у нас будут разные инструменты.

Установим библиотеку HCodecs с Hackage:

cabal install HCodecs

Теперь заглянем на страницу документации этого пакета (на сайте Hackage), нас интересует модуль

Codec.Midi, ведь мы хотим создавать именно midi-файлы. Здесь мы видим описание протокола midi, за-

кодированное в типах. Посмотрим на тип Message, он описывает midi-сообщения. В первую очередь нас ин-

тересуют конструкторы:

NoteOn {

channel

:: !Channel,

key

:: !Key,

velocity :: !Velocity }

NoteOff

{

channel

:: !Channel,

key

:: !Key,

velocity :: !Velocity }

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

ленивых вычислениях. Конструктор NoteOn обозначает нажатие клавиши на канале Channel с высотой Key и

уровнем громкости Velocity. Конструктор NoteOff обозначает отпускание клавиши, параметры имеют тот

же смысл, что и в случае NoteOn.

Думаю что такое высота и громкость примерно понятно, но что такое канал? Считается, что один испол-

нитель может управлять сразу несколькими генераторами тона. Управление распределяется по каналам. На

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

ются целыми числами из диапазона от 0 до 127. Ноте до первой октавы ( C) соответствует цифра 60, ноте ля

первой октавы ( A) соответствует номер 69. Одно число кодирует сразу и октаву и ступень лада.

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

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

64 или начальное значение 0.

Также мы будем играть разными инструментами. Инструменты в протоколе midi называются програм-

мами. Мы можем установить определённый инструмент на данном канале с помощью сообщения:

306 | Глава 21: Музыкальный пример

ProgramChange {

channel :: !Channel,

preset

:: !Preset }

Целое число Preset указывает на код инструмента. Теперь посмотрим, что же такое midi-файл:

data Midi = Midi {

fileType :: FileType,

timeDiv

:: TimeDiv,

tracks

:: [Track Ticks] }

midi-файл состоит из трёх значений. Это обозначение типа файла:

data FileType = SingleTrack | MultiTrack | MultiPattern

По типу midi-файлы могут различаться на файлы с одним треком, файлы с несколькими треками, и

файлы, которые содержат группы треков, которые называют узорами (pattern). По смыслу трек соответствует

партии инструмента.

Тип TimeDiv кодирует скорость записи сообщений. Различают два варианта:

data TimeDive = TicksPerBeat Int

| TicksPerSecond Int Int

Первый конструктор говорит о том, что разрешение времени закодировано в формате PPQN, он указы-

вает на число ударов в одной четвертной длительности. Второй конструктор говорит о том, что разрешение

кодируется в формате SMPTE, оно указывает на число кадров в секунде.

Теперь посмотрим, что такое трек:

type Track a = [(a, Message)]

Трек это список событий с временными отсчётами. Время в midi отсчитывается относительно предыдуще-

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

произошли ещё два события:

[(0, e1), (0, e2), (0, e3), (10, e4), (0, e5)]

21.2 Музыкальная запись в виде событий

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

надстройку над протоколом midi. Я долго думал об этом и в итоге пришёл к выводу, что наиболее простой

и податливый способ представления музыки на нотном уровне реализован в языке Csound. Там ноты пред-

ставлены в виде последовательности событий. Каждое событие начинается в определённый момент и длится

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

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

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

ность события. Мы ослабим эти ограничения. Событие будет содержать лишь время начала, длительность и

некоторое содержание.

data Event t a = Event {

eventStart

:: t,

eventDur

:: t,

eventContent

:: a

} deriving (Show, Eq)

Параметр t символизирует время, а параметр a – некоторое содержание события. Мы будем говорить,

что в некоторый момент времени произошло значение типа a и оно длилось некоторое время. Треком мы

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

data Track t a = Track {

trackDur

:: t,

trackEvents

:: [Event t a]

}

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

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

Значение тишины будет выглядеть так:

silence t = Track t []

Этим мы говорим, что ничего не произошло в течение t единиц времени.

Музыкальная запись в виде событий | 307

Преобразование событий во времени

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

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

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

delayEvent :: Num t => t -> Event t a -> Event t a

delayEvent d e = e{ eventStart = d + eventStart e }

Ещё одно простое преобразование заключается в изменении масштаба времени, в музыке или анимации

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

stretchEvent :: Num t => t -> Event t a -> Event t a

stretchEvent s e = e{

eventStart

= s * eventStart e,

eventDur

= s * eventDur

e }

Для изменения масштаба времени мы умножили временные параметры на число s. Эти операции мы

можем перенести и на значения типа Track.

delayTrack :: Num t => t -> Track t a -> Track t a

delayTrack d (Track t es) = Track (t + d) (map (delayEvent d) es)

stretchTrack :: Num t => t -> Track t a -> Track t a

stretchTrack s (Track t es) = Track (t * s) (map (stretchEvent s) es)

Класс преобразований во времени

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

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

Temporal (временн ой):

class Temporal a where

type Dur a :: *

dur

:: a -> Dur a

delay

:: Dur a -> a -> a

stretch :: Dur a -> a -> a

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

к методам delay и stretch мы добавим метод dur, мы будем считать, что всё что происходит во времени

конечно и с помощью метода dur мы всегда можем узнать протяжённость значения их класса Temporal во

времени. Для определения этого класса нам придётся подключить расширение TypeFamilies. Теперь мы

легко можем определить экземпляры класса Temporal для Event и Track:

instance Num t => Temporal (Event t a) where

type Dur (Event t a) = t

dur

= eventDur

delay

= delayEvent

stretch = stretchEvent

instance Num t => Temporal (Track t a) where

type Dur (Track t a) = t

dur

= trackDur

delay

= delayTrack

stretch = stretchTrack

Композиция треков

Определим две полезные в музыке операции: параллельную и последовательную композицию треков. В

параллельной композиции мы играем два трека одновременно:

(=:=) :: Ord t => Track t a -> Track t a -> Track t a

Track t es =:= Track t’ es’ = Track (max t t’) (es ++ es’)

Теперь общая длительность трека равна длительности большего из треков, а события включают в себя

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

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

308 | Глава 21: Музыкальный пример

(+:+) :: (Ord t, Num t) => Track t a -> Track t a -> Track t a

(+:+) a b = a =:= delay (dur a) b

При этом у нас как раз и получится, что мы сначала сыграем целиком трек a, а затем трек b. Теперь

определим аналоги операций =:= и +:+ для списков:

chord :: (Num t, Ord t) => [Track t a] -> Track t a

chord = foldr (=:=) (silence 0)

line :: (Num t, Ord t) => [Track t a] -> Track t a

line = foldr (+:+) (silence 0)

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

loop :: (Num t, Ord t) => Int -> Track t a -> Track t a

loop n t = line $ replicate n t

Экземпляры стандартных классов

Мы можем сделать тип трек экземпляром класса Functor:

instance Functor (Event t) where

fmap f e = e{ eventContent = f (eventContent e) }

instance Functor (Track t) where

fmap f t = t{ trackEvents = fmap (fmap f) (trackEvents t) }

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

объединения, а нейтральным элементом будет тишина, которая длится ноль единиц времени:

instance (Ord t, Num t) => Monoid (Track t a) where

mappend = (=:=)

mempty

= silence 0

21.3 Ноты в midi

С помощью типа Track мы можем описывать всё, что имеет свойство случаться во времени и длиться,

мы можем описывать наборы событий. Операции из класса Temporal и операции последовательной и парал-

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

чтобы это стало музыкой, нам не хватает нот.

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

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

событии, эта информация уже встроена в тип Track.

data Note = Note {

noteInstr

:: Instr,

noteVolume

:: Volume,

notePitch

:: Pitch,

isDrum

:: Bool

}

Итак нота содержит код инструмента, громкость и высоту и ещё один параметр. По последнему пара-

метру можно узнать сыграна нота на барабане или нет. В midi ноты для ударных обрабатываются особым

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

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

type Instr

= Int

type Volume = Int

type Pitch

= Int

Целые числа соответствуют целым числам в протоколе midi. Значения для типов Volume и Pitch лежат в

диапазоне от 0 до 127.

Введём специальное обозначение для музыкального типа Track:

type Score = Track Double Note

Ноты в midi | 309

Синонимы для нот

Высота ноты

Музыкантам ближе буквенные обозначения для нот нежели коды midi. Определим удобные синонимы:

note :: Int -> Score

note n = Track 1 [Event 0 1 (Note 0 64 (60+n) False)]

Эта функция строит трек, который содержит одну ноту. Нота длится одну целую длительность играется

на инструменте с кодом 0, на средней громкости. Параметр функции задаёт смещение от ноты до первой

октавы. Определим остальные ноты:

a, b, c, d, e, f, g,

as, bs, cs, ds, es, fs, gs,

af, bf, cf, df, ef, ff, gf :: Score

c = note 0;

cs = note 1;

d = note 2;

ds = note 3;

...

Первая буква содержит буквенное обозначение ноты, а вторая либо s (от англ. sharp диез) или f (от англ.

flat бемоль). Все эти ноты находятся в первой октаве, но смещением высоты на 12 единиц мы легко можем

смещать эти ноты в любую другую октаву:

higher :: Int -> Score -> Score

higher n = fmap (\a -> a{ notePitch = 12*n + notePitch a })

lower :: Int -> Score -> Score

lower n = higher (-n)

high :: Score -> Score

high = higher 1

low :: Score -> Score

low = lower 1

С помощью этих функций мы легко можем смещать группы нот в любую октаву. Функция higher прини-

мает число октав, на которые необходимо сместить вверх высоту во всех нотах трека. Смещение высоты на

12 определяет смещение на одну октаву. Остальные функции определены в через функцию higher.

Длительность ноты

Пока что наши ноты длятся 1 единицу времени. Но нам бы хотелось иметь в распоряжении и другие дли-

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

изменим масштаб времени и длительность всех нот изменится. Определим несколько синонимов:

bn, hn, qn, en, sn :: Score -> Score

-- (brewis note)

(half note)

(quater note)

bn = stretch 2;

hn = stretch 0.5;

qn = stretch 0.25;

-- (eighth note)

(sizth note)

en = stretch 0.125;

sn = stretch 0.0625;

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

Громкость ноты

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

тех, что изменяли высоту звука октавами:

louder :: Int -> Score -> Score

louder n = fmap $ \a -> a{ noteVolume = n + noteVolume a }

quieter :: Int -> Score -> Score

quieter n = louder (-n)

310 | Глава 21: Музыкальный пример

Смена инструмента

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

номер соответствует роялю. Но с помощью класса Functor мы легко можем изменить инструмент:

instr :: Int -> Score -> Score

instr n = fmap $ \a -> a{ noteInstr = n, isDrum = False }

drum :: Int -> Score -> Score

drum n = fmap $ \a -> a{ notePitch = n, isDrum = True }

Согласно протоколу midi в случае ударных инструментов высота звука кодирует инструмент. Поэтому

в функции drum мы изменяем именно поле notePitch. Создадим также несколько синонимов для создания

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

bam :: Int -> Score

bam n = Track 1 [Event 0 1 (Note 0 n 35 True)]

Номер 35 кодирует “бочку”.

Паузы

Слово silence верно отражает смысл, но оно слишком длинное. Давайте определим несколько синони-

мов:

rest :: Double -> Score

rest = silence

wnr = rest 1;

bnr = bn wnr;

hnr = hn wnr;

qnr = qn wnr;

enr = en wnr;

snr = sn wnr;

21.4 Перевод в midi

Теперь мы можем составить какую нибудь мелодию:

q = line [c, c, hn e, hn d, bn e, chord [c, e]]

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

функцию:

render :: Score -> Midi

Мы реализуем простейший случай. Будем считать, что у нас только 15 инструментов, а все остальные

инструменты – ударные. Мы запишем нашу музыку на один трек midi-файла, распределив 15 неударных

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

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

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

import qualified Codec.Midi as M

render :: Score -> Midi

render s = M.Midi M.SingleTrack (M.TicksPerBeat divisions) [toTrack s]

divisions :: M.Ticks

divisions = 96

toTrack :: Score -> M.Track

toTrack = undefined

Мы загрузили модуль Codec.Midi под псевдонимом M, так мы сможем отличать низкоуровневые опре-

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

писать приставку M.

В нашей упрощённой реализации на одном канале может играть только один инструмент. В самом начале

мы назначим инструмент на канал с помощью сообщения ProgramChange. Для этого нам необходимо понять

какому инструменту какой канал соответствует. В библиотеке HCodecs каналы идут от нуля до 15. Девятый

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

по инструментам:

Перевод в midi | 311

type MidiEvent = Event Double Note

groupInstr :: Score -> ([[MidiEvent]], [MidiEvent])

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

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

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

которая превращает эту пару в набор midi-сообщений:

mergeInstr :: ([[MidiEvent]], [MidiEvent]) -> M.Track Double

Наши отсчёты времени записаны в виде значений типа Double, Нам необходимо перейти к целочислен-

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

tfmTime :: M.Track Double -> M.Track M.Ticks

Тогда функция toTrack примет вид:

toTrack :: Score -> M.Track M.Ticks

toTrack = tfmTime . mergeInstr . groupInstr

Все три составляющие функции пока не определены. Начнём с функции tfmTime. Нам необходимо от-

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

относительные. Специально для этого в библиотеке HСodecs определена функция:

fromAbsTime :: Num a -> Track a -> Track a

Также нам понадобится функция:

type Time = Double

fromRealTime :: TimeDiv -> Trrack Time -> Track Ticks

Она проводит квантование во времени. С помощью неё мы преобразуем отсчёты в Double в целочисленные

отсчёты. С помощью этих функций мы можем определить функцию timeDiv так:

import Data.List(sortBy)

import Data.Function (on)

...

tfmTime :: M.Track Double -> M.Track M.Ticks

tfmTime = M. fromAbsTime . M. fromRealTime timeDiv .

sortBy (compare ‘on‘ fst)

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

относительным и в самом конце производим квантование по времени. Функция sortBy сортирует элементы

согласно некоторой функции упорядочивания:

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

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

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

дочивания мы составляем с помощью специальной функции on, которая определена в модуле Data.Function.

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

цию двух аргументов и функцию одного аргумента и словно “подкладывает” вторую функцию под первую:

Prelude Data.Function> :t on

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

Теперь напишем функцию mergeInstr. Она устанавливает инструменты на каналы и преобразует события

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

остальных инструментов:

312 | Глава 21: Музыкальный пример

mergeInstr :: ([[MidiEvent]], [MidiEvent]) -> M.Track Double

mergeInstr (instrs, drums) = concat $ drums’ : instrs’

where instrs’ = zipWith setChannel ([0 .. 8] ++ [10 .. 15]) instrs

drums’

= setDrumChannel drums

setChannel :: M.Channel -> [MidiEvent] -> M.Track Double

setChannel = undefined

setDrumChannel :: [MidiEvent] -> M.Track Double

setDrumChannel =

undefined

Имя instrs’ указывает на последовательность списков сообщений для каждого неударного инструмента.

Функция setChannel принимает номер канала и список событий. По ним она строит список midi-сообщений.

Определим эту функцию:

setChannel :: M.Channel -> [MidiEvent] -> M.Track Double

setChannel ch ms = case ms of

[]

-> []

x:xs

-> (0, M.ProgramChange ch (instrId x)) : (fromEvent ch =<< ms)

instrId = noteInstr . eventContent

fromEvent :: M.Channel -> MidiEvent -> M.Track Double

fromEvent = undefined

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

инструмент. По построению программы все ноты в переданном списке играются на одном и том же инстру-

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

неопределённая функция fromEvent она переводит сообщение в список midi-сообщений:

fromEvent :: M.Channel -> MidiEvent -> M.Track Double

fromEvent ch e = [

(eventStart e, noteOn n),

(eventStart e + eventDur e, noteOff n)]

where n = clipToMidi $ eventContent e

noteOn

n = M.NoteOn

ch (notePitch n) (noteVolume n)

noteOff n = M.NoteOff ch (notePitch n) 0

clipToMidi :: Note -> Note

clipToMidi n = n {

notePitch

= clip $ notePitch n,

noteVolume

= clip $ noteVolume n }

where clip = max 0 . min 127

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

для ударных инструментов в midi-сообщения:

setDrumChannel :: [MidiEvent] -> M.Track Double

setDrumChannel ms = fromEvent drumChannel =<< ms

where drumChannel = 9

Для ударных инструментов выделен отдельный канал. Считается, что все они происходят на 10 канале.

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

девятый канал.

Мы переводим событие в два midi-сообщения, первое говорит о том, что мы начали играть ноту, а второе

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

в диапазон midi.

Нам осталось определить только одну функцию. Эта функция распределяет события по инструментам.

Сначала мы разделим события на те, что играются на ударных и неударных инструментах, а затем разделим

“неударные” ноты по инструментам:

import Control.Arrow(first, second)

import Data.List(sortBy, groupBy, partition)

...

groupInstr :: Score -> ([[MidiEvent]], [MidiEvent])

Перевод в midi | 313

groupInstr = first groupByInstrId .

partition (not . isDrum . eventContent) . trackEvents

where groupByInstrId = groupBy ((==) ‘on‘ instrId) .

sortBy

(compare ‘on‘ instrId)

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

Функция partition разделяет список на пару списков. В первом списке находятся все те элементы, для

которых заданный предикат вернул True, а во втором списке – все остальные элементы исходного списка:

Prelude Data.List> :t partition

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

Функция groupBy превращает список в список списков:

Prelude Data.List> :t groupBy

groupBy :: (a -> a -> Bool) -> [a] -> [[a]]

Если бинарная функция на соседних элементах исходного списка вернула True, то они помещаются в

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

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

отсортировали события по значению идентификатора. После этого значения с одинаковыми идентификато-

рами стали соседними и мы сгруппировали их с помощью groupBy.

Функция first применяет функцию к первому элементу пары. Вот мы и закончили, можно послушать ре-

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

в момент времени t = 0, но на практике это может оказаться не так, мы можем сместить ноты функцией

delay в отрицательную сторону. Тогда первые ноты будут содержать отрицательное время начала события.

Но мы можем исправить эту ситуацию, сместив все ноты на время самой первой ноты, конечно смещать

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

alignEvents :: [MidiEvent] -> [MidiEvent]

alignEvents es

| d < 0

= map (delay (abs d)) es

| otherwise = es

where d = minimum $ map eventStart es

Вызовем эту функцию сразу после функции trackEvents в функции groupInstr. Второй нюанс заключа-

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

HCodecs оно обозначается с помощью конструктора TrackEnd. В самом конце необходимо добавить сообще-

ние (0, TrackEnd):

toTrack :: Score -> M.Track M.Ticks

toTrack = addEndMsg . tfmTime . mergeInstr . groupInstr

addEndMsg :: M.Track M.Ticks -> M.Track M.Ticks

addEndMsg = (++ [(0, M.TrackEnd)])

Теперь мы можем проверить, что у нас получилось. Создадим файл:

module Main where

import System

import Track

import Score

import Codec.Midi

out = (>> system ”timidity tmp.mid”) .

exportFile ”tmp.mid” . render

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

tmp. mid и в самом конце запускаем файл с помощью проигрывателя timidity. Вместо timidity вы можете

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

татор. Послушаем ноту до:

*Main> out c

314 | Глава 21: Музыкальный пример

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

ранную на рояле. Наберём какую-нибудь мелодию:

*Main> let x = line [c, hn e, hn e, low b, c]

*Main> out x

Сыграем в два раза быстрее, на другом инструменте:

*Main> out $ instr 15 $ hn x

Сыграем канон. Канон это когда одна и та же мелодия ведётся в разных голосах с запаздыванием. Сыграем

двухголосный канон:

*Main> out $ instr 80 (loop 3 x) =:= delay 2 (instr 65 $ low $ loop 3 x)

Номера инструментов можно посмотреть по справке к протоколу General Midi. Это дополнение к прото-

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

21.5 Пример

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

дию. Ниже приведён небольшой пример. Инструменты:

closedHiHat = drum 42;

rideCymbal = drum 59;

cabasa = drum 69;

maracas

= drum 70;

tom

= drum 45;

flute

= instr 73;

piano

= instr 0;

Ударная секция:

b1 = bam 100

b0 = bam 84

drums1 = loop 80 $ chord [

tom

$ line [qn b1, qn b0, hnr],

maracas $ line [hnr, hn b0]

]

drums2 = quieter 20 $ cabasa $ loop 120 $ en $ line [b1, b0, b0, b0, b0]

drums3 = closedHiHat $ loop 50 $ en (line [b1, loop 12 wnr])

drums = drums1 =:= drums2 =:= drums3

Уже сейчас мы можем загрузить эту партию в интерпретатор и послушать, вызвав out drums. Аккорды к

мелодии:

c7

= chord [c, e, b]

gs7 = chord [low af, c, g]

g7

= chord [low g, low bf, f]

harmony = piano $ loop 12 $ lower 1 $ bn $ line [bn c7, gs7, g7]

Мелодия:

ac = louder 5

mel1 = bn $ line [bnr, subMel, ac $ stretch (1+1/8) e, c,

subMel, enr]

where subMel = line [g, stretch 1.5 $ qn g, qn f, qn g]

mel2 = loop 2 $ qn $ line [subMel, ac $ bn ds, c, d, ac $ bn c, c, c, wnr,

subMel, ac $ bn g, f, ds, ac $ bn f, ds, ac $ bn c]

where subMel = line [ac ds, c, d, ac $ bn c, c, c]

mel3 = loop 2 $ line [pat1 (high c) as g, pat1 g f d]

where pat1 a b c = line [pat a, loop 3 qnr, wnr,

pat b, qnr, hnr, pat c, qnr, hnr]

pat

x

= en (x +:+ x)

mel = flute $ line [mel1, mel2, mel3]

Пример | 315

Добавим в конце звук тарелки:

cha = delay (dur mel1 + dur mel2) $ loop 10 $ rideCymbal $ delay 1 b1

Соберём всё вместе и послушаем:

res = chord [

drums,

harmony,

high mel,

louder 40 cha,

rest 0]

main = out res

В конце стоит фиктивный элемент rest 0 для того чтобы было удобно глушить инструменты комменти-

рованием.

21.6 Эффективное представление музыкальной нотации

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

Мы очень часто пользуемся операцией delay через операцию line. Так в выражении:

q = line [s1, s2, line [loop 2 s3, s4], s5]

Мы будем несколько раз обходить элемент s3 для каждого применения line. К примеру сначала мы

смести все элементы на 3, потом сместим на 5, потом на 10, но вместо этого мы могли бы сразу сместить

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

в типе Track:

data Track t a = Track {

trackDur

:: t,

trackEvents :: TList t a

data TList t a = Empty | Single a | Append (TList t a) (TList t a)

| TFun (Tfm t) (TList t a)

data Tfm t = Tfm ! t ! t

Тип TList позволяет проводить быстрое объединение списков. Дополнительный конструктор TFun обо-

значает линейное преобразование списка во времени. Линейное преобразование кодируется двумя числами,

это масштаб и смещение. Мы считаем, что события в конструкторе Single начинаются в момент времени 0

и длятся 1 единицу времени. Так например событие, которое произошло на 2 единице времени и длилось 4

единицы можно представить так:

TFun (4 2) (Single a)

Значение Tfm k d обозначает линейную функцию

f ( x) = kx + d

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

“не преобразованного” события, то есть события Event 0 1 a.

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

fromTList :: TList t a -> [Event t a]

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

перевод из Track в Midi останутся прежними.

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

В этой главе мы построили секвенсор для создания midi-файлов. Мы воспользовались библиотекой

HCodecs и создали над ней небольшую надстройку.

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

менное воспроизведение) и преобразование событий во времени (сдвиг и масштабирование). Все остальные

операции выражались через эти простейшие операции. Отметим, что есть и другие подходы. Например в биб-

лиотеках Haskore и Euterpea примитивными конструкциями является единичное событие (без отметок во

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

виде реализован в библиотеках temporal-music-notation и temporal-music-notation-demo.

316 | Глава 21: Музыкальный пример

21.8 Упражнения

• Попробуйте написать какую-нибудь мелодию.

• Подумайте каких операций не хватает. Например было бы удобно иметь возможность вырезать из ме-

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

позволяет убрать лишнее.

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

Приложения

318 | Приложения

Начало работы с Haskell

Компилятор

Для программирования в Haskell нам понадобится компилятор. Мы будем пользоваться наиболее разви-

тым компилятором~– GHC. Лучше всего устанавливать его вместе с Haskell Platform:

http://hackage.haskell.org/platform/

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

библиотек. Если по каким-то причинам установить Haskell Platform не удалось. Не отчаивайтесь, можно

загрузить компилятор с сайта GHC:

http://www.haskell.org/ghc/

И далее установить все необходимые библиотеки с Hackage с помощью cabal (устанавливается отдельно

с http://www.haskell.org/cabal/).

Среда разработки

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

продвинутых текстовых редакторах (vim, Emacs, scite, kate, notepad++). Отметим всё же среду разработки

Leksah (http://leksah.org/), она написана на Haskell и её можно установить с Hackage.

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

подсветка синтаксиса можно воспользоваться gedit. Пишем код в gedit, сохраняем, переключаемся на ghci,

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

gedit.

Начало работы с Haskell | 319

Литература

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

электронный журнал “Практика функционального программирования” (). Пока в нём доминируют два языка

– это Erlang и Haskell.

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

в создании этой книги.

Книги

• Miran Lipovac̆a. Learn You A Haskell For A Great Good.

Очень хорошая книга для начинающих, Haskell в картинках. Весёлая и познавательная книга1

http://learnyouahaskell.com/

• Hal Daume III. Yet Another Haskell Tutorial.

Ещё одна очень хорошая книга для начинающих. Без картинок, но всё по делу.

• Paul Hudak. Haskell School of Expression.

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

Haskell. Главные достоинства – много текста об общих принципах и интересные приложения, картинки,

музыка, анимация, управление роботами и всё это на Haskell.

• Paul Hudak. Haskell School of Music.

Пол Хьюдак увлекается не только Haskell, но и музыкой. Он написал книгу, которая целиком посвящена

описанию музыки в Haskell:

http://www.cs.yale.edu/homes/hudak/Papers/HSoM.pdf

http://haskell.cs.yale.edu/

• Bryan O’Sullivan, Don Stewart, John Goerzen. Real World Haskell.

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

Авторы подробно изучают вопросы, связанные с применением Haskell на практике.

http://book.realworldhaskell.org/

• Готовится к выходу к книга Саймона Марлоу о параллельных вычислениях в Haskell. Обещает быть

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

Тематический сборник

Основы

• John Hughes. Why Functional Programming Matters.

• Paul Hudak, John Hughes, Simon Peyton Jones, Philip Wadler. A History of Haskell: Being Lazy With Class.

• Mark P. Jones. Functional Programming with Overloading and Higher-Order Polymorphism.

• Евгений Кирпичев. Элементы функциональных языков программирования, журнал Практика функци-

онального программирования.

• Simon Thompson. Programming It in Haskell.

• Justin Bailey. Haskell Cheat Sheet.

Разработка программ сверху-вниз

• Дмитрий Астапов. Давно не брал я в руки шашек, журнал Практика функционального программиро-

вания.

1Обновление: книга переведена на русский, вышла в издательстве ДМК Пресс.

320 | Приложения

Функторы и монады

• Conor McBride, Ross Paterson. Applicative programming with effects. Статья об аппликативных функторах.

• Philip Wadler. The Essence of Functional Programming.

Статья, в которой впервые зашла речь о применении монад в Haskell.

• Tarmo Uustalu, Varmo Vene. The Essence of Dataflow Programming.

Статья о комонадах, но есть много интересного и о монадах.

• Bulat Ziganshin. Haskell I/O inside: Down the Rabbit’s Hole. Статья на HaskellWiki.

• John Launchbury, Simon Peyton Jones. Lazy functional state threads.

Статья о типе ST.

• Simon Peyton Jones. Tackling the Awkward Squad: monadic input/output, concurrency, exceptions, and

foreign-language calls in Haskell.

Ленивые вычисления

• Douglas McIlroy. Power Series, Power Serious.

• Дмитрий Астапов. Реурсия+мемоизация=динамическое программирование, журнал Практика функ-

ционального программирования.

• Сергей Зефиров. Лень бояться, журнал Практика функционального программирования.

• Jerzy Karczmarczuk. Specific “scientific” data structures, and their processing.

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

• Graham Hutton. A tutorial on the universality and expressiveness of fold

• Jeremy Gibbons. Origami Programming.

• Jeremy Gibbons, Geraint Jones. The Under-Appreciated Unfold.

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

• Шалак В.И. Шейнфинкель и комбинаторная логика.

• Paul Hudak: Conception, Evolution, and Application of Functional Programming Languages.

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

• Бенджамин Пирс. Типы в языках программирования.

Большая книга о теории типов.

http://newstar.rinet.ru/~goga/tapl/

• Денис Москвин. Системы типизации лямбда-исчисления.

Курс видео-лекций.

http://www.lektorium.tv/course/?id=22797

• John Harrison. Introduction to Functional Programming.

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

• А. Филд, П. Харрисон, Функциональное программирование, Москва “Мир”, 1993.

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

Прочитав её, вы сможете не только пользоваться ФП-языками но и написать такой язык самостоя-

тельно.

• Rinus Plasmeijer and Marko van Eekelen. Functional Programming and Parallel Graph Rewriting.

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

пиляторов для функциональных языков.

Литература | 321

Теория категорий

Две очень хорошие книги для начинающих:

• Maarten M. Fokkinga. Gentle Introduction to Category Theory.

Также где-то в сети есть и перевод на русский.

• Steve Awodey. Category Theory.

• Eugenia Cheng, Simon Willerton aka TheCatsters. Курс видео-лекций на youtube.

http://www.scss.tcd.ie/Edsko.de.Vries/ct/catsters/linear.php

http://www.youtube.com/user/TheCatsters

Статьи по категориальным типам:

• Varmo Vene. Categorical Programming with Inductive and Coinductive Types. Phd-диссертация.

• Erik Meijer, Graham Hutton. Bananas in Space: Extending Fold and Unfold to Exponential Types.

• Martin Erwig. Categorical Programming with Abstract Data Types.

• Martin Erwig. Metamorphic Programming: Structured Recursion for Abstract Data Types.

Практика

• Conal Elliott. Denotational design with type class morphisms.

• Johan Tibell. High Performance Haskell. Слайды с выступления.

• Johan Tibel. Faster persistent data structures through hashing. Слайды с выступления.

• Simon Marlow. Parallel and Concurrent Programming in Haskell.

• Edward Z. Yang. Блог о Haskell в картинках. Много полезной информации о лени и устройстве ghc.

http://blog.ezyang.com/about/

• Oleg Kiselyov. Блог в том числе и о Haskell. Много решений интересных и нетривиальных задач. http:

//okmij.org/ftp/

Как работает GHC

• Документация GHC:

http://hackage.haskell.org/trac/ghc/wiki/Commentary

• Don Stewart. Multi-paradigm Just-In-Time Compilation. BS Thesis, 2002.

Автор пробует компилировать Haskell-код в Java-код. При этом очень доступно объясняеются внутрен-

ности STG.

• Simon Marlow, Simon Peyton Jones. The Glasgow Haskell Compiler. The Architecture of Open Source

Application, Volume 2, 2012.

• Simon Marlow, Simon Peyton Jones. Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order

Languages. ICFP’04.

• Simon Peyton Jones. Implementing lazy functional languages on stock hardware: the Spineless Tagless G-

machine.

• Simon Marlow, Tim Harris, Roshan P. James, Simon Peyton Jones. Parallel Generational-Copying Garbage

Collection with a Block-Structured Heap. ISMM’08.

• Simon Peyton Jones, Andre Santos. A transformation-based optimizer for Haskell. Science of computer

programming, 1998.

322 | Приложения

• Simon Peyton Jones, John Launchbury. Unboxed values as first citizens in a non-strict functional programming

language. 1991.

• Simon Marlow, Simon Peyton Jones. Secrets of Glasgow Haskell Compiler inliner. 1999

Статья о тонкостях реализации прагмы INLINE.

• Simon Peyton Jones, Andrew Tolmach, Tony Hoare. Playing by the Rules, ICFP 2001

Статья о прагме RULES.

Встроенные проблемно-ориентированные языки (EDSL)

• Oleg Kiselyov. Implementing Explicit and Finding Implicit Sharing in EDSLs.

Чистое решение проблемы поиска дублирующих подвыражений.

• Andy Gill. Type-Safe Observable Sharing in Haskell.

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

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

• Conal Elliott, Sigbjorn Finne, Oege de Moor. Compiling Embedded Languages.

Отчёт о построении EDSL для анимации.

• Bruno C.d.S. Oliveira, Andres Loh. Abstract Syntax Graphs for Domain Specific Languages.

Применение графов для кодирования дублирующих подвыражений в EDSL.

• Jacques Carette, Oleg Kiselyov and Chung-chieh Shan. Finally Tagless, Partially Evaluated. Tagless Staged

Interpreters for Simpler Typed Languages.

Построение расширяемого синтаксиса с помощью классов типов.

• Wouter Sweistra. Data types a la carte.

Построение расширяемых типов. В этой статье и выше под словом “расширяемый” понимается возмож-

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

И все-все-все

Если вдруг у вас возникли вопросы по Haskell, и рядом с вами не оказалось того, кто мог бы на них

ответить, и в книгах нет ответа, вы можете спросить у сообщества Haskell, в haskell-cafe, там вам быстро и с

радостью ответят:

http://www.haskell.org/mailman/listinfo/haskell-cafe

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

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

Также стоит отметить журнал Monad.Reader:

http://themonadreader.wordpress.com/

Литература | 323

Обзор Hackage

Число пакетов, загруженных на Hackage, уже перевалило за 2000. В Hackage легко заблудиться. Очень

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

для использования в серьёзных приложениях. Но среди них есть и очень хорошие пакеты. Некоторые из них

включены в Haskell Platform. Ниже приведён тематический обзор наиболее популярных пакетов.

Стандартные библиотеки

Все приведённые в этом подразделе библиотеки включены в Haskell Platform.

Полный список библиотек для Haskell Platform можно посмотреть на сайте http://lambda.haskell.

org/hp-tmp/docs.

• Начало-всех-начал: base

Библиотека включает в себя все стандартные определения, например модули Prelude, Data.List,

Control.Monad и многие другие.

• Стандартные монады: transformers, mtl

Включает монады State, Writer, Reader и другие.

• Контейнеры: containers

Ассоциативные массивы, множества, последовательности, деревья.

• Массивы: array

• Графы: fgl

• Архиваторы: zlib

• Вычисление по значению: deepseq

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

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

deepseq из одноимённой библиотеки.

• Параллельное программирование: stm и parallel

• Временная арифметика, календарь: time

• Парсинг: parsec

• Регулярные выражения: regex-base, regex-posix

• Построение структурированного текста: pretty

• Тестирование программ: HUnit, QuickCheck

• Управление файловой системой: directory

• Работа с путями к файлам/директориям: filepath

• Сетевые библиотеки: network, HTTP, cgi.

• 3д Графика: OpenGL, GLUT.

• Монадные трансформеры: transformers

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

ровать несколько монад. Например, если нам нужно использовать чтение-запись в файл совместно с

изменяемым состоянием.

324 | Приложения

Эффективные типы данных

• Списки: dlist – эффективное объединение списков.

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

ровались вправо. Как в a++(b++(c++d)). Иначе время объединения из линейного превратится в квад-

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

пируются скобки при объединении. Время объединения всегда будет линейным.

• Строки: bytestring

Если ваша программа загружена обработкой строк, и работает слишком медленно, рассмотрите вари-

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

док.

• Текст: text или utf8-string

Работа с текстом в формате Unicode. Часто проблемы возникают при необходимости обработки рус-

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

из этих библиотек.

• Двоичные данные: binary или cereal – Сериализация/десериализация данных.

• Случайные числа: mersenne-random-pure64

Эффективный генератор случайных чисел.

• Ввод-вывод: iteratee

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

файлов, эта библиотека может существенно помочь.

• Контейнеры: unordered-containers

Альтернатива стандартной библиотеке containers. Эффективные типы Map и Set.

• Последовательности: fingertree, seq

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

• Массивы: vector

Эффективный тип для представления массивов. Замена стандартному типу Data.Array.

• Самые эффективные изменяемые хэш-таблицы: hashtables

• Матрицы: hmatrix, repa

Разработка программ

• Тестирование, проверка инвариантов: QuickCheck

• Оценка быстродействия: criterion

• Просмотр Core в человеческом виде: ghc-core

• Настройка сборки мусора: ghc-gc-tune

• Трассировка программ: hat

И все-все-все

• Парсинг: parsec или attoparsec

• Языки разметки: pandoc, xhtml, tagsoup, blaze-html, html

• XML: xml, HaXml

• JSON: json, aeson

• Web: happstack, snap, yesod, hakyll

• Сетевые библиотеки: network, HTTP, cgi, curl

• Графика: diagrams, gnuplot, SDL

Обзор Hackage | 325

• 3д графика: OpenGL, GLFW, GLUT

• Базы данных: HDBC

• Встраиваемые приложения реального времени с жёсткими ограничениями: atom

• GUI: wxHaskell, gtk2hs

• Оценка производительности программ: criterion

• Статистика: statistics

• Парсинг и генерация кода Haskell: haskell-src-exts

• FRP: reactive, reactive-banana, yampa

• Линейная алгебра: vector-space, hmatrix

326 | Приложения

Места

Где культивируется Haskell?

Университеты

Посмотрим на университеты, в которых Haskell преподают, развивают и применяют:

• Британия: Эдинбург, Ноттингем, Оксфорд (лаборатория информатики), Глазго.

• Америка: Йельский, Коннектикут, Техас, Оклахома, Портлэнд, Канзас

• Нидерланды: Утрехт

• Швеция: Технологический Чалмерса, Гёттинген.

• Австралия: Новый Южный Уэльс, Западной Австралии

• и другие, полный список на http://www.haskell.org/haskellwiki/Haskell_in_education.

Компании

• Microsoft Research – разрабатывают GHC.

• Galios – ведут исследования и решают практические задачи на ФП-языках, особенно на Haskell.

• Well-Typed – решают практические задачи, консультируют и всё на Haskell. Также занимаются органи-

зацией Haskell-слётов, поддержкой стандартных библиотек.

• и другие, полный список на http://www.haskell.org/haskellwiki/Haskell_in_industry

Места | 327

Document Outline

Предисловие

Структура книги

Основные понятия

Благодарности

Основы

Общая картина

Типы

Значения

Классы типов

Контекст классов типов. Суперклассы

Экземпляры классов типов

Ядро Haskell

Двумерный синтаксис

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

Упражнения

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

Интерпретатор

У-вей

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

Класс Show. Строки и символы

Строки и символы

Пример: Отображение дат и времени

Автоматический вывод экземпляров классов типов

Арифметика

Класс Eq. Сравнение на равенство

Класс Num. Сложение и умножение

Класс Fractional. Деление

Стандартные числа

Документация

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

Упражнения

Типы

Структура алгебраических типов данных

Структура констант

Несколько слов о теории графов

Строчная запись деревьев

Структура функций

Композиция и частичное применение

Декомпозиция и сопоставление с образцом

Проверка типов

Проверка типов с контекстом

Ограничение мономорфизма

Рекурсивные типы

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

Упражнения

Декларативный и композиционный стиль

Локальные переменные

where-выражения

let-выражения

Декомпозиция

Сопоставление с образцом

case-выражения

Условные выражения

Охранные выражения

if-выражения

Определение функций

Уравнения

Безымянные функции

Какой стиль лучше?

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

Упражнения

Функции высшего порядка

Обобщённые функции

Функция тождества

Константная функция

Функция композиции

Аналогия с числами

Функция перестановки

Функция on

Функция применения

Приоритет инфиксных операций

Приоритет функции композиции

Приоритет функции применения

Функциональный калькулятор

Функции, возвращающие несколько значений

Комбинатор неподвижной точки

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

Основные функции высшего порядка

Приоритет инфиксных операций

Упражнения

Функторы и монады: теория

Композиция функций

Класс Category

Специальные функции

Взаимодействие с внешним миром

Три композиции

Обобщённая формулировка категории Клейсли

Примеры специальных функций

Частично определённые функции

Многозначные функции

Применение функций

Применение функций многих переменных

Несколько полезных функций

Функторы и монады

Функторы

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

Монады

Свойства классов

Полное определение классов

Исторические замечания

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

Упражнения

Функторы и монады: примеры

Случайные числа

Конечные автоматы

Отложенное вычисление выражений

Тип Map

Накопление результата

Тип-обёртка newtype

Записи

Накопление чисел

Накопление логических значений

Накопление списков

Монада изменяемых значений ST

Тип ST

Императивные циклы

Быстрая сортировка

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

Упражнения

IO

Чистота и побочные эффекты

Монада IO

Как пишутся программы

Типичные задачи IO

Вывод на экран

Ввод пользователя

Чтение и запись файлов

Ленивое и энергичное чтение файлов

Аргументы программы

Вызов других программ

Случайные значения

Исключения

Потоки текстовых данных

Форточка в мир побочных эффектов

Отладка программ

Композиция монад

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

Упражнения

Редукция выражений

Стратегии вычислений

Преимущества и недостатки стратегий

Вычисление по необходимости

Аннотации строгости

Принуждение к СЗНФ с помощью seq

Функции с хвостовой рекурсией

Тонкости применения seq

Энергичные образцы

Энергичные типы данных

Пример ленивых вычислений

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

Упражнения

Реализация Haskell в GHC

Этапы компиляции

Язык STG

Вычисление STG

Куча

Стек

Правила общие для обеих стратегий вычисления

Правила для стратегии вставка-вход

Правила для стратегии вычисление-применение

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

Управление памятью. Сборщик мусора

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

Статистика вычислителя

Профилирование функций

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

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

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

Прагма INLINE

Прагма RULES

Прагма UNPACK

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

Упражнения

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

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

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

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

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

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

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

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

Водосборы

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

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

Упражнения

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

Свёртка

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

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

Maybe

Списки

Деревья

Развёртка

Списки

Потоки

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

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

Упражнения

Поиграем

Стратегия написания программ

Описание задачи

Набросок решения

Каркас. Типы и классы

Ленивое программирование

Пятнашки

Цикл игры

Приведём код в порядок

Формат запросов

Последние штрихи

Правила игры

Упражнения

Лямбда-исчисление

Лямбда исчисление без типов

Составление термов

Абстракция

Редукция. Вычисление термов

Рекурсия. Комбинатор неподвижной точки

Кодирование структур данных

Конструктивная математика

Расширение лямбда исчисления

Комбинаторная логика

Связь с лямбда-исчислением

Немного истории

Лямбда-исчисление с типами

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

Упражнения

Теория категорий

Категория

Функтор

Естественное преобразование

Монады

Категория Клейсли

Дуальность

Начальный и конечный объекты

Начальный объект

Конечный объект

Сумма и произведение

Экспонента

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

Упражнения

Категориальные типы

Программирование в стиле оригами

Индуктивные и коиндуктивные типы

Существование начальных и конечных объектов

Гиломорфизм

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

Упражнения

Дополнительные возможности

Пуд сахара

Сахар для списков

Сахар для монад, do-нотация

Расширения

Обобщённые алгебраические типы данных

Семейства типов

Классы с несколькими типами

Экземпляры классов для синонимов

Функциональные зависимости

Ограничение мономорфизма

Полиморфизм высших порядков

Лексически связанные типы

И другие удобства и украшения

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

Упражнения

Средства разработки

Пакеты

Создание пакетов

Создаём библиотеки

Создаём исполняемые программы

Установка пакета

Удаление библиотеки

Репозиторий пакетов Hackage

Дополнительные атрибуты пакета

Установка библиотек для профилирования

Создание документации с помощью Haddock

Комментарии к определениям

Комментарии к модулю

Структура страницы документации

Разметка

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

Упражнения

Ориентируемся по карте

Алгоритм эвристического поиска А*

Поиск маршрутов в метро

Тестирование с помощью QuickCheck

Формирование тестовой выборки

Классификация тестовых случаев

Оценка быстродействия с помощью criterion

Основные типы criterion

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

Упражнения

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

Основные библиотеки

Изменяемые значения

OpenGL

Chipmunk

Боремся с IO

Определяемся с типами

Структура проекта

Детализируем функции обновления состояния игры

Детализируем дальше

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

Упражнения

Музыкальный пример

Музыкальная нотация

Нотная запись в европейской традиции

Протокол midi

Музыкальная запись в виде событий

Преобразование событий во времени

Композиция треков

Экземпляры стандартных классов

Ноты в midi

Синонимы для нот

Перевод в midi

Пример

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

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

Упражнения

Приложения

Начало работы с Haskell

Литература

Книги

Тематический сборник

И все-все-все

Обзор Hackage

Стандартные библиотеки

Эффективные типы данных

Разработка программ

И все-все-все

Места

Университеты

Компании