Модули

Модули – это способ организации различных компонентов программы. Проводя аналогии с C++, это своего рода гибрид файлов и пространств имён.

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

В первой строчке файла исходных текстов (не считая комментариев и директив компилятора) объявляется название модуля:

module ModuleName where

После названия модуля в круглых скобках через запятую может следовать список экспортируемых имён (функций, типов, классов типов, etc), например:

module ModuleName (someFunction) where

someFunction x y = x + y

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

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

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

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

module ModuleName where

import Data.List

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

module ModuleName where

import Data.List (lookup)

Альтернативно, после имени модуля может быть директива hiding и список имён, тогда импортируются все имена кроме указанных:

module ModuleName where

import Data.List hiding (lookup)

Имена из импортированного модуля оказываются в текущей области видимости. Если есть несколько модулей с пересекающимися именами (например, Data.Map и Data.List оба содержат функцию lookup и другие), это приведёт к конфликту имён. Чтобы этого избежать, к именам можно обращаться, добавляя полное имя модуля (через точку):

module ModuleName where

import Data.List
import Data.Map

listLookup = Data.List.lookup
mapLookup = Data.Map.lookup

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

module ModuleName where

import Data.List as L (lookup)
import Data.Map as M (lookup)

listLookup = L.lookup
mapLookup = M.lookup

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

module ModuleName where

import qualified Data.List (lookup) as L
import qualified Data.Map (lookup) as M

listLookup = L.lookup
mapLookup = M.lookup
preludeLookup = lookup -- определение из Prelude

Модуль Prelude импортируется автоматически, если он явно не указан в списке импортов. Явное указание Prelude позволяет изменять набор импортов “по умолчанию”.

Если заголовок модуля не указан, по умолчанию полагается, что модуль имеет заголовок

module Main where

Модуль Main должен экспортировать функцию main, которая является точкой входа в программу.

Функция main и do-нотация

Функция main является точкой входа в программу на Haskell. С определённой точки зрения это так же своего рода “окно во внешний мир” – в большинстве программ на Haskell, операции ввода-вывода возможны только в контексте функции main или специальных функций (имеющих специальный тип), которые вызываются из функции main (прямо или косвенно).

Поскольку main не будет в полном смысле “чистой” (без побочных эффектов), Haskell допускает использование специального синтаксиса, называемого do-нотацией, для эмуляции императивного стиля. do-нотация начинается с ключевого слова do, далее следует последовательность “команд”, которые должны начинаться в одном и том же столбце исходного файла (аналогично связываниям в блоке let). Команды включают:

1. Вычисление с побочным эффектом

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

   Например,

   main = do
     putStr "Hello, "
     putStrLn "World!"

2. let-связывание в виде команды

   Про это вскользь упоминалось ранее, но повторимся. Синтаксис повторяет синтаксис связывания let ... in ..., но без in .... Имена, объявленные в таком блоке let доступны после объявления в блоке do (как в императивных программах). Внутри одного блока let определения по-прежнему взаимно рекурсивны.

   Например,

   main = do
     let hello = "Hello, "
     -- ниже доступно имя hello
     putStr hello
     let world = "World!"
     -- ниже доступно имя world
     putStrLn world

3. Связывание результата вычисления с побочным эффектом с именем

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

   Например,

   main = do
     putStr "Please enter your name: "
     name <- getLine -- связать результат вычисления getLine с именем name
     -- ниже доступно имя name
     putStr "Hello, "
     putStrLn name

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

Следует отдельно отметить, что do-нотация – это только способ записи, похожий на императивный стиль. На самом деле, это просто синтаксический сахар для всё того же функционального языка, основанного на λ-исчислении. Чтобы не быть голословным, последний пример можно переписать без do-нотации, например, следующим образом:

main = putStrLn =<<
  (putStr "Please enter your name: " *> getLine <* putStr "Hello, ")

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

Аннотации типов

