Haskell: введение в функциональное программирование

Автор: к.ф.-м.н., доцент кафедры информатики В.Н. Власов

удобный для просмотра вид

1. Основной сайт разработчиков (англ.) Haskell.org (есть небольшой раздел на русском языке).
2. Сайт с переводом основной документации по синтаксису языка (рус.) Haskell-98.
3. Ряд статей на сайте RSDN.org (рус.) о декларативном, функциональном программировании и о Haskell, в частности Декларативное программирование . Особый интерес для начинающих представляют статьи Мягкое введение в Haskell-1 и Мягкое введение в Haskell-2, Функциональные типы и композиция функций в Хаскелле.МОНАДЫ!!!
4. A Gentle Introduction To Haskell, version 98. Revised June, 2000, (оригинал);
5. Цикл переводов «Еще Одно Руководство по Монадам» от Mike Vanier в 4-х частях: Основы, Функции '>>=' и return, Монадные законы, Монада Maybe и монада списка (возможно, самое лучшее введение по монадам на русском языке). Оригиналы и ещё 4-е статьи смотреть тут Mike's World-O-Programming;
6. Трансформеры монад (перевод на рус.);
7. «Жесткое введение» в Haskell Через тернии к Haskell (перевод). 2/2;
8. Цикл статей на сайте Техническая библиотека IBM: Функциональное программирование на Haskell : Часть 1. Введение, Функциональное программирование на Haskell: Часть 2.Основные типы и классы, Функциональное программирование на Haskell: Часть 3. Определение функций
9. Официальная документация на модуль Prelude
10. Эдвард руки — С++ (почему не надо программировать на С++, но нужно на Haskell)
11. Савчук И. Почему объектно-ориентированное программирование провалилось?
12. OOP vs type classes
13. Haskell в продакте: Отчёт менеджера проекта
14. Haskell: что это такое
15. Если бы языки программирования были машинами, Если бы языки программирования были религиями (шуточное )
16. Учебник по Haskell. Антон Холомьёв (пока лучший учебник на русском!!)
17. Шевченко Д. О Haskell по-человечески
18. Haskell IDE от FP Complete (описание на русском онлайн IDE), сейчас доступна по адресу: Haskell IDE от FP Complete (копия статьи)
19. онлайн песочница для попробовать в браузере
20. Haskell Playground

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

Полезные команды в ghci:

:q – выйти из оболочки;

:l <имя программы> – загрузить программу с указанным именем. Программа может не содержать модуля Main, а только определения функций (что мы и будем делать первое время);

:r – перегрузить текущий модуль;

:t <имя функции> – напечатать сигнатуру функции;

:i <имя функции> – напечатать сигнатуру функции и указать, в каком файле была определена данная функция;

Кроме того, надо знать, что выражения в оболочке интерпретатора можно сразу вычислять. Наберем 2 + 2 и нажмем Enter, или наберем abs (-2) и нажмем Enter, и т.д.

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

> let {f :: Int -> Int; f n = n * 2}

Отметим, что в версиях ghc/ghci, начиная с 8.0.2, ключевое слово let писать необязательно.

Многострочные записи делают следующим образом:

> :{
| let f :: Int -> Int
|     f n = n * 2
> :}

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

> :set +m:
| let f :: Int -> Int
|     f n = n * 2

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

Дополнительно отметим, что командами вида :!cmd можно вызвать команду шелла cmd (например ls в Linux или dir в Windows).

Определим факториал. В качестве необязательного начала укажем его сигнатуру. Она задает область определения и значения данной функции. В нашем случае – это потенциально бесконечное множество целых чисел. Можно попробовать вычислить факториал от 10000 или от даже большего аргумента. Для сравнения можно изменить лишь сигнатуру в определении этой функции на Int -> Int (или прямо в ghci введем новую функцию: let {f :: Int -> Int; f 1 =1; f n = n * f(n-1)}) и мы уже вряд ли сможем посчитать факториал с аргументом более 31.

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

fact :: Integer -> Integer
fact 0 = 1
fact n = n * fact (n-1)

В следующем определении мы установим «охрану» (guards), т.е. зададим ряд условий, которые также будут просматриваться по порядку. Если условие True, то считается выражение после равенства, если False, то просматривается следующее условие. При этом условия могут пересекаться или даже не покрывать все возможные ситуации. Если все условия будут просмотрены и ни одно из них не даст True, то получим ошибку времени выполнения.

Для получения сведений о типе функции, в интерпретаторе можно задать :t fact' или для более подробных сведений :i fact'.

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

fact' x | x <= 1    = 1
        | otherwise = x * fact' (x-1) 

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

