Джоэла Каасинена (Nitor) и Джона Лонга (Университет Хельсинки)

9 Лекция 9: повторение части 1

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

9.1 Типы

Помните примитивные типы Хаскелла? Вот они:

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

Есть еще один мощный механизм для создания большего количества типов: Алгебраические типы данных (ADTs). Некоторые примеры включают:

-- Enumeration types
data Bool = True | False
data Color = Red | Green | Blue

-- Record types that contain fields
data Vector2d = MakeVector Double Double
data Person = Person Int String

-- Parameterized types. Note the type parameter `a`
data PairOf a = TwoValues a a

-- Recursive types
data IntList = Empty | Node Int IntList

-- Complex types which combine many of these features
data Maybe a = Nothing | Just a
data Either a b = Left a | Right b
data List a = Nil | Cons a (List a)             -- This is equivalent to the built-in [a] type
data Tree a = Leaf a | Node a (Tree a) (Tree a)
data MultiTree a = MultiTree a [MultiTree a]     -- Note the list

Ценности этих типов включают:

Вы можете комбинировать параметризованные типы сложными способами, например, с чем-то вроде Either [String->String] (Maybe String, Int).

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

[a] -> [a]    -- function from list of any type, to list of the same type
[a] -> a      -- function from list of any type, to the element type
(a,b) -> [a]  -- function from tuple to list

9.1.1 Подробнее о списках

Литералы списка могут быть написаны с использованием знакомого синтаксиса [x,y,z]. Тем не менее, эта нотация является лишь сокращением, поскольку списки фактически составлены из списков конструкторов [] и (:). Эти конструкторы также используются при сопоставлении списков шаблонов. Вот некоторые примеры списков:

Существует также синтаксис диапазона для списков:

List Comprehensions - еще один мощный способ создания списков:

В общем случае [f x | x <- xs, p x] эквивалентно map f (filter p xs). Аналогично, [y | x <- xs, let y = f x] эквивалентно [f x | x <- xs]. В генераторах списков можно сочетать <-, let и выражение результата [f x | ...].

Еще одно замечание по синтаксису. Напомним, что (:) ассоциируется справа, например, True:False:[] совпадает с True:(False:[]). (На самом деле, (True:False):[] даже не является списком, потому что True:False пытается добавить True перед False, который не является списком.)

9.2 Функции

Основной формой определения функции является:

functionName :: argumentType -> returnType
functionName argument = returnValue

Например:

repeatString :: String -> String
repeatString s = s ++ s

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

surroundString :: String -> String -> String
surroundString around s = around ++ s ++ around

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

id :: a -> a
id x = x

const :: a -> b -> a
const x y = x

flip :: (a -> b -> c) -> b -> a -> c
flip f x y = f y x

Более сложные функции могут быть определены с помощью pattern matching. Мы можем сопоставить шаблоны на конструкторах алгебраических типов данных, таких как Maybe, а также списки конструкторов [] и (:).

swap :: (a,b) -> (b,a)
swap (x,y) = (y,x)

maybe :: b -> (a -> b) -> Maybe a -> b
maybe def _ Nothing  = def
maybe _   f (Just x) = f x

safeHead :: [a] -> Maybe a
safeHead []    = Nothing
safeHead (x:_) = Just x

Еще больше изощренности можно достичь с помощью guards. Охрана позволяет определить функцию в каждом конкретном случае на основе тестов типа Bool. Охрана полезна в ситуациях, когда сопоставление шаблонов не может быть использовано. Конечно, защитные выражения (guards) также могут сочетаться с сопоставлением шаблонов:

myAbs :: Int -> Int
myAbs x
  | x < 0     = -x
  | otherwise = x

safeDiv :: Double -> Double -> Maybe Double
safeDiv x y
  | y == 0    = Nothing
  | otherwise = Just (x / y)

buy :: String -> Double -> String
buy "Banana" money
  | money < 3.2   = "You don't have enough money for a banana"
  | otherwise     = "You bought a banana"
buy product  _    = "No such product: " ++ product

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

divDefault :: Double -> Double -> Double -> Double
divDefault x y def = case safeDiv x y of
  Nothing -> def
  Just w  -> w

Выражения позволяют локальные определения где пункты работают аналогично let С. Например:

circleArea :: Double -> Double
circleArea r = let pi = 3.1415926
                   square x = x * x
               in pi * square r

circleArea' :: Double -> Double
circleArea' r = pi * square r
    where pi = 3.1415926
          square x = x * x

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

incrementAll :: [Int] -> [Int]
incrementAll xs = map (\x -> x + 1) xs

Отметим, что f x = y - это то же самое, что и f = \x -> y.

Наконец, бинарные операторы имеют sections. Секции частично применяются операторами. Раздел оператора получается путем написания оператора и одного из его аргументов в скобках. Например, (*2) умножает аргумент 2 справа, например, (*2) 5 ==> 5 * 2. Дробное число (например, Double) можно перевернуть с помощью раздела (1/), например (1/) 2 ==> 0.5.

incrementAll' :: [Int] -> [Int]
incrementAll' xs = map (+1) xs

9.3 Функциональное программирование

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

Наиболее часто представленным примером функционального программирования является манипуляция функциональным списком. функции высшего порядка (функции, которые принимают функции в качестве аргументов) map и filter Вот один пример из части 1:

-- a predicate that checks if a string is a palindrome
palindrome :: String -> Bool
palindrome str = str == reverse str

-- palindromes n takes all numbers from 1 to n, converts them to
-- strings using show, and keeps only palindromes
palindromes :: Int -> [String]
palindromes n = filter palindrome (map show [1..n])

palindromes 150
  ==> ["1","2","3","4","5","6","7","8","9",
       "11","22","33","44","55","66","77","88","99",
       "101","111","121","131","141"]

В части 1 мы встретили и другие приёмы функционального программирования, например частичное применение (partial application):

map (take 3) [[1,2,3,4,5],[6,7,8,9,0]]
  ==> [[1,2,3],[6,7,8]]

Кроме того, функциональная композиция:

(map reverse . filter (/="Smith")) ["Jones","Smith","White"]
  ==> ["senoJ","etihW"]
map (negate . sum) [[1,2,3],[5]]
  ==> [-6,-5]

И, наконец, folds:

foldr (*) 1 [2,3,4]  ==> 24
foldr max 0 [1,3,7]  ==> 7
foldr (++) "" ["abc","de","f"] ==> "abcdef"

9.4 Рекурсия

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

repeatString :: Int -> String -> String
repeatString 0 s = ""
repeatString n s = s ++ repeatString (n-1) s

times :: Int -> Int -> Int
times 0 n = 0
times 1 n = n
times m n = n + times (m - 1) n

safeLast :: [a] -> Maybe a
safeLast []     = Nothing
safeLast [x]    = Just x
safeLast (x:xs) = safeLast xs

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

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

filter :: (a -> Bool) -> [a] -> [a]
filter _    []     = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

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

sumNumbers :: [Int] -> Int
sumNumbers xs = go 0 xs
  where go sum [] = sum
        go sum (x:xs) = go (sum+x) xs

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

-- split a string into pieces at the given character
mySplit :: Char -> String -> [String]
mySplit c xs = helper [] xs
  where helper piece [] = [piece]
        helper piece (y:ys)
          | c == y    = piece : helper [] ys
          | otherwise = helper (piece++[y]) ys

mySplit '-' "a-bcd-ef"  ==>  ["a","bcd","ef"]

9.5 Классы типов

Следующие функции параметрически полиморфны (parametrically polymorphic):

id :: a -> a
id x = x

head :: [a] -> a
head (x:_) = x

fst :: (a,b) -> a
fst (x,y) = x

Параметрически полиморфные функции всегда работают одинаково, независимо от того, с какими типами мы работаем. Это означает, что мы не можем определить специальную реализацию id только для типа Int или fst для типа (Bool, String).

Напротив, ad hoc polymorphism позволяет различным типам иметь разные реализации одной и той же функции. Специальный полиморфизм в Haskell может быть достигнут путем определения класса type и последующего объявления instances этого класса для различных типов. Специальный полиморфизм является удобным способом выражения общего набора операций, даже когда реализация операций зависит от типа, на который они действуют.

Функции, использующие специальный полиморфизм, имеют ограничение -класса в своих типах. Вот несколько примеров:

negate :: Num a => a -> a
(==) :: Eq a => a -> a -> Bool
sort :: Ord a => [a] -> [a]

Тип Num a => a -> a означает: для любого типа X, который является членом класса Num, эта функция имеет тип X -> X. Другими словами, мы можем вызвать negate на любом типе номера, но не на других типах:

Prelude> negate 1
-1
Prelude> negate 1.0
-1.0
Prelude> negate True
<interactive>:3:1: error:
    • No instance for (Num Bool) arising from a use of ‘negate’

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

• сравнение
  • Eq - для сравнения равенства. Содержит оператора ==
  • Ord предназначен для сравнения заказов. Он содержит упорядоченные операторы сравнения, такие как < и =>, и функции, такие как max и min.
• Числа
  • Num Для всех типов чисел. Содержит +, -, * и negate.
  • Integral предназначен для целых типов номеров. В частности, он содержит целое подразделение div.
  • Fractional для типов номеров, поддерживающих подразделение, /
• Преобразование значений в строки
  • Show содержит функцию show :: Show a => a -> String, которая преобразует значения в строки.
  • Read содержит функцию read :: Read a => String -> a, обратную show.

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

sumTwoSmallest :: (Num a, Ord a) => [a] -> a
sumTwoSmallest xs = let (a:b:_) = sort xs
                    in a+b

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

class Sized a where
  empty :: a        -- a thing with size 0
  size :: a -> Int

class Eq a where
  (==) :: a -> a -> Bool

Рассмотрим следующие структуры данных:

data Numbers = None | One Int | Two Int Int
data IntList = Nil | ListNode Int IntList
data Tree a = Leaf | Node a (Tree a) (Tree a)

Все они имеют размеры, которые мы можем посчитать, но нам нужно выполнить операцию по-другому:

instance Sized Numbers where
  empty = None
  size None      = 0
  size (One _)   = 1
  size (Two _ _) = 2

instance Sized IntList where
  empty = Nil
  size Nil               = 0
  size (ListNode _ list) = 1 + size list

instance Sized (Tree a) where
  empty = Leaf
  size Leaf = 0
  size (Node _ left right) = 1 + size left + size right

Мы также можем легко объявить экземпляры Eq для Numbers и IntList:

instance Eq Numbers where
  None      == None       = True
  (One x)   == (One y)    = x==y
  (Two x y) == (Two z w)  = x==z && y==w
  _         == _          = False         -- to handle cases like None == One 1

instance Eq IntList where
  Nil             == Nil               = True
  (ListNode x xs) == (ListNode y ys)   = x == y && xs == ys
  _               == _                 = False

Однако, поскольку тип данных Tree параметризован по типу элемента a, нам нужен экземпляр Eq a, чтобы иметь экземпляр Eq (Tree a). Это достигается путем добавления классового ограничения к декларации экземпляра. Это называется иерархия instance..

instance Eq a => Eq (Tree a) where
  Leaf         == Leaf              = True
  (Node x l r) == (Node x' l' r')   = x == x' && l == l' && r == r'
  _            == _                 = False

9.5.1 Автоматический вывод экземпляров (deriving)

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

data Numbers = None | One Int | Two Int Int
  deriving (Show, Read, Eq, Ord)

None == One 1       ==> False
Two 1 2 == Two 1 2  ==> True
None < Two 1 2      ==> True
Two 1 3 < Two 1 2   ==> False
show (Two 1 3)      ==> "Two 1 3"

9.6 Викторина

Что такое тип ('c',not)

1. [Char]
2. [Bool]
3. (Char,Bool -> Bool)
4. (Char,Bool)
5. Это ошибка типа.

Что такое тип ['c',not]

1. [Char]
2. [Bool]
3. (Char,Bool -> Bool)
4. (Char,Bool)
5. Это ошибка типа.

Какое из них является значением следующего типа?

data T = X Int | Y String String | Z T

1. X "foo"
2. Y "foo"
3. Z (X 1)
4. X (Z 1)

Каков тип этой функции?

f (_:Just x:_) = x
f _            = False

1. Maybe a -> a
2. [Maybe a] -> a
3. [Maybe a] -> Bool
4. [Maybe Bool] -> Bool

Каков тип этой функции?

f x y = x-y == 0

1. (Num a, Eq a) => a -> a -> Bool
2. Num a => a -> a -> Bool
3. Eq a => a -> a -> Bool
4. a -> a -> Bool

Какой из следующих типов может быть у x, чтобы x (&&) y не было ошибкой типа?

1. Bool
2. Bool -> Bool -> Bool
3. (Bool -> Bool -> Bool) -> Bool -> Bool

9.7 Работа над упражнениями

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

1. Клонируйте репозиторий GitHub: https://github.com/moocfi/haskell-mooc
2. Перейдите в каталог exercises/
3. Запустите stack build, чтобы загрузить зависимости
4. Отредактируйте файл Set9a.hs
5. Проверьте свои ответы с помощью stack runhaskell Set9aTest.hs
6. Отправьте ответы на официальной странице отправки
7. Повторяйте по мере необходимости. Наборы упражнений можно выполнять в любом порядке и отправлять сколько угодно раз.
8. Общий балл доступен на официальной странице статуса

9.8 Упражнения

• Set9a - небольшие Упражнения, которые повторяют часть 1 курса
• Set9b - давайте решим головоломку N Queens!

10 Лекция 10: Редукционизм

• чистота
• лень
• Оценка Haskell

10.1 Ленивость и чистота

Чистота и лень упоминались как ключевые черты Хаскелла в начале части 1. Давайте рассмотрим их поближе.

Haskell — чистый (pure) функциональный язык. Это означает, что значение f x y при заданных x и y всегда одно и то же. Иными словами, значения x и y однозначно определяют значение f x y. Это свойство также называют ссылочной прозрачностью (referential transparency).

Чистота также означает отсутствие побочных эффектов: вычисление f x y не может, например, прочитать строку от пользователя. При разных вызовах f строка могла бы отличаться и влиять на возвращаемое значение, нарушая ссылочную прозрачность. Разумеется, побочные эффекты необходимы для полезной работы программы. Позже мы разберём, как Haskell с ними справляется.

Haskell — ленивый (lazy) язык: значение не вычисляется, пока оно не понадобится. Лучше всего это видно на примере. Рассмотрим две функции:

f x = f x   -- infinite recursion
g x y = x

Оценка f 1 не прекращается из-за бесконечной рекурсии. Однако это работает:

g 2 (f 1)  ==>  2

Лень не является проблемой, потому что Хаскелл чист. Только результат функции имеет значение, а не побочные эффекты. Поэтому, если результат функции не используется, мы просто не можем оценить его без изменения значения (семантики) программы. Хорошо, иногда мы получаем программу прекращения вместо той, которая продолжается вечно, но добавление лени никогда не делает функциональную программу Haskell перерывом.

Если вас интересует теория, лежащая в основе этого, ознакомьтесь с теоремой Church-Rosser или статьей Haskell Wiki «Ленивость и нестрогость» (Lazy vs. non-strict).

10.2 Рассуждения с помощью равенств

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

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

int c = 0;
int funny(int x) {
  return x + c++;
}

Выражение c++ увеличивает значение c и возвращает старое значение c. В следующий раз, когда она будет оценена, значение c увеличилось на единицу. Это означает, что в зависимости от текущего значения c, funny(0) может возвращать 0, 1, 2 или любое другое целое значение. (Это может даже вернуть отрицательные значения, если c переполнится!)

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

Рассмотрим следующее выражение:

map (+1) . reverse . map (-1)

Это выражение можно упростить до reverse. Мы начинаем с установления некоторых полезных фактов (или lemmas). Прежде всего, предположим, что мы знаем

1. map id === id
2. map f . map g === map (f.g)
3. reverse . map f === map f . reverse

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

4. (+1) . (-1) === id

Мы можем доказать факт 4, рассуждая о том, как (+1) . (-1) Поведение для произвольного ввода x:

((+1) . (-1)) x === ((+1) ((-1) x))
                === ((+1) (x - 1))
                === (x - 1) + 1
                === x
                === id x

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

(+1) . (-1) === id

Если вы знакомы с доказательством по индукции (proof by induction), попробуйте в качестве упражнения доказать первые три утверждения. Индукционные доказательства не входят в этот курс, поэтому незнание индукции не помешает дальнейшему обучению.

Из фактов 1-4 следует, что

    map (+1) . reverse . map (-1)
=== map (+1) . (reverse . map (-1))    -- By associativity of (.)
=== map (+1) . (map (-1) . reverse)    -- By fact 3
=== (map (+1) . map (-1)) . reverse    -- By associativity of (.)
=== map ((+1) . (-1)) . reverse        -- By fact 2
=== map id . reverse                   -- By fact 4
=== id . reverse                       -- By fact 1
=== reverse                            -- By the definition of id

Этот курс не будет вдаваться в подробности о доказательстве вещей о программах, но хорошо знать, что чисто функциональное программирование очень совместимо с таким анализом. [+]

10.3 Бесконечные списки

Преимущества лени лучше всего демонстрируют некоторые примеры с участием infinite lists. Начнем с repeat 1, который генерирует бесконечный список 1. Если мы попытаемся сказать GHCi напечатать значение repeat 1, он просто будет продолжать печатать 1 вечно, пока мы не прервем его с помощью Control-C:

Prelude> repeat 1
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
^C

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

Prelude> take 10 $ repeat 1
[1,1,1,1,1,1,1,1,1,1]
Prelude> take 20 $ repeat 1
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
Prelude> repeat 1 !! 13337
1

Бесконечный список, который просто повторяет один элемент, иногда может быть необходим, но это бессмысленно. Рассмотрим несколько более полезных бесконечных списков. Вы можете использовать синтаксис [n..] для создания бесконечного списка чисел, начиная с n:

Prelude> take 20 [0..]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]
Prelude> take 10 . map (2^) $ [0..]
[1,2,4,8,16,32,64,128,256,512]