Мы называем Haskell строго статически типизированным языком программирования. Однако можно заметить, что до сих пор мы вообще не вспоминали о типах. Это получилось, поскольку Haskell – типовыводящий язык, и делал всю работу, связанную с типами незаметно для нас. Однако хорошей практикой считается указание хотя бы типов объявлений верхнего уровня.

Типы в Haskell указываются после ключевого слова :: (два двоеточия). Эта нотация аналогична нотации из простого типизированного λ-исчисления (где используется одно двоеточие). В отличие от простого типизированного λ-исчисления, типы в Haskell могут быть полиморфными. Названия конкретных типов начинаются с заглавной буквы, названия переменных – с маленькой. В процессе выведения типов, вместо переменных типов будут подставлены конкретные (возможно составные, напр. типы функций)

Аннотации типов для имён указываются на отдельной строчке, обычно рядом со связыванием. Этот синтаксис работает как на верхнем уровне, так и в let- и where-связываниях:

almostPi :: Integer
almostPi = 3

someFunction x =
  let almostE :: Integer
      almostE = 3
  in almostE * x

otherFunction x = almostPi * x
  where almostPi :: Integer
        almostPi = 3

Если аннотация для имени не указана, Haskell попытается вывести тип имени из значения.

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

(3 :: Float) * 4

3 * 4 :: Float

Это фиксирует тип на одном из шагов вывода типов. Если компилятор не может вывести типы таким образом, чтобы его вывод совпадал с указанным типом, генерируется ошибка компиляции. Ещё раз отметим, это не приведение/преобразование типов, как, например в С:

float x;
int a;
x = 3.14;
a = (int) x;

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

Объявление типов

Haskell позволяет объявлять пользовательские типы. Простейшее объявление типов – это объявление синонимов. Синонимы объявляются ключевым словом type:

type SynonymName = SomeType
--   ⬑ имя синонима
--                 ⬑ имя типа

Объявления синонимов могут быть параметрическими:

type ParametricSynonym a = ParametricType a

Строго говоря, аргумент не обязательно должен фигурировать в правой части:

type ParametricSynonym a = SimpleType

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

Второй вариант – определение новых типов данных. Они объявляются с ключевым словом data:

data NewDataType = DataConstructor Argument1 Argument2
                 | OtherDataConstructor ...

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

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

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

data MyEnumType = Value1 | Value2 | Value3

объявляет тип MyEnumType и три значения этого типа – Value1, Value2 и Value3 (поскольку чистые функции 0 аргументов – это значения).

Объявление

data ErrorOrSuccess a = Error | Success a

объявляет тип высшего порядка (ака семейство типов) (ErrorOrSuccess a), значение Error (которое может иметь любой тип из семейства) и функцию Success, принимающую аргумент какого-то (любого) типа a и возвращающую значение типа ErrorOrSuccess a.

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

На основе синтаксиса объявлений типов данных есть синтаксис для объявления записей, он описан в лекции 4.

Наконец, типы данных, имеющие ровно один конструктор, принимающий ровно один аргумент (т.е. вида data NewType = DataCtor OldType или data NewTypeCtor a = DataCtor a), могут быть объявлены с ключевым словом newtype вместо data. Типы, объявленные через newtype не добавляют накладных расходов во время выполнения по сравнению с базовым типом.

Основные типы

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

Простейший пример типа высшего порядка – тип функции, определяемый, как и в простом типизированном λ-исчислении, как некий бинарный оператор ->, действующий на два других типа. Тогда для некоторых типов a и b, функция из a в b будет иметь тип a -> b. В качестве b здесь может выступать любой тип, в том числе и тип функции, например, если b = c -> d, то a -> b = a -> (c -> d). Так же, как и в λ-исчислении, оператор ->, называемый конструктор типа функции, считается правоассоциативным. Как и все прочие бинарные операторы, оператор -> может использоваться префиксно, если взять его в скобки:

type IntFunction = (->) Int Int
-- эквивалентно
type IntFunction = Int -> Int

Тип, содержащий переменные типа (которые не фиксированы), будем называть полиморфным типом. Тип, не содержащий переменных типа – конкретным.

Основные простые типы

• Int – знаковое машинное целое
• Integer – знаковое целое произвольной длины (теоретически представимо любое целое число, практически ограничено объёмом оперативной памяти)
• Word – беззнаковое машинное целое
• Float и Double – числа с плавающей запятой одинарной и двойной точности соответственно
• Rational – рациональные числа (представимые в виде дроби) произвольной точности; хранятся как два целых. Значение типа Rational может быть сконструировано из двух целых с помощью оператора %, определённого в модуле Data.Ratio.
• Fixed – числа с фиксированной запятой. Определены в модуле Data.Fixed. Строго говоря это семейство типов Fixed a, где a принимает значение E0, E1, E2, E3, E6, E9 или E12, и означает число знаков после запятой. Хранятся в виде Integer, а расположение запятой определяется параметром типа. Могут быть сконструированы из целого конструктором MkFixed.
• Bool – тип булевских переменных, имеет два значения, True и False. Почему значения с заглавной буквы, станет ясно несколько позднее.
• Char – тип символа Unicode.
• String – строка, список Char
• () – единичный тип, единственное значение ()
• Ordering – тип, отражающий порядок элементов. Имеет значения LT, EQ и GT.

Типы Int, Integer и т.п. достаточно непрозрачны, т.е. их определения нельзя выразить в рамках базового Haskell. Некоторые из этих типов, однако, можно определить в терминах Haskell:

-- Rational
type Rational = Ratio Integer
data Ratio a = Ratio a a

-- Fixed
newtype Fixed a = MkFixed Integer
data E0
data E1
-- и т.д.

-- Bool
data Bool = False | True

-- String
type String = [Char]

-- ()
data () = ()
-- строго говоря, это некорректный синтаксис, но
-- с точки зрения поведения всё именно так.

-- Ordering
data Ordering = LT | EQ | GT

На самом деле, в стандартной библиотеке GHC записано

data Ratio a = a :% a

т.е. конструктор данных определён как оператор.

Но конструктор данных типа Ratio по умолчанию не экспортируется, и является деталью реализации, поэтому его название не имеет значения. Вместо него используется оператор %, определённый в модуле Data.Ratio

Определённый интерес представляют типы E0 и прочие. Они не имеют конструкторов, т.е. не существует значений, имеющих тип E0 и т.п. Эти типы используются только на уровне типов в качестве маркеров для семейства типов Fixed a.

Основные типы высшего порядка

Кортежи

Собственно, кортежи разного количества элементов являются разными семействами, но их удобно обсуждать вместе. Минимальный размер кортежа – 2 элемента, максимальный теоретически не ограничен, практически стандарт языка требует хотя бы 15 элементов. В стандартной библиотеке есть функции для работы с кортежами до 7 элементов.

Максимальный размер кортежа в GHC 8.6 – 62 элемента (но несложно обойти это ограничение, используя вложенные кортежи).

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

Пары объявляются как (a, b), где a, b – произвольные типы, значения – как (x, y). Строго говоря, синтаксис (x, y) – это сахар для применения конструктора значения пары (,) к аргументам x и y, поэтому вообще-то пары конструирует функция (,). Аналогично, типы конструирует конструктор типов (,), поэтому следующие варианты кода эквивалентны:

someValue :: (Int, String)
-- эквивалентно
someValue :: (,) Int String

someValue = (123, "say my name")
-- эквивалентно
someValue = (,) 123 "say my name"

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

Списки

Определение типа списка записывается обычно в виде

data [] a = [] | a : ([] a)

Это, строго говоря, не является корректным синтаксисом Haskell, поэтому перепишем это в виде

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