1. заданную для x >= 0:
sign (x) = 0, если x=0
sign (x) = 1, иначе

2. заданную для любого x:
sign (x) = -1, при x<0
sign (x) =  1, при x>0
sign (x) =  0, иначе

В Haskell возможно описание вычисления функции в зависимости от условий в более-менее традиционном ключе, для чего присутствуют операторы if и case. Однако, их применение отлично от аналогичных операторов в императивных языках. (Правильнее их называть выражениями с использованием case- и if-then-else-конструкций)

у = х > 9 ? 100 : 200;

Ключевое слово if предназначено для указание на ветвление вычислительного процесса в зависимости от условия булевского типа. Части then и else обязательны, они в отличие от императивного аналога задают не порядок действий, а функции, которые возвращают результат для задаваемой функции. Данное выражение является частным, более простым случаем применения выражений с case.

Иными словами, условное выражение вида

nosign x = if x >= 0 then x else negate x

эквивалентно выражению

fcase x = case x >= 0 of 
           True  -> x
           False -> negate x

Рассмотрим более сложные примеры с case-выражениями:

casing :: Integer -> Integer -> Integer
casing x y = case (x, y) of 
               (_, 0) -> x
               (_, n) -> 1 + casing x (n-1)      

casing' :: Integer -> Integer -> Integer
casing' x y = case (x, y) of 
               (_, 0) | ( x >= 0 && y >= 0 ) -> x
               (_, y) | ( x >= 0 && y >= 0 ) -> 1 + casing' x (y-1)      
               (_,_)  | ( x < 0 || y < 0   ) -> error "cannot work with negative x and y"

Последний пример является комбинацией использования case-выражения с «охраной» для предотвращения применения функции для отрицательных аргументов.

Стоит также упомянуть, что задание функций уравнениями также возможно рассматривать как упрощенную запись с соответствующими case-выражениями.

Упражнение. Задать функцию sign(x) из предыдущего упражнения, используя ветвления с if и с case.

Карринг. Отметим, что в Haskell функции f'(x,y)=x+y и f'' x y = x+y — разные по сути функции. Если f'(x,y) — это функция от одного переменного (кортежа или вектора (x,y)), то f'' x y = x+y — это функция от двух переменных. Тип у них тоже будет разный, и это можно будет узнать командой :t.

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

Рассмотрим выше заданную функцию f'' x y, назовем ее более логично add x y.

add x y = x + y

Тогда мы легко можем задать частный случай сложения, функцию-инкремент add1 t = 1+t просто частичным применением уже заданной функции add

add1  = add 1

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

mi2  = \x -> (x-2)
 
trio :: Integer -> Integer -> Integer -> Integer
trio = \x y z -> x*y + z

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

duo'  = trio 2 3
duo'' = \t -> trio 2 t 3

Если мы подставим в качестве аргумента 4, то увидим разницу значений функций duo' и duo''.

В следующем, более простом примере, функции padd1 и padd3 эквивалентны, хотя заданы различными способами (можно запустить функции для проверки с аргументами 4 и 5):

-- add x y = x+y
padd  = \x y -> x^2 + y
padd1 t  = \x   -> padd t x
padd2 t  = \x   -> padd x t
padd3 x  = padd x

Необходимость в анонимных функциях возникает, например, при использовании функций высокого порядка (т.е. таких, которые в качестве аргумента сами получают функции). Например, рассмотрим функцию map, которая применяет полученную в качестве аргумента функцию к списку, полученному в качестве второго аргумента. Например, мы могли бы передать этой функции уже готовую функцию, а могли бы задать ее «на лету». Для просмотра результатов в ghci наберите show l1 и show l2.

l1 = map abs [(-1), 2, (-4.2)]
l2 = map (\x -> if x >= 0 then x else negate x) [(-1), 2, (-4.2)]

Сигнатура при использования лямбда-абстракций (особенно, когда у вводимой функции нет имени) может быть определена в скобках по месту использования:

l3 = 
  map ((\x -> if x >= 0 
               then x 
               else negate x)::(Double -> Double)) 
    [(-1), 2, (-4.2)]

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

let-выражения.

roots a b c =
 let d = b^2 - 4*a*c
     sd = sqrt d
     x1 = (-b - sd) / (2*a)
     x2 = (-b + sd) / (2*a)
 in (x1,x2)

where-конструкция. Данная конструкция не является выражением, она является частью синтаксиса объявления функций и case-выражений. Хотя в применении они очень похожи!

roots' a b c = (x1,x2) where
 d = b^2 - 4*a*c
 sd = sqrt d
 x1 = (-b - sd) / (2*a)
 x2 = (-b + sd) / (2*a)

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

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