Функция cycle повторяет элементы из данного списка снова и снова. Это может быть полезно при работе с вращениями или циклами.

Prelude> take 21 $ cycle "asdf"
"asdfasdfasdfasdfasdfa"
Prelude> take 4 . map (take 4) . tails $ cycle "asdf"
["asdf","sdfa","dfas","fasd"]

10.3.1 Пример: номера транзакций

В качестве более конкретного примера того, как cycle полезен, давайте рассмотрим вычисление контрольной цифры финских номеров транзакций банковских переводов (viitenumero). Номер транзакции состоит из произвольного количества цифр и одной контрольной цифры в конце. Для проверки остальные цифры справа налево умножают поочерёдно на 7, 3, 1, 7, 3, 1 и так далее, после чего складывают произведения. Если сумма вместе с контрольной цифрой делится на 10, номер считается корректным.

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

digits:       1  1  6  1  2
              *  *  *  *  *
multipliers:  3  7  1  3  7
              3+ 7+ 6+ 3+14 = 33
check digit is 7, 33+7=40 is divisible by 10, valid

Вот код Haskell для проверки номера транзакции. Обратите внимание, как мы используем бесконечный список cycle [7,3,1] для множителей.

viitenumeroCheck :: [Int] -> Bool
viitenumeroCheck allDigits = mod (checksum+checkDigit) 10 == 0
  where (checkDigit:digits) = reverse allDigits
        multipliers = cycle [7,3,1]
        checksum = sum $ zipWith (*) multipliers digits

viitenumeroCheck [1,1,6,1,2,7]  ==> True
viitenumeroCheck [1,1,6,1,2,8]  ==> False

10.3.2 Пример: возведение в степень

Наконец, вот как вы найдете первую мощность 3, которая больше 100.

Prelude> head . filter (>100) $ map (3^) [0..]
243

Давайте рассмотрим, как это работает шаг за шагом. Обратите внимание, как карта и фильтр обрабатывают список лениво, по одному элементу за раз. Это похоже на то, как generators или iterators работают на таких языках, как Python или Java.

    head (filter (>100) (map (3^) [0..]))
==> head (filter (>100) (map (3^) (0:[1..])))   -- evaluate first element of the lazy list
==> head (filter (>100) (1 : map (3^) [1..]))   -- map processes the element
==> head (filter (>100) (map (3^) [1..]))       -- filter drops the element
==> head (filter (>100) (map (3^) (1:[2..])))   -- evaluate second element of the lazy list
==> head (filter (>100) (3 : map (3^) [2..]))   -- map processes the element
==> head (filter (>100) (map (3^) [2..]))       -- filter drops the element
-- let's take bigger steps now
==> head (filter (>100) (9 : map (3^) [3..]))   -- map processes, filter will drop
==> head (filter (>100) (27 : map (3^) [4..]))  -- map processes, filter will drop
==> head (filter (>100) (81 : map (3^) [5..]))  -- map processes, filter will drop
==> head (filter (>100) (243 : map (3^) [6..])) -- map processes
==> head (243 : filter (>100) (map (3^) [6..])) -- filter lets the value through
==> 243                                         -- head returns the result

10.4 Как работает Haskell?

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

В большинстве других языков программирования (таких как Java, C или Python) оценка продолжается снаружи. Аргументы функций оцениваются перед функцией.

Оценка Haskell происходит снаружи, а не снаружи. Определение внешней функции в выражении применяется без оценки каких-либо аргументов. Вот конкретный пример с игрушечными функциями f и g:

g :: Int -> Int -> Int
g x y = y+1
f :: Int -> Int -> Int -> Int
f a b c = g (a*1000) c

Внутренняя (нормальная) оценка:

f 1 (1234*1234) 2
  -- evaluate arguments to f
  ==> f 1 1522756 2
  -- evaluate f
  ==> g (1*1000) 2
  -- evaluate arguments to g
  ==> g 1000 2
  -- evaluate g
  ==> 2+1
  ==> 3

Хаскелл вне оценки:

f 1 (1234*1234) 2
  -- evaluate f without evaluating arguments
  ==> g (1*1000) 2
  -- evaluate g without evaluating arguments
  ==> 2+1
  ==> 3

Обратите внимание, что неиспользованные расчеты 1234*1234 и 1*1000 не были оценены. Вот почему лень часто бывает полезной.

10.4.1 Сопоставление с образцом запускает вычисления

Давайте рассмотрим более сложный пример с сопоставлением шаблонов и более сложными данными (списками). Соответствие шаблона приводит к оценке Haskell очень конкретным образом, как мы увидим. Вот некоторые функции, которые мы будем использовать. Они знакомы из Прелюдии, но я дам им простые определения.

not True = False
not False = True
map f [] = []
map f (x:xs) = f x : map f xs
length [] = 0
length (x:xs) = 1+length xs

Вот внутренняя оценка выражения:

length (map not (True:False:[]))
  ==> length (not True : not False : [])  -- evaluate call to map
  ==> length (False:True:[])              -- evaluate calls to not
  ==> 2

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

length (map not (True:False:[]))
  -- We can't evaluate length since we don't know which equation of length applies,
  -- so we look at length's argument. We can apply the second equation of map, so we do.
  ==> length (not True : map not (False:[]))
  -- Now the argument of length has a (:) we can pattern match on, so we apply the
  -- second equation of length
  ==> 1 + length (map not (False:[]))
  -- The outermost function is now +, but it can't do anything unless both arguments
  -- are numbers. So we need to evaluate length. In order to pick an equation, we need
  -- to evaluate the argument of length again. We apply the second equation of map
  ==> 1 + length (not False : map not ([]))
  -- Now we can apply the second equation of length again.
  ==> 1 + (1 + length (map not []))
  -- The outermost + needs a number to be evaluated. The second + also needs a number.
  -- We need to evaluate length again, which means we need to pick an equation for length,
  -- which means we need to evaluate its argument. This time it is the first equation for
  -- map that applies.
  ==> 1 + (1 + length [])
  -- Now we can apply the first equation for length
  ==> 1 + (1 + 0)
  -- The outermost + still can't be evaluated, but the inner one can
  ==> 1 + 1
  -- Finally we evaluate the outer +
  ==> 2

Обратите внимание, что нам не нужно было оценивать какие-либо приложения not.

Введём несколько терминов. Говорят, что сопоставление с образцом форсирует (forces) вычисление. Haskell вычисляет значение до слабой головной нормальной формы (weak head normal form, WHNF). По сути, WHNF — это значение, с которым уже можно сопоставить образец. Выражение находится в WHNF, если его нельзя вычислить дальше на верхнем уровне. Отсюда следует:

• является постоянной, например: 1
• Имеет конструктор на высшем уровне, например: False, Just (1+1), 0:filter f xs
• является функцией, например: (\x -> 1+x)

Наиболее заметным классом выражений, который является not в WHNF, являются функциональные приложения. Если выражение состоит из функции (то есть не является конструктором), применяемой к некоторым аргументам, то оно не в WHNF. Мы должны оценить его, чтобы получить что-то сопоставимое.

В предыдущем примере мы не могли выбрать уравнение для length в length (map not (False:[])). Аргумент (map not ...) отсутствует в WHNF, поэтому его нельзя сопоставить с шаблоном. Поэтому мы должны его оценить. Когда мы применяем второе уравнение map, мы получаем length (not False : map not []), и теперь аргумент в пользу длины находится в WHNF, поскольку на верхнем уровне находится конструктор (:). Это немного более очевидно, если мы перейдем от инфикса к префиксной записи и напишем аргумент length как (:) (not False) (map not []).

На практике сопоставление шаблонов — не единственное, что заставляет оценивать. Примитивисты, такие как (+), также приводят свои аргументы.