Это абсолютно эквивалентная запись, только конструктор типа списка [] назван List, конструктор значения пустого списка [] назван Nil, и конструктор присоединения в начало списка : назван Cons.

Это рекурсивное определение, и его можно читать следующим образом: “Значение типа списка List a может быть либо пустым списком Nil, либо текущим значением элемента списка типа a и всем остальным списком List a”.

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

myList = 1 : 2 : 3 : 4 : []

Оператор : правоассоциативный и имеет приоритет 5.

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

myList = 1 : 2 : 3 : 4 : []
-- эквивалентно
myList = [1, 2, 3, 4]

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

Естественно, : работает как оператор добавления в начало любого списка:

1:[2,3,4] == [1,2,3,4]

Следует отметить, что поскольку это структура односвязного списка, добавление в конец списка или вычисление длины – это операция, имеющая временную сложность \(O(n)\), где \(n\) – длина списка.

Функции

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

Тип IO

Семейство типов IO a – это типы, задача которых “пометить” операции, взаимодействующие с внешним миром, такие как чтение файлов, вывод на экран и т.п.

Функция main по стандарту имеет тип

main :: IO ()

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

Когда мы обсуждали do-нотацию, мы говорили, что командой может быть вычисление с побочным эффектом или связывание результата такого вычисления с именем. Более формально, в качестве команды может выступать выражение, имеющее тип IO () (или IO a, где a ≠ (), но это сгенерирует предупреждение компилятора), либо конструкция вида (с явными аннотациями типов)

(name :: a) <- (action :: IO a)

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

Другие типы

Интересно так же отметить следующие типы:

data Maybe a = Nothing | Just a
data Either a b = Left a | Right b

Оба типа широко используются для сигнализирования об ошибке. Тип Maybe a может возвращать значение типа a (“завёрнутое” в конструктор Just), либо значение Nothing. Соответственно для частично-определённых функций, таких, например, как поиск ключа в словаре ключ-значение (которые не для любого значения аргумента могут вернуть результат), возвращаемый тип часто делают вместо типа результата Maybe тип результата.

Тип Either a b используется для того же, b – обычно тип корректного результата. В качестве a используется какой-либо тип, сигнализирующий какая именно ошибка произошла. Например, можно написать какой-то такой код:

data ErrorType = DivByZero | NegativeLogarithm

makeSomeComputation :: Float -> Either ErrorType Float
makeSomeComputation x =
  if x < 0 then Left NegativeLogarithm
  else if x == 0 then Left DivByZero
  else Right (log x / x)

Типы числовых литералов

Числовые литералы в Haskell немного “волшебные”, в том смысле, что числовой литерал, независимо от вида, может иметь любой числовой тип, в котором представим. Так, скажем, в зависимости от контекста, литерал 1 может иметь тип Int, Integer, Word, Float, Rational и т.п.

Литералы дробных чисел не могут иметь целочисленный тип. Так, 3.14 может иметь тип Rational, Float, Double, но не Int, Integer или Word.

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

Haskell – язык со строгой типизацией, поэтому неявных преобразований между типами нет. В основном это заметно на числовых типах: неявного преобразования между Float и Integer или Float и Double быть не может. Однако, есть несколько функций, которые позволяют конвертировать числовые типы один в другой:

• fromInteger – конвертирует Integer в любой числовой тип
• toInteger – конвертирует любой целочисленный тип в Integer
• fromIntegral – конвертирует любой целочисленный тип в любой числовой тип
• realToFrac – конвертирует любой численный тип¹ в любой дробный (Ratio a, Float, Double)
• round – округление до целого (дробная часть 0.5 к чётному). Есть другие методы округления, рассматриваемые в лекции 4
• fromRational – преобразование Rational в любой дробный тип

Например, такой код не компилируется:

let x = (8 :: Int) in x / 4

(операция деления определена только для дробных чисел)

Но такой – да:

let x = (8 :: Int) in fromIntegral x / 4

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

Основные функции ввода-вывода

Стандартный ввод-вывод