roots' a b c | ((a == 0) && (b == 0)) = error "No roots at all!"
             | ((a == 0) && (b /= 0)) =  (x,x)  -- let x = -c/b in (x,x)  
             | (a  /= 0)  = (x1,x2) 
  where  
    d  = b^2 - 4*a*c
    sd = if (d<0) then error ("No real roots! d=" ++ show d)
           else sqrt d  
    x1 = (-b - sd) / (2*a)
    x2 = (-b + sd) / (2*a)
    x  = -c/b

Два странных (для программистов из «другого» мира) оператора «.» и «$». Сначала рекомендуется о них прочесть статьи:

Функциональные типы и композиция функций в Хаскелле

Еще Одно Руководство по Монадам (часть 1: основы)

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

Ирония в том, что в «бесточечном стиле» оператор «точка» (.) очень даже используется, — сильнее, чем в обычном коде. Тут правильнее было бы сказать «безаргументный стиль», а не «бесточечный», так как мы опускаем аргументы функций. Mike Vanier

Вот как это можно использовать:

f x = cos (sin x)
g x = cos $ sin x
h = cos . sin

Здесь функции f, g и h задают одну и ту же композицию двух функций sin и cos.

Практичность оператора применения еще нагляднее – он так же позволяет не писать лишних скобок, вот еще то же самое определение

f x = cos $ sin x

Попробуем

2 + 2.0
4.0

Теперь попробуем

let x = 2 
x + 2.0
 
<interactive>:1:4:
    No instance for (Fractional Integer)
      arising from the literal `2.0' at <interactive>:1:4-6

Почему ошибки не было в первом случае, и откуда она взялась во втором? И как ее избежать? Ведь в других языках приведение констант делает автоматически…

Prelude> :t x
x :: Integer

Prelude> :t x
x :: Num t => t

Prelude> x + 2.0
4.0

Prelude> :set -XMonomorphismRestriction
Prelude> let x = 2
Prelude> x + 2.0

<interactive>:5:5: error:
    * No instance for (Fractional Integer)
        arising from the literal `2.0'
...

Вот версия более простого и понятного примера, без странностей ограничения мономорфизма:

Prelude>let x=2::Int; y=2::Double
Prelude> x+y
<interactive>:2:3: error:
    * Couldn't match expected type `Int' with actual type `Double'
    * In the second argument of `(+)', namely `y'
      In the expression: x + y
      In an equation for `it': it = x + y

В языках типа Си это соответствовало бы объявлению и инициализации переменных типа int и double, а потом совместного их использования в одном арифметическом выражении.

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

import Control.Monad.State
 
fact' :: Integer -> State Integer Integer 
-- тип состояния - Integer, тип результата - тоже Integer
fact' 0 = do
    acc <- get -- получаем накопленный результат
    return acc -- возвращаем его
fact' n = do
    acc <- get -- получаем аккумулятор
    put (acc * n) -- домножаем его на n и сохраняем
    fact' (n - 1) -- продолжаем вычисление факториала
 
-- fact :: Integer -> Integer
fact n = fst $ runState (fact' n) 1 -- начальное значение состояния = 1

<html><hr></html>

Задания к уроку

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

2. Сделать тоже самое в отдельном файл и загрузить его в ghci с помощью команды :l.

3. Написать код для функций min, max, |x|, [x], среднего арифметического двух чисел и списка чисел, многочленов, рациональных функций и др. числовых функций.

Списки — широко используемая в Haskell (и в др. функц. языках в целом) полиморфная структура данных. Например, [a] — это семейство типов, состоящее из типов списка с элементами из a, для любого типа a. Список целых (напр., [1,2,3]), список символов (['a','b','c']), даже список списков целых и т.д. – все являются членами этого семейства (отметим, однако, что [2,'b'] не является таким примером и списком).

Список [1,2,3] в Haskell на самом деле является сокращенной формой записи для списка 1:(2:(3:[])), где [] — это пустой список, : — инфиксный оператор, добавляющий свой первый аргумент в начало своего второго аргумента (некоторого списка). Поскольку : правоассоциативен, мы можем написать 1:2:3:[].

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

(везде ниже xs, ys и т.п. обозначают список)

• xs !! n — получим n-й произвольный элемент списка xs, начиная с нулевого;
• head xs — вернет первый элемент списка xs;
• last xs — вернет последний элемент списка xs;
• tail xs — вернет список xs без первого элемента;
• init xs — вернет список xs без последнего элемента;
• reverse xs — вернет обратный список;
• length xs — вернет длину списка xs;

Ряд функций для добавления как отдельных элементов, так и целых списков.

• x:xs — добавит x в качестве нового головного (нулевого) элемента к списку xs;
• xs ++ [x] — добавит x в качестве последнеого элемента к списку xs;
• list1 ++ list2 — конкатенация двух списков list1 и list2;

Если же нам необходимо вставить x на произвольную позицию n, надо разбить список на два меньших куска, поместить новый элемент между ними и соединить все вместе обратно:

let (ys, zs) = splitAt n xs
in ys ++ [x] ++ zs

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

• drop n xs — вернет список, где удалены первых n элементов из списка xs;
• take n xs — вернет список из первых n элементов из списка xs;
• splitAt n xs — вернет пару списков, полученных из списка xs разбиением c n-й позиции (причем n-й элемент войдет во второй список);

Если мы хотим удалить только n-й элемент из списка, нам придется вновь разбить список на два меньших куска, удалить нулевой элемент из второго списка и соединить все вместе обратно:

let (ys, zs) = splitAt n xs
in ys ++ (tail zs)

Задание к уроку. Напишите функцию slice, которая работает как срезы (слайсы, slices) в таких языках как Python и Perl. Другими словами, должно быть что-то типа такого

> slice 2 3 [2.3, 7.4, 5.66, 6.1, 7.0]
[5.66, 6.1]

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

• null xs — проверяет, пуст ли список xs (возвращает True или False);
• x `elem` xs — проверит, лежит ли элемент x в списке xs (возвращает True или False);
• any test xs — вернет True, если какой-либо элемент списка удовлетворяет условию test (если тип списка [a], то тип функции test должен быть a -> Bool);
• all test xs — вернет True, если все элементы списка удовлетворяет условию test (с аналогичными выше требованиями);
• filter test xs — вернет только те элементы списка, которые удовлетворяют условию test (с аналогичными выше требованиями);

Пример использования в ghci:

Prelude> let xs = [1,2,322,100]
Prelude> filter (\x -> if x>1 then True else False) xs
Prelude> [2,322,100]

• map f xs — применит функцию f ко всем элементам списка xs и вернет новый список;
• map (\x -> if p x then f x else x) xs — применит функцию f только к тем элементам списка, для которых функция p вернет True;
• concat [[x,y,z],[a,b,c,d,e],[o,p,r,s,t]] — из списка списков вернет список элементов всех списков [x,y,z,a,b,c,d,e,o,p,r,s,t];
• zip xs ys — вернет список пар вида (x,y), в каждой из которых первый элемент x является очередным элементом первого списка xs, а второй элемент y — второго списка ys;
• zip xs [0..] — нумерация (альтернативная, ср. с п.3.1) элементов списка (так, например, zip ['a','b','c'] [0..] даст [('a',0), ('b',1), ('c',2)]);

Следующие функции всегда быстры:

• : — добавление первого элемента к началу списка;
• head — получение первого элемента списка;
• tail — удаление первого элемента из списка, т.е. хвост списка.

Функции, которые имеют дело с n-м элементом или первыми n элементами, обычно имеют скорость порядка n:

• xs !! n;
• take n xs;
• drop n xs;
• splitAt n xs.

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

• length xs;
• list1 ++ list2 — скорость зависит только от длины list1;
• last xs;
• map my_fn xs;
• filter my_test xs;
• zip list1 list2 — скорость зависит от наименьшего из этих двух списков, поскольку именно он задет размер результирующего списка;
• sum xs;
• minimum xs;
• maximum xs.

Задача 1. Написать собственные реализации функций maximum, minimum, sum, filter, reverse, sort.

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

{ 2x | x ∈  N }

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

[ 2*x | x <- [1..] ]

(отметим, заданный список будет бесконечный!)

После выражений вида x <- xs, называемых генератором, могут быть дополнительные условия (охрана), которые также должны быть выполнены:

[ 2*x | x <- [1..], 3 < x, x < 7 ]

Отметим, что хотя с математической точки зрения данный список будет формально заданным, его вычисление, быстро выдав три первых ответа: 8,10,12 — зависнет, так как реально программа будет перебирать все натуральные значения x, начиная с 1. Поэтому запуск можно делать как

take 3 [ 2*x | x <- [1..], 3 < x, x < 7 ]

либо как указано выше, вводить ограничение сверху, т.е. использовать x ← [1..57].

В примере также показан способ построения списков, называемых диапазон:

• [1..] — список всех натуральных чисел;
• [1,3..] — список всех нечетных натуральных чисел;
• [1,3..99] — список всех нечетных натуральных чисел от 1 до 99;

Простые задачи. Описать списки четных и нечетных чисел, список квадратов четных чисел, список кубов нечетных. Выбрать из них список чисел, делящихся на 7, от 2000 до 10000.

Задача 1. Написать код, генерирующий потенциально бесконечный список чисел Фибоначчи. Рассмотреть возможности «лобового решения» с бинарной рекурсией и оптимизации. (см. варианты решения)

Задача 2. Написать код, генерирующий потенциально бесконечный список простых чисел. Оптимизация по скорости, памяти и краткости кода не требуется. (см. решение здесь)

Для целей «разгрузки» базового модуля Prelude в плане работы со списками, создан модуль Data.List, который содержит помимо основных дополнительные удобные функции. Модуль необходимо вызывать квалифицированно:

import qualified Data.List

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

import Data.List(delete)

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

• nub xs – возвращает список, в котором удалены повторяющиеся элементы;
• delete x xs – удаляет первое вхождение заданного элемента x из списка xs;
• sortBy p xs – осуществляет сортировку списка xs, используя специальным образом заданную программистом функцию p;
• union xs ys – возвращает объединение двух списков;
• intersect xs ys – возвращает пересечение двух списков;
• (\\) – возвращает разность (неассоциативную) двух списков, таким образом: (xs ++ ys) \\ xs == ys (если нет общих элементов);
• elem x xs – предикат, возвращающий истину, если элемент x принадлежит списку xs;
• tails xs – функция возвращает список хвостов данного списка, напр.:

  tails "abc" == ["abc", "bc", "c", ""]

• isPrefixOf, isSuffixOf, isInfixOf – предикаты, принимающие два аргумента-списка list1 и list2, и возвращающие True, если list1 является приставкой, окончанием или содержится где-то в списке list2.

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

Модуль Data.List предоставляет ряд функций, полезных для реализации функций поиска и замены в списках. Помимо уже указанных (!!), elem есть следующие:

• find p xs – возвращает первый элемент в списке xs (обернутый конструктором Just), который удовлетворяет предикату p или Nothing в противном случае;
• findIndex p xs – возвращает индекс первого элемента в списке xs (обернутый конструктором Just), который удовлетворяет предикату p или Nothing в противном случае;
• filter p xs – возвращает подсписок списка xs, элементы которого удовлетворяют предикату p.

Задача 1. В Haskell нет встроенных функций по типу index, substr, replace для работы с поиском и заменой. Написать собственные реализации.

Хорошим собранием образцов таких определений функций является сам модуль Prelude. Для нужд обучения полезно писать собственные реализации таких функций и/или изучать готовый код.

last [x]    = x
last (_:xs) = last xs
 
init [x]    = []
init (x:xs) = x:(init xs)
 
head (x:_)  = x
 
tail (_:xs) = xs
 
null []     = True
null (_:_)  = False
 
length []   = 0
length(x:xs)= 1 + length xs

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

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

length' [] n = n
length' (_:xs) n = length' xs (n+1)

length ys = length' ys 0 

Здесь length' определена как хвостовая рекурсия, т.е. рекурсия, в определении которой последний вызов является вызовом самой себя (хвостовой вызов) и таким образом, позволяет избежать накладных расходов. Кроме того, такие определения при трансляции компилятором преобразуется в цикл типа for.

Задание 1 для самостоятельной работы: написать собственный код для всех функций работы со списками, приведенных в главе 3.

Задание 2: написать код функции транспозиции, т.е. для данного списка xs и данных номеров-параметров n,m поменять элементы xs!!n xs!!m местами. Иными словами, в императивном смысле нам необходимо сделать что-то подобное следующему:

tmpn := xs[n]; tmpm := xs[m];
xs[n]:= tmpm;  xs[m]:= tmpn;

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

Импортирование сторонних модулей производится при помощи ключевого слова import. После этого ключевого слова должно располагаться наименование импортируемого модуля, после которого может находиться перечисление тех программных сущностей, которые импортируются в модуль. Если такого списка нет, то импортируется все экспортируемое данным модулем. Например:

import Data.List
import Data.Char (
  toLower,
  toUper
)

SIC. Экспорт воплощения экземпляров классов делается всегда, вне зависимости от списка — попросту, нет механизма внесения в список.

А что делать, если возникает конфликт имен при импорте? Рассмотрим возможные решения ниже.

Иногда бывает проще при импорте скрыть некоторые имена, чем перечислять то, что импортируется. Это можно сделать при помощи ключевого слова hidding, которое должно располагаться после наименования модуля при импорте. После этого перечисляются имена, которые должны быть скрыты при импорте:

import MyModule hiding (
someFunction1, someFunction2
)