Вместо того, чтобы заставлять, некоторые источники говорят о строгость Например, мы можем сказать, что (+) это Строго в обоих аргументах.

10.4.2 Несколько слов о разделении вычислений (sharing)

Есть еще одна вещь об оценке Хаскелла. Каждый раз, когда вы даете значение name, он получает shared. Это означает, что каждое появление имени указывает на одно и то же (потенциально неоцененное) выражение. Когда выражение оценивается, все вхождения имени видят результат.

Давайте рассмотрим очень простой пример.

square x = x*x

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

square (2+2)
  ==> (2+2) * (2+2)   -- definition of square
  ==>   4   * (2+2)   -- (*) forces left argument
  ==>   4   *   4     -- (*) forces right argument
  ==>      16         -- definition of (*)

На самом деле выражение 2+2, которому дали имя x, вычисляется лишь один раз. Затем полученный результат используется в обоих вхождениях x внутри square. Ниже показано корректное вычисление — сначала текстом, затем графически. Теперь вместо дерева выражений получается граф выражений, поэтому модель вычислений Haskell иногда называют уменьшение графа.

square (2+2)
  ==> (2+2) * (2+2)
  ==>   4   *   4
  ==>      16

В качестве другого примера рассмотрим функцию f ниже и ее оценку.

f :: Int -> Int
f i = if i>10 then 10 else i

                  _______shared________
                 |                     |
f (1+1) ==> if (1+1)>10 then 10 else (1+1)
        ==> if 2>10 then 10 else 2
        ==> if False then 10 else 2
        ==> 2

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

g :: Int -> Int -> Int
g i j = if i>10 then 10 else j

                        ______no sharing_____
                       |                     |
g (1+1) (1+1) ==> if (1+1)>10 then 10 else (1+1)
              ==> if 2>10 then 10 else (1+1)
              ==> if False then 10 else (1+1)
              ==> (1+1)
              ==> 2

Здесь у нас есть два разных имени для эквивалентных выражений, и Хаскелл волшебным образом не делится ими. Автоматически совместное использование эквивалентных выражений называется оптимизацией Common Subexpression Elimination (CSE). Узнать немного больше CSE и Haskell можно здесь.

Вы можете назвать вещи через

• Функциональные аргументы
• let ... in ...
• where

В сочетании с ленью обмен означает, что Имя оценивается не более одного раза.

10.4.3 Дополнительные примеры

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

not :: Bool -> Bool
not True = False
not False = True

(||) :: Bool -> Bool -> Bool
True || _ = True
_    || x = x

even :: Int -> Bool
even x  =  (x == 0)  ||  not (even (x-1))

Сначала заметим, что || форсирует левый аргумент, но не правый. Иными словами, || строг по левому аргументу (strict in its left argument). Чтобы выбрать подходящее уравнение, достаточно вычислить левый аргумент ||. Следовательно, even форсирует свой первый аргумент:

• || вытесняет x==0
• x==0 вытесняет x

Теперь давайте оценим выражение even 2 по WHNF.

even 2
==> 2 == 0  ||  not (even (2-1))                    -- apply definition of even
==> False   ||  not (even (2-1))                    -- || forces its first argument
==> not (even (2-1))                                -- second equation of ||
==> not ((2-1) == 0 || not (even ((2-1)-1)))        -- not forces its argument: apply definition of even
==> not (  1   == 0 || not (even (  1  -1)))        -- note sharing!
==> not (  False    || not (even (1-1)))
==> not (not (even (1-1)))
==> not (not ((1-1) == 0 || not (even ((1-1)-1))))
==> not (not (  0   == 0 || not (even (  0  -1))))  -- (sharing)
==> not (not (   True    || not (even (0-1))))
==> not (not True)
==> not False
==> True

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

even' x =  not (even' (x-1))  ||  x == 0

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

head (x:_) = x
head [] = -1

filter p [] = []
filter p (x:xs) = if p x
                  then x : filter p xs
                  else filter p xs

map f [] = []
map f (x:xs) = f x : map f xs

-- [0..] is syntax sugar for enumFrom 0
enumFrom n = n : enumFrom (n+1)

А вот и мы:

    head (filter (>100) (map (3^) [0..]))
=== head (filter (>100) (map (3^) (enumFrom 0)))
-- head forces filter, which forces map, which forces enumFrom. We apply the definition of enumFrom.
==> head (filter (>100) (map (3^) (0:[1..])))
-- head forces filter, which forces map. We apply the second equation of map.
==> head (filter (>100) ((3^0) : map (3^) [1..]))
-- head forces filter. We apply the second equation of filter
==> head (if ((3^0)>100)
          then (3^0) : filter (>100) (map (3^) [1..])
          else filter (>100) (map (3^) [1..]))
-- head forces if, if forces >, > forces ^. Note sharing!
==> head (if (1>100)
          then 1 : filter (>100) (map (3^) [1..])
          else filter (>100) (map (3^) [1..]))
-- head forces if, if forces >
==> head (if False
          then 1 : filter (>100) (map (3^) [1..])
          else filter (>100) (map (3^) [1..]))
-- apply definition of if
==> head (filter (>100) (map (3^) [1..]))
-- let's take slightly bigger steps now
==> head (filter (>100) (map (3^) (1:[2..])))
==> head (filter (>100) ((3^1) : map (3^) [2..]))
==> head (filter (>100) (3 : map (3^) [2..]))
==> head (filter (>100) (map (3^) [2..]))
-- and even bigger steps now
==> head (filter (>100) (9 : map (3^) [3..]))
==> head (filter (>100) (27 : map (3^) [4..]))
==> head (filter (>100) (81 : map (3^) [5..]))
==> head (filter (>100) (243 : map (3^) [6..]))
==> head (243 : filter (>100) (map (3^) [6..]))
==> 243

Вуу.

10.5 Работа с бесконечными списками

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

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

everySecond :: [a] -> [a]
everySecond [] = []
everySecond (x:y:xs) = x : everySecond xs

take 10 (everySecond [0..])  ==>  [0,2,4,6,8,10,12,14,16,18]

Хорошая эвристика для написания функций, которые хорошо работают с бесконечными списками, заключается в следующем: может ли head результата быть оценено дешево? Вот два примера функций, которые не работают с бесконечными входами. В случае с mapTailRecursive проблема заключается в том, что перед тем, как войти в WHNF, он должен обработать весь вход. В случае с myDrop проблема заключается в том, что он использует функцию length, которая не работает для бесконечных списков.

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

mapTailRecursive :: (a -> b) -> [a] -> [b]
mapTailRecursive f xs = go xs []
    where go (x:xs) res = go xs (res++[f x])
          go []     res = res

head (map succ [0..]) ==> head (succ 0 : map succ [1..]) ==> succ 0 ==> 1
head (mapTailRecursive succ [0..])
  ==> head (go [0..] [])
  ==> head (go [1..] ([]++[succ 0]))
  ==> head (go [2..] ([]++[succ 0]++[succ 1]))
  ==> head (go [3..] ([]++[succ 0]++[succ 1]++[succ 2]))
  --  never terminates

drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
drop n (x:xs) = drop (n-1) xs

myDrop :: Int -> [a] -> [a]
myDrop 0 xs = xs
myDrop n xs = if n > length xs then [] else myDrop (n-1) (tail xs)

head (drop 2 [0..]) ==> head (drop 1 [1..]) ==> head (drop 0 [2..]) ==> head [2..] ==> 2
head (myDrop 2 [0..])
  ==> head (if n > length [0..] then [] else myDrop (n-1) (tail [0..]))
  ==> head (if n > 1+length [1..] then [] else myDrop (n-1) (tail [0..]))
  ==> head (if n > 1+1+length [2..] then [] else myDrop (n-1) (tail [0..]))
  ==> head (if n > 1+1+1+length [3..] then [] else myDrop (n-1) (tail [0..]))
  --  never terminates

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

head (takeWhile (>=0) [0..]) ==> 0
head (concat (repeat [1,2,3])) ==> 1
head (zip [0..] [2..]) ==> (0,2)
head (filter even [3..]) ==> 4

10.6 Интерлюдия: добавляем строгость

Помните foldr из части 1? Рассмотрим родственную функцию foldl. Ниже приведено определение foldl для списков; на самом деле она входит в класс типов Foldable и работает также с другими структурами. foldr обрабатывает список справа налево, а foldl — слева направо. Точнее, foldr правоассоциативна, тогда как foldl левоассоциативна. Сравните:

foldr (+) 0 [1,2,3]  ==>  1+(2+(3+0))
foldl (+) 0 [1,2,3]  ==>  ((0+1)+2)+3

Вот определения foldl и foldr:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f y []     = y
foldr f y (x:xs) = f x (foldr f y xs)