putChar :: Char -> IO ()

Вывести один символ на стандартный вывод

putStr :: String -> IO ()

Вывести строку на стандартный вывод

putStrLn :: String -> IO ()

Как putStr, но добавляет перенос строки после вывода

print :: Show a => a -> IO ()

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

getChar :: IO Char

Прочитать один символ со стандартного ввода

getLine :: IO String

Прочитать строку со стандартного ввода (до первого переноса строки)

getContents :: IO String

Прочитать всё содержимое стандартного ввода.

interact :: (String -> String) -> IO ()

Получить всё содержимое стандартного ввода, передать его в функцию типа String -> String, результат функции вывести на стандартный вывод:

interact f = do s <- getContents
                putStr (f s)

Ввод-вывод в файл

type FilePath = String

Тип FilePath определён как синоним для String.

readFile :: FilePath -> IO String

Прочитать содержимое файла как строку

writeFile :: FilePath -> String -> IO ()

Записать строку как файл (перезаписав содержимое)

appendFile :: FilePath -> String -> IO ()

Добавить строку в конец файла

Экспорт/импорт конструкторов значений типов

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

import Data.Bool (Bool(True, False), not)

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

import Module (Type(..))

Выражение (..) после имени импортируемого типа импортирует так же и все конструкторы значений. Аналогичный синтаксис работает и при экспорте:

module MyModule (MyType(..)) where

data MyType = Ctor1 | Ctor2 | Ctor3

Если при импорте/экспорте указать только название типа, то ни один конструктор не будет импортирован/экспортирован:

Prelude> import Prelude (Bool)
Prelude> True
<interactive>:34:1: error: Data constructor not in scope: True

Упражнения

Упражнение 1

Пусть встроенная функция length имеет сигнатуру

length :: [a] -> Int

(на самом деле сигнатура length немного более общая)

1. Сколько аргументов она принимает?

2. Какие типы аргументов?

3. Какой тип результата?

4. Каковы результаты следующих выражений?

   length [1,2,3,4]

   length [(1,2),(2,3),(3,4),(4,5)]

   length "hello"

   Проверьте себя в GHCi.

Упражнение 2

Рассмотрите типы в выражениях

12 / 4

и

12 / length [1,2,3]

Одно из них компилируется, второе – нет. Почему? Как можно это исправить?

Упражнение 3

Какой тип выражения

2+3 == 5

?

Каков его результат?

Проверьте себя в GHCi.

Упражнение 4

Что означают следующие выражения?

1. x = 3

2. x + 3 == 7

Упражнение 5

Ниже приведены выражения. Какие из них будут работать? Какие не будут? Почему?

• length [1,2,3] == 2
• length [1, 'a', 2, 'b']
• [1, 2.0, 3.1]
• length [1,2] + length [2,3]
• (3==3) && ('b' < 'a')
• (8 == 9) && 0

Каков результат выражений, которые будут работать?

Проверьте себя в GHCi.

Упражнение 6

Палиндром – это строка, прочитанная в обратном порядке дающая исходную. Например, слово мадам – палиндром.

Встроенная функция

reverse :: [a] -> [a]

принимает на вход список и возвращает список с элементами в обратном порядке.

Напишите функцию isPalindrome, возвращающую True, если аргумент является палиндромом. Функция isPalindrome должна иметь сигнатуру:

isPalindrome :: String -> Bool

Упражнение 7

Встроенные функции fst и snd возвращают первый и второй элементы пары соответственно:

fst :: (a, b) -> a
snd :: (a, b) -> b

Используя fst и snd, напишите реализацию функции f, имеющей сигнатуру

f :: (a, b) -> (c, d) -> ((b, d), (a, c))

Упражнение 8

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

Например,

• ввод: Монтенегро
• вывод: оргенетноМ

Скомпилируйте и проверьте её работу.

Пример сессии:

> reverse.exe
спиртовать
ьтавотрипс