Unknown - haskell-notes

or use -XNoMonomorphismRestriction

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

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

Prelude> :q

Leaving GHCi.

$ghci -XNoMonomorphismRestriction

Prelude> leteq =( ==)

Prelude> :t eq

eq :: Eqa =>a ->a -> Bool

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

{-# Language NoMonomorphismRestriction #-}

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

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

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

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

для Nat

data Nat = Zero | Succ Nat

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

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

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

( +) a Zero

=a

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

( *) a Zero

= Zero

( *) a ( Succb) =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 []