Как foldr f y (x:xs) ==> f x (foldr f y xs), он позволяет ленивым оценкам сосредоточиться на f на втором этапе. Таким образом, foldr хорошо работает с ленивыми или короткозамыкающими операциями:

    foldr (&&) True [False,False,False]
==> False && (foldr (&&) True [False,False])
==> False

    head (foldr (++) [] ["Hello","World","lorem","ipsum"])
==> head ("Hello" ++ (foldr (++) [] ["World","lorem","ipsum"]))
==> head ('H':("ello" ++ (foldr (++) [] ["World","lorem","ipsum"])))
==> 'H'

Однако foldl необходимо обработать весь список, чтобы получить значение WHNF. Причина в том, что foldl остается в самой левой позиции до тех пор, пока его аргументы в списке остаются пустыми. Это делает foldl приоритетом для ленивых оценок. Только после того, как список становится пустым, оценка переходит к упрощению сложенных значений.

    foldl (&&) True [False,False,False]
==> foldl (&&) (True&&False) [False,False]
==> foldl (&&) ((True&&False)&&False) [False]
==> foldl (&&) (((True&&False)&&False)&&False) []
==> ((True&&False)&&False)&&False
==> (    False    &&False)&&False
==>              False    &&False
==>                      False

    head (foldl (++) [] ["Hello","World","lorem","ipsum"])
==> head (foldl (++) ([]++"Hello") ["World","lorem","ipsum"])
==> head (foldl (++) (([]++"Hello")++"World") ["lorem","ipsum"])
==> head (foldl (++) ((([]++"Hello")++"World")++"lorem") ["ipsum"])
==> head (foldl (++) (((([]++"Hello")++"World")++"lorem")++"ipsum") [])
==> head (((([]++"Hello")++"World")++"lorem")++"ipsum")
-- head forces the last ++, which forces the next-to-last ++, and so on
==> head ((("Hello"++"World")++"lorem")++"ipsum")
-- same happens again
==> head ((('H':("ello"++"World"))++"lorem")++"ipsum")
-- for clarity, let's drop the "ello"++"World" expression which isn't needed
==> head ((('H':__)++"lorem")++"ipsum")
-- now the next-to-last ++ can operate
==> head (('H':(__++"lorem"))++"ipsum")
-- let's drop the __++"lorem" expression
==> head (('H':__)++"ipsum")
-- now the last ++ can operate
==> head ('H':(__++"ipsum"))
==> 'H'

Так зачем вообще использовать foldl? Вернемся к нашему первому примеру. Теперь, поскольку + является строгой операцией, оба типа сгиба должны создавать выражение с большим количеством +. Реализация Haskell должна отслеживать это выражение в памяти, поэтому такая проблема называется space leak.

    foldr (+) 0 [1,2,3]
==> 1 + foldr (+) 0 [2,3]
==> 1 + (2 + foldr (+) 0 [3])
==> 1 + (2 + (3 + foldr (+) 0 []))
==> 1 + (2 + (3 + 0))
==> 1 + (2 + 3)
==> 1 + 5
==> 6

    foldl (+) 0 [1,2,3]
==> foldl (+) (0+1) [2,3]
==> foldl (+) ((0+1)+2) [3]
==> foldl (+) (((0+1)+2)+3) []
==> ((0+1)+2)+3
==> (  1  +2)+3
==>       3  +3
==>          6

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

    foldl' (+) 0 [1,2,3]
==> foldl' (+) (0+1) [2,3]
-- force second argument
==> foldl' (+) 1 [2,3]
==> foldl' (+) (1+2) [3]
-- force second argument
==> foldl' (+) 3 [3]
==> foldl' (+) (3+3) []
-- force second argument
==> foldl' (+) 6 []
==> 6

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

Вы можете найти foldl' в Data.List Модуль, и он работает именно так. Но как можно реализовать foldl' Мы точно знаем, как это сделать для определенного типа, скажем. Int Мы просто добавляем совпадение шаблонов на второй аргумент, который не изменяет семантику функции.

foldl'Int :: (Int -> Int -> Int) -> Int -> [Int] -> Int
foldl'Int f z [] = z
foldl'Int f 0 (x:xs) = foldl'Int f (f 0 x) xs
foldl'Int f z (x:xs) = foldl'Int f (f z x) xs

    foldl'Int (+) 0 [1,2,3]
==> foldl'Int (+) (0+1) [2,3]
-- to be able to pick between the second and third equations, (0+1) is forced
==> foldl'Int (+) 1 [2,3]
-- the third equation applies
==> foldl'Int (+) (1+2) [3]
-- again, we need to pick between the second and third equations
==> foldl'Int (+) 3 [3]
==> foldl'Int (+) (3+3) []
==> 3+3
==> 6

Для написания общей реализации foldl' необходимо ввести новую встроенную функцию seq. Звонок seq a b оценивает b, но вынуждает a войти в WHNF. Вот несколько примеров использования seq в GHCi. Чтобы продемонстрировать то, что оценивается, мы используем специальное значение undefined, которое вызывает ошибку, если что-то пытается оценить его в WHNF.

Prelude> seq (not True) 3
3
Prelude> seq undefined 3
*** Exception: Prelude.undefined
Prelude> (seq (not True) 3) + 7
10
Prelude> (seq undefined 3) + 7
*** Exception: Prelude.undefined
Prelude> let f x = f x in seq (f 3) 3
-- ...infinite recursion

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

strictHead :: [a] -> a
strictHead xs = seq (last xs) (head xs)

Давайте поиграем с ним в GHCi:

Prelude> head [1,2,3]
1
Prelude> strictHead [1,2,3]
1
Prelude> head (1:2:undefined)
1
Prelude> strictHead (1:2:undefined)
*** Exception: Prelude.undefined
Prelude> head [1..]
1
Prelude> strictHead [1..]
-- ...infinite recursion

Наконец, вот определение для foldl'. Обратите внимание, как нам нужно ввести совместное использование новой переменной, z', чтобы seq мог оценить новое значение, а затем использовать его в рекурсивном вызове. Новое определение также используется в более подробной оценке foldl' (+) 0 [1,2,3] ниже.

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f z [] = z
foldl' f z (x:xs) = let z' = f z x
                    in seq z' (foldl' f z' xs)

    foldl' (+) 0 [1,2,3]
==> seq (0+1) (foldl' (+) (0+1) [2,3])  -- seq forces first argument
          |                 |
          +-----sharing-----'
          |                 |
==> seq   1   (foldl' (+)   1   [2,3])  -- first argument to seq in WHNF, seq disappears
==> foldl' (+) 1 [2,3]
==> seq (1+2) (foldl' (+) (1+2) [3])
==> seq   3   (foldl' (+)   3   [3])
==> foldl' (+)   3   [3]
==> seq (3+3) (foldl' (+) (3+3) [])
==> seq   6   (foldl' (+)   6   [])
==> foldl' (+)   6   []
==> 6

Мы не будем углубляться в эту тему на этом курсе, но важно, чтобы вы знали, что seq существует. Подробнее об seq можно узнать на Haskell Wiki, а о том, когда нужна строгость, — в книге Real World Haskell. Часто лучше использовать шаблоны bang вместо seq, как обсуждается FPComplete и Real World Haskell.

10.7 Объявления newtype

Вспомните лекцию 7. Иногда нужны коробочные типы. Есть специальное ключевое слово newtype Можно использовать вместо data Когда нужен тип коробки. newtype Мы ожидаем одного строителя, с одним полем. Например,

newtype Money = Cents Int

Тем не менее, следующие не будут работать, вам нужно data:

-- the compiler won't accept these!
newtype Currency = Dollars Int | Euros Int
newtype Money = Money Int Int

Так в чем разница? С точки зрения написания кода, ничего. Вы работаете с newtype точно так же, как с data. Однако макет памяти отличается. С помощью data вводится косвенный слой (конструктор), а с помощью newtype – нет. Опосредование для data необходимо для поддержки нескольких конструкторов и нескольких полей. Иллюстрация:

code:                                 memory:

data Money = Cents Int                x --> Cents --> 100
x = Cents 100


newtype Money = Cents Int             x --> 100
x = Cents 100

Эта разница имеет много последствий. Прежде всего, newtype более эффективен: при компиляции тип можно сказать «исчезает». Тип все еще проверяется, поэтому вы получаете безопасность типа без какого-либо воздействия на производительность. Во-вторых, новинками являются strict. Конкретно это означает, что Money x находится в слабой нормальной форме головы, только если x находится в WHNF. Это можно увидеть в GHCi:

-- if we use data, Cents undefined is in WHNF
Prelude> data Money = Cents Int
Prelude> seq (Cents undefined) True
True
-- if we use newtype, Cents undefined isn't in WHNF, and trying
-- to make it so trips up in undefined
Prelude> newtype Money = Cents Int
Prelude> seq (Cents undefined) True
*** Exception: Prelude.undefined

Когда следует использовать newtype? В общем, лучше всего использовать newtype, когда у вас есть однопользовательский одноконструкторный тип данных. Однако ничто не пойдет катастрофически неправильно, если вы всегда используете data. Модель newtype также часто используется, когда вам нужно определить другой экземпляр класса типа для типа. Вот пример, который определяет тип числа с перевернутым заказом.

newtype Inverted = Inverted Int
  deriving (Show, Eq)

instance Ord Inverted where
  compare (Inverted i) (Inverted j) = compare j i

Prelude Data.List> sort [1,2,3]
[1,2,3]
Prelude Data.List> sort [Inverted 1,Inverted 2,Inverted 3]
[Inverted 3,Inverted 2,Inverted 1]

10.8 Что-то интересное: завязываем узел (Tying the Knot)

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

Prelude> take 21 $ cycle "asdf"
"asdfasdfasdfasdfasdfa"

Вот как это выглядит в памяти:

Ранее сообщалось, что формы данных Haskell направляли графы в память. Это пример направленного графа с циклом.

Как можно определить такие структуры? Мы просто даем значение имени и ссылаемся на это имя в самой стоимости. То есть значение recursive или self-referential. Этот трюк известен как tying knot. Простой пример:

  code                     memory

let xs = 1:2:xs      xs -> (1:) -> (2:) -+
 in xs                      ^            |
                            +------------+

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

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

data Room = Room String [(String,Room)]

describe :: Room -> String
describe (Room s _) = s

move :: Room -> String -> Maybe Room
move (Room _ directions) direction = lookup direction directions

world :: Room
world = meadow
  where
    meadow = Room "It's a flowery meadow next to a cliff." [("Stay",meadow),("Enter cave",cave)]
    cave = Room "You are in a cave" [("Exit",meadow),("Go deeper",tunnel)]
    tunnel = Room "This is a very dark tunnel. It seems you can either go left or right."
                  [("Go back",cave),("Go left",pit),("Go right",treasure)]
    pit = Room "You fall into a pit. There is no way out." []
    treasure = Room "A green light from a terminal fills the room. The terminal says <<loop>>."
                    [("Go back",tunnel)]

play :: Room -> [String] -> [String]
play room [] = [describe room]
play room (d:ds) = case move room d of Nothing -> [describe room]
                                       Just r -> describe room : play r ds

Prelude> play world ["Stay","Enter cave","Go deeper","Go back","Go deeper","Go right"]
["It's a flowery meadow next to a cliff.",
 "It's a flowery meadow next to a cliff.",
 "You are in a cave",
 "This is a very dark tunnel. It seems you can either go left or right.",
 "You are in a cave",
 "This is a very dark tunnel. It seems you can either go left or right.",
 "A green light from a computer terminal floods the room. The terminal says <<loop>>."]

Вот как выглядит world игры в памяти:

               ,-----------------,
               v                 |
         +-----------------------|-----------------+
meadow-->|Room "It's..." ["Stay" o, "Enter cave" o]|
         +---------------------------------------|-+
                                    ^            v
         +--------------------------|----------------+
cave---->|Room "You are..." ["Exit" o, "Go deeper" o]|
         +-----------------------------------------|-+
                                       ^           v
         +-----------------------------|----------------------------+
tunnel-->|Room "This is..." ["Go back" o, "Go left" o, "Go right" o]|<--------,
         +------------------------------------------|-------------|-+         |
                                                    |             |           |
                     ,------------------------------'             |           |
                     v                                            v           |
         +---------------------+                +-----------------------------|-+
pit----->|Room "You fall..." []|    treasure--->|Room "A green..." ["Go back" o]|
         +---------------------+                +-------------------------------+

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

10.9 Что-то интересное: Debug.Trace

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

Мы можем использовать функцию trace :: String -> a -> a из модуля Debug.Trace, чтобы заглянуть в оценку Haskell. Выражение trace "message" x такое же, как и x, но печатает message при его оценке. Мы можем использовать trace, чтобы засвидетельствовать лень оператора ||:

Prelude> import Debug.Trace
Prelude Debug.Trace> trace "a" True
a
True
Prelude Debug.Trace> trace "a" False || trace "b" True
a
b
True
Prelude Debug.Trace> trace "a" True || trace "b" True
a
True

Мы также можем посмотреть, когда оцениваются элементы списка. Обратите внимание, что length не нуждается в оценке элементов списка, и sum должен оценить их все. (Чтобы быть точным, head xs фактически не оценивает первый элемент xs, но возвращает его в GHCi, который оценивает его, чтобы показать его.)

Prelude Debug.Trace> head [trace "first" 1, trace "second" 2, trace "third" 3]
first
1
Prelude Debug.Trace> last [trace "first" 1, trace "second" 2, trace "third" 3]
third
3
Prelude Debug.Trace> length [trace "first" 1, trace "second" 2, trace "third" 3]
3
Prelude Debug.Trace> sum [trace "first" 1, trace "second" 2, trace "third" 3]
third
second
first
6

Модуль Debug.Trace предлагает и полезные варианты trace. Особенно удобна функция traceShowId x: она печатает show x, а результатом оставляет x. Проверим вычисление предыдущего примера с head, filter и map с помощью traceShowId. Хотя traceShowId отображается на бесконечный список [0..], фактически вычисляются только шесть значений. Последнее число 243 — возвращаемый результат, а не сообщение трассировки.

Prelude Debug.Trace> head (filter (>100) (map (\x -> traceShowId (3^x)) [0..]))
1
3
9
27
81
243
243

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

-- computes sums like 7+5+3+1
sumEverySecond :: Int -> Int
sumEverySecond 0 = 0
sumEverySecond n = n + sumEverySecond (n-2)

sumEverySecond 6 ==> 12
sumEverySecond 7 ==> doesn't terminate

Мы можем отладить это, добавив trace, чтобы обернуть весь рекурсивный случай.

sumEverySecond :: Int -> Int
sumEverySecond 0 = 0
sumEverySecond n = trace ("sumEverySecond "++show n) (n + sumEverySecond (n-2))

Prelude Debug.Trace> sumEverySecond 6
sumEverySecond 6
sumEverySecond 4
sumEverySecond 2
12
Prelude Debug.Trace> sumEverySecond 7
sumEverySecond 7
sumEverySecond 5
sumEverySecond 3
sumEverySecond 1
sumEverySecond -1
sumEverySecond -3
sumEverySecond -5
-- and so on

Ха! Проблема в том, что нашего базового случая рекурсии sumEverySecond 0 недостаточно, чтобы остановить рекурсию.

Наконец, слово осторожности. Использование trace, и особенно traceShowId, может вызвать вещи, которые иначе не были бы оценены, чтобы получить оценку. Например:

Prelude Debug.Trace> traceHead xs = head (traceShowId xs)
Prelude Debug.Trace> traceHead [0..]
-- never terminates since it's trying to show an infinite list

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

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

10.10 Викторина

Какое из этих утверждений верно?

1. reverse . reverse . reverse === reverse
2. reverse . reverse === reverse
3. reverse . id === id

Какой из них является бесконечным списком, который начинается с [0,1,2,1,2,1,2...]?

1. cycle [0,1,2]
2. 0:repeat [1,2]
3. 0:cycle [1,2]
4. 0:[1,2..]

Каков следующий шаг при оценке этого выражения?

head (map not (True:False:[]))

1. head (False : True : [])
2. head (not True)
3. head (False : map not (False:[]))
4. head (not True : map not (False:[]))

Какое из этих значений not в слабой нормальной форме головы?

1. map
2. f 1 : map f (2 : [])
3. Just (not False)
4. (\x -> x) True

Какое из этих утверждений о следующей функции верно?

f 0 x = 1+x
f _ x = 2+x

1. f строго придерживается левого аргумента
2. f строга в своих аргументах
3. f приводит оба аргумента
4. Ни один из вышеперечисленных

Работает ли эта функция с бесконечными списками? Почему?

f [] = []
f (x:xs) = x : map not xs

1. Нет, потому что он включает в себя случай [], который так и не был достигнут.
2. Нет, потому что он использует map, который оценивает весь список.
3. Да, потому что он смотрит только на первый элемент списка, прежде чем произвести значение WHNF.
4. Да, потому что это называется map, который работает с бесконечными списками.

Что насчет этого?

f xs = map (+(sum xs)) xs

1. Нет, потому что он использует map, который оценивает весь список.
2. Нет, потому что вычисление sum результата требует всего списка входных данных.
3. Да, потому что он не включает случай []
4. Да, потому что это называется map, который работает с бесконечными списками.

10.11 Упражнения

• Set10a
• Set10b

11 Лекция 11: RealWorld -> (a,RealWorld)

11.1 Содержание

• Ио

11.2 Вас обманули!

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

questionnaire = do
  putStrLn "Write something!"
  s <- getLine
  putStrLn ("You wrote: "++s)

Prelude> questionnaire
Write something!
Haskell!
You wrote: Haskell!

Чтение ввода и запись вывода было достаточно легко. Мы также можем читать по сети. Вот полная программа Haskell, которая извлекает некоторые слова из URL-адреса с помощью HTTP и печатает их.

import Network.HTTP
import Control.Monad

main = do
  rsp <- simpleHTTP (getRequest "http://httpbin.org/base64/aGFza2VsbCBmb3IgZXZlcgo=")
  body <- getResponseBody rsp
  forM_ (words body) $ \w -> do
     putStr "word: "
     putStrLn w

Вы можете найти эту программу в репозитории курса как exercises/Examples/FetchWords.hs, и вы можете запустить его следующим образом:

$ cd exercises/Examples
$ stack runhaskell FetchWords.hs
word: haskell
word: for
word: ever

Что здесь происходит? Давайте посмотрим на типы:

Prelude> :t putStrLn
putStrLn :: String -> IO ()
Prelude> :t getLine
getLine :: IO String

Значение типа IO a — это операция (operation), которая производит значение типа a. Например, getLine — операция ввода-вывода, производящая строку. Тип () называется единичным типом (unit type), и его единственное значение — (). Он используется, когда операция ввода-вывода не возвращает содержательного результата, но выполняет побочные эффекты.

Сравнение с типами Java может помочь:

Операции ввода-вывода могут быть объединены в более крупные операции с использованием do-notation.

do operation
   operation arg
   variable <- operationThatReturnsStuff
   let var2 = expression
   operationThatProducesTheResult var2

11.2.1 Примеры

Полезные операции ввода-вывода можно найти в стандартных библиотечных модулях Prelude и System. IO

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

query :: IO ()
query = do
  putStrLn "Write something!"                    -- run an operation, ignore produced value
  s <- getLine                                   -- run an operation, capture produced value
  let n = length s                               -- run a pure function
  putStrLn ("You wrote "++show n++" characters") -- run an operation, passing on the produced value

Prelude> query
Write something!
lorem ipsum
You wrote 11 characters

Значение, произведенное последней линией блока do, является значением, произведенным целым блоком. Обратите внимание, что askForALine имеет тот же тип, что и getLine, IO String:

askForALine :: IO String
askForALine = do
  putStrLn "Please give me a line"
  getLine

В дополнение к операциям ввода-вывода, таким как query, вы также можете запускать операции ввода-вывода, которые производят значения, такие как askForALine, в GHCi. Вы можете использовать <- для захвата результата операции в переменную, если хотите.

Prelude> askForALine
Please give me a line
this is a line
"this is a line"
Prelude> line <- askForALine
Please give me a line
this is a line
Prelude> :t line
line :: String
Prelude> line
"this is a line"

Если операции нужны параметры, можно определить функцию, возвращающую операцию. Обратите внимание: тип ask, как у обычной функции, содержит ->. Обычный синтаксис определения функции используется и для имени параметра question.

ask :: String -> IO String
ask question = do
  putStrLn question
  getLine

Prelude> ask "What is love?"
What is love?
Baby don't hurt me!
"Baby don't hurt me!"
Prelude> response <- ask "Who are you?"
Who are you?
The programmer.
Prelude> response
"The programmer."
Prelude> :t response
response :: String
Prelude> :t ask
ask :: String -> IO String
Prelude> :t ask "Who are you?"
ask "Who are you?" :: IO String

11.3 Тонкости return

Название функции Haskell return немного сбивает с толку. В других языках return — встроенное ключевое слово, а в Haskell это обычная функция. return :: a -> IO a принимает значение и превращает его в операцию, производящую это значение.

produceThree :: IO Int
produceThree = return 3

printThree :: IO ()
printThree = do
  three <- produceThree
  putStrLn (show three)

Это звучит не очень полезно, не так ли? В сочетании с нотацией это так. Здесь мы возвращаем boolean в зависимости от того, ответил ли пользователь Y или N:

yesNoQuestion :: String -> IO Bool
yesNoQuestion question = do
  putStrLn question
  s <- getLine
  return (s == "Y")

Prelude> yesNoQuestion "Fire the missiles?"
Fire the missiles?
Y
True
Prelude> answer <- yesNoQuestion "Are you sure?"
Are you sure?
N
Prelude> :t answer
answer :: Bool
Prelude> answer
False

Записка! Это означает, что возвращение Не прекращается исполнение Операция (в отличие от Java или C). Помните, что в do-блоках последняя строка определяет, какую стоимость производить. Это означает, что данная операция производит 2:

produceTwo :: IO Int
produceTwo = do return 1
                return 2

Prelude> produceTwo
2

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

produceThree = do putStrLn "1"   -- side effect, produces (), which is ignored
                  return    2    -- no side effect, produces 2, which is ignored
                  getLine        -- side effect, produces a String, which is ignored
                  return    3    -- no side effect, produces 3, which is passed on

Prelude> final <- produceThree
1
this line is ignored
Prelude> final
3

Также обратите внимание, что это одна и та же операция:

do ...
   x <- op
   return x

do ...
   op

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

return (f x : xs)
-- alternatively:
return $ f x : xs

11.4 do и типы

Давайте рассмотрим типизацию донотации более подробно. Do-блок строит значение типа IO <something>. Например, в

foo = do
  ...
  lastOp

lastOp должен быть типа IO X (для некоторых X). Типом foo также будет IO X. Рассмотрим следующий пример с параметрами:

bar x y = do
  ...
  lastOp arg

lastOp должен быть типа Y -> IO X (так что lastOp arg имеет тип IO X). Тип bar будет A -> B -> IO X (а внутри bar будут x :: A и y :: B).

Если вы используете return:

quux x = do
  ...
  return value

Функция quux будет иметь тип A -> IO B, где x :: A и value :: B.

Давайте посмотрим на типизацию <- дальше. Если op :: IO X и у вас есть var <- op, var будет иметь тип X. Мы видели это во многих примерах GHCi.

Последняя линия do не может быть foo <- bar. Это также не может быть let foo = bar. Последняя линия определяет, что производит вся операция, поэтому она должна быть операцией (например, return something).

Вот работающий пример:

alwaysFine :: IO Bool
alwaysFine = do
  putStrLn "What?" -- :: IO ()
  return 2         -- :: IO Int, produced value is discarded
  s <- getLine     -- getLine :: IO String, thus s :: String
  putStrLn s       -- putStrLn :: String -> IO (), thus putStrLn s :: IO ()
  let b = True     -- b :: Bool
  return b         -- :: IO Bool
                   -- Thus, alwaysFine :: IO Bool

Система типов не позволяет «сбежать» из IO. Хотя <- извлекает X из IO X, использовать <- можно только внутри do, а весь блок do снова имеет тип IO Y. Иными словами, коробку IO можно ненадолго открыть, но затем необходимо в неё вернуться. Что происходит в IO, остаётся в IO.

Позже мы поговорим о том, что это значит. На данный момент достаточно знать, что если у вас есть функция с типом не-IO, например, myFunction :: Int -> [String] -> String, внутри нее не может происходить IO. Это чистая функция.

11.5 Управляющие конструкции

Для следующих примеров нам понадобятся две новые операции.

print :: Show a => a -> IO ()   -- print a value using the show function
readLn :: Read a => IO a        -- get a line and convert it to a value using the read function

Обычные инструменты рекурсии, защитные выражения (guards) и if-then-else также работают в мире IO. Вот операция IO, которая определяется с помощью охранника:

printDescription :: Int -> IO ()
printDescription n
  | even n    = putStrLn "even"
  | n==3      = putStrLn "three"
  | otherwise = print n

Prelude> printDescription 2
even
Prelude> printDescription 3
three
Prelude> printDescription 5
5

Вот операция, которая печатает все числа в списке с использованием рекурсии и сопоставления шаблонов:

printList :: [Int] -> IO ()
printList [] = return () -- do nothing
printList (x:xs) = do print x
                      printList xs -- recursion

Prelude> printList [1,2,3]
1
2
3

Вот два немного более сложных примера рекурсивных операций ввода-вывода. Они используют значение, создаваемое рекурсивным вызовом. Операция readAndSum n считывает номера n от пользователя и печатает их сумму. Операция ask questions показывает пользователю каждую строку в questions, считывает ответ и возвращает список всех ответов.

readAndSum :: Int -> IO Int
readAndSum 0 = return 0
readAndSum n = do
  i <- readLn            -- read one number
  s <- readAndSum (n-1)  -- recursion: read and sum rest of numbers
  return (i+s)           -- produce result

Prelude> s <- readAndSum 3
2
4
5
Prelude> s
11

ask :: [String] -> IO [String]
ask [] = return []
ask (question:questions) = do
  putStr question
  putStrLn "?"
  answer <- getLine         -- get one answer
  answers <- ask questions  -- recursion: get rest of answers
  return (answer:answers)   -- produce result

Prelude> replies <- ask ["What is your name","How old are you"]
What is your name?
Yog-Sothoth
How old are you?
The question is meaningless
Prelude> replies
["Yog-Sothoth","The question is meaningless"]

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

-- when b op performs op if b is true
when :: Bool -> IO () -> IO ()
-- unless b op performs op if b is false
unless :: Bool -> IO () -> IO ()
-- do something many times, collect results
replicateM :: Int -> IO a -> IO [a]
-- do something many times, throw away the results
replicateM_ :: Int -> IO a -> IO ()
-- do something for every list element
mapM :: (a -> IO b) -> [a] -> IO [b]
-- do something for every list element, throw away the results
mapM_ :: (a -> IO b) -> [a] -> IO ()
-- the same, but arguments flipped
forM  :: [a] -> (a -> IO b) -> IO [b]
forM_ :: [a] -> (a -> IO b) -> IO ()

Используя их, мы можем переписать наши предыдущие примеры:

printList :: [Int] -> IO ()
printList xs = mapM_ print xs

readAndSum n = do
  numbers <- replicateM n readLn
  return (sum numbers)

ask :: [String] -> IO [String]
ask questions = do
  forM questions askOne

askOne :: String -> IO String
askOne question = do
  putStr question
  putStrLn "?"
  getLine

11.6 Несколько слов о do и отступах

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

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

Некоторые примеры этого правила:

-- This is not OK, putStrLn is way too left
foo = do y <- getLine
   putStrLn y

-- This is not OK either
foo = do y <- getLine
           putStrLn y

-- This is OK
foo = do y <- getLine
         putStrLn y

-- This is also OK: putting a line break after do
foo = do
  y <- getLine
  putStrLn y

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

-- This is not OK, the string starts a new operation
quux = do putStrLn
          "this long string"
          print 1

-- This is OK
quux = do putStrLn
            "this long string"
          print 1

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

-- This is OK
foo x = do quux
           y <- blorg
           when y (do thing
                      otherThing)
           return 3

-- This is also OK: starting putting a line break after do, using $
foo x = do
  quux
  y <- blorg
  when y $ do
    thing
    otherThing
  return 3

11.7 Давайте напишем программу

После всех этих коротких разовых примеров давайте обратимся к чему-то более длинному. Давайте напишем программу для получения аннотаций всех типов из всех файлов .hs. Мы используем операции ввода-вывода, такие как readFile и listDirectory, для чтения и поиска файлов, а также чистый код, такой как map и filter, для фактической обработки. Во-первых, вот краткий обзор библиотечных операций, которые мы используем:

-- split string into lines
lines :: String -> [String]
-- `isSuffixOf suf list` is true if list ends in suf
Data.List.isSuffixOf :: Eq a => [a] -> [a] -> Bool
-- `isInfixOf inf list` is true if inf occurs inside list
Data.List.isInfixOf :: Eq a => [a] -> [a] -> Bool
-- FilePath is just an alias for String
type FilePath = String
-- get entire contents of file
readFile :: FilePath -> IO String
-- list files in directory
System.Directory.listDirectory :: FilePath -> IO [FilePath]
-- is the given file a directory?
System.Directory.doesDirectoryExist :: FilePath -> IO Bool

А вот и сама программа. Вы также можете найти его в хранилище курса как exercises/Examples/ReadTypes.hs.

module Examples.ReadTypes where

import Control.Monad (forM)
import Data.List (isInfixOf, isSuffixOf)
import System.Directory (listDirectory, doesDirectoryExist)

-- a line is a type signature if it contains :: but does not contain =
isTypeSignature :: String -> Bool
isTypeSignature s = not (isInfixOf "=" s) && isInfixOf "::" s

-- return list of types for a .hs file
readTypesFile :: FilePath -> IO [String]
readTypesFile file
  | isSuffixOf ".hs" file = do content <- readFile file
                               let ls = lines content
                               return (filter isTypeSignature ls)
  | otherwise             = return []

-- list children of directory, prepend directory name
qualifiedChildren :: String -> IO [String]
qualifiedChildren path = do childs <- listDirectory path
                            return (map (\name -> path++"/"++name) childs)

-- get type signatures for all entries in given directory
-- note mutual recursion with readTypes
readTypesDir :: String -> IO [String]
readTypesDir path = do childs <- qualifiedChildren path
                       typess <- forM childs readTypes
                       return (concat typess)

-- recursively read types contained in a file or directory
-- note mutual recursion with readTypesDir
readTypes :: String -> IO [String]
readTypes path = do isDir <- doesDirectoryExist path
                    if isDir then readTypesDir path else readTypesFile path

-- main is the IO action that gets run when you run the program
main :: IO ()
main = do ts <- readTypes "."
          mapM_ putStrLn ts

Мы можем запустить эту программу, перейдя в каталог exercises/Examples и запустив:

$ stack runhaskell ReadTypes.hs
deposit :: String -> Int -> Bank -> Bank
withdraw :: String -> Int -> Bank -> (Int,Bank)
runBankOp :: BankOp a -> Bank -> (a,Bank)
... and so on

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

11.8 Что все это значит?

Вернёмся в функциональный мир. Как согласовать операции IO с чистотой и ленивостью Haskell? Значение вроде putStrLn :: String -> IO () — чистая функция, возвращающая операцию: putStrLn x всегда одинаково при одинаковом x. Иными словами, операция является чистым описанием последовательности побочных эффектов; сами эффекты возникают только при выполнении операции. При запуске программы Haskell среда выполняет одну операцию — main :: IO (). Остальные операции выполняются лишь тогда, когда связаны с main.

Когда в GHCi выражение, которое вы вводите в оценку операции, GHCi выполняет эту операцию для вас. Вот демонстрация чистоты print:

Prelude> x = print 1   -- creates operation, doesn't run it
Prelude> x             -- runs the operation
1
Prelude> x             -- runs it again!
1

Операции — это значения, как числа, списки и функции. Поэтому можно писать код, работающий с операциями. Следующая функция принимает две операции, a и b, и возвращает новую операцию, которая спрашивает пользователя, какую из них выполнить.

choice :: IO x -> IO x -> IO x
choice a b =
  do putStr "a or b? "
     x <- getLine
     case x of "a" -> a
               "b" -> b
               _ -> do putStrLn "Wrong!"
                       choice a b

Prelude> choice (putStrLn "A!!!!") (putStrLn "B!!!!")
a or b? z
Wrong!
a or b? a
A!!!!

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

mapM_ :: (a -> IO b) -> [a] -> IO ()
mapM_ op     [] = return ()       -- do nothing for an empty list
mapM_ op (x:xs) = do op x         -- run operation on first element
                     mapM_ op xs  -- run operation on rest of list, recursively

Prelude> mapM_ print [1,2,3]
1
2
3

11.9 Еще одна вещь: IORef

До сих пор мы использовали только терминальный ввод-вывод (getLine, print) и работу с файлами (readFile, listDirectory). В императивных программах на Java, Python или C встречаются и другие побочные эффекты, которые нельзя выразить чистой функцией Haskell. Один из них — изменяемое состояние (mutable state). Чистая функция не может читать изменяемое состояние: иначе два вызова одной функции с одинаковыми аргументами могли бы вернуть разные значения.

Haskell типа IORef a из модуля Data.IORef является изменяемой ссылкой на значение типа a

newIORef :: a -> IO (IORef a)                -- create a new IORef containing a value
readIORef :: IORef a -> IO a                 -- produce value contained in IORef
writeIORef :: IORef a -> a -> IO ()          -- set value in IORef
modifyIORef :: IORef a -> (a -> a) -> IO ()  -- modify value contained in IORef with a pure function

Вот несколько примеров использования IORef в GHCi:

Prelude> :m +Data.IORef
Prelude Data.IORef> myRef <- newIORef "banana"
Prelude Data.IORef> readIORef myRef
"banana"
Prelude Data.IORef> writeIORef myRef "apple"
Prelude Data.IORef> readIORef myRef
"apple"
Prelude Data.IORef> modifyIORef myRef reverse
Prelude Data.IORef> readIORef myRef
"elppa"