Учебник по Haskell - [29]

Только в этом случае мы не получим общего типа для eq: компилятор постарается вывести значение,

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

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

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

изменить. Компилятор даже подсказал нам как это сделать в сообщении об ошибке:

Probable fix: give these definition(s) an explicit type signature

or use -XNoMonomorphismRestriction

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

несколькими способами. Мы можем запустить интерпретатор с флагом -XNoMonomorphismRestriction:

Prelude> :q

Leaving GHCi.

$ ghci -XNoMonomorphismRestriction

Prelude> let eq = (==)

Prelude> :t eq

eq :: Eq a => a -> a -> Bool

или в самом начале модуля написать:

{-# Language NoMonomorphismRestriction #-}

Расширение будет действовать только в рамках данного модуля.

3.5 Рекурсивные типы

Обсудим ещё одну особенность системы типов Haskell. Типы могут быть рекурсивными, то есть одним из

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

для Nat

data Nat = Zero | Succ Nat

Видите, во второй альтернативе участвует сам тип Nat. Это приводит к бесконечному числу значений. Та-

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

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

(+) a Zero

= a

(+) a (Succ b) = Succ (a + b)

(*) a Zero

= Zero

(*) a (Succ b) = a + (a * b)

54 | Глава 3: Типы

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

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

базе~– цепочку рекурсивных вызовов.

Рассмотрим тип по-сложнее. Списки:

data [a] = [] | a : [a]

Деревья значений для Nat напоминают цепочку конструкторов Succ, которая венчается конструктором

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

сток, который содержит значение неокоторого типа a. Значение заканчивается пустым списком [].

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

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

всех элементов списка:

map :: (a -> b) -> [a] -> [b]

Посмотрим как она работает:

Prelude> map (+100) [1,2,3]

[101,102,103]

Prelude> map not [True, True, False, False, False]

[False, False, True, True, True]

Prelude> :m +Data.Char

Prelude Data.Char> map toUpper ”Hello World”

”HELLO WORLD”

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

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

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

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

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

преобразуем с помощью функции map:

map :: (a -> b) -> [a] -> [b]

map f []

= []

map f (a:as) = f a : map f as

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

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

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

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

раз списки водите синонимы с помощью let.

Перейдём к следующей функции. Это функция фильтрации:

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

Она принимает предикат и список, угдайте что она делает:

Prelude Data.Char> filter isUpper ”Hello World”

”HW”

Prelude Data.Char> filter even [1,2,3,4,5]

[2,4]

Prelude Data.Char> filter (> 10) [1,2,3,4,5]

[]

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

цией.

Теперь определение:

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

filter p []

= []

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

Попробуйте разобраться с ним самостоятельно, по аналогии с map. Оно может показаться немного гро-

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

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

Рекурсивные типы | 55

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr f z []

= z

foldr f z (a:as) = f a (foldr f z as)

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

дящие по типу функции. В этой маленькой функции кроется невероятная сила. Посмотрим на несколько

примеров:

Prelude Data.Char> :m -Data.Char

Prelude> let xs = [1,2,3,4,5]

Prelude> foldr (:) [] xs

[1,2,3,4,5]

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