Лабораторная работа

Лабораторная работа №6





Теоретическая часть:
1. МОДУЛИ
Программы на языке Haskell состоят из набора модулей. Модули служат двум целям: управлению пространствами имен и созданию абстрактных типов данных. Модули имеют имена, начинающиеся с заглавной буквы; в интерпретаторе Hugs текст модуля должен находиться в отдельном файле, имя которого совпадает с именем модуля. Этот файл должениметь расширение .hs. С практической точки зрения модуль представляет собой просто одно большое объявление, начинающееся с ключевого слова module. Приведем пример модуля с именем Tree.

module Tree ( Tree(Leaf,Branch), leafList) where

data Tree a = Leaf a | Branch (Tree a) (Tree a)

leafList (Leaf x) =[x]
leafList (Branch left right) = leafList left ++leafList right

Модуль явно экспортирует Tree, Leaf, Branch и leafList. Экспортируемые из модуля имена перечисляются в скобках после ключевого слова module. Если это перечисление не указано, по умолчанию из модуля экспортируются все имена. Заметьте, что имена типа и его конструкторов должны быть сгруппированы, как в конструкции Tree(Leaf, Branch). В качествесокращения можно использовать запись Tree(..). Возможно также экспортировать только часть конструкторов данных. Модуль Tree теперь может быть импортирован в какой-либо другой модуль:
module Main where
import Tree (Tree(Leaf,Branch), leafList)
...

Здесь мы явно указали список импортируемых сущностей; если опустить его, импортируются все сущности, экспортируемые из модуля. Очевидно, если в двухимпортируемых модулях содержатся различные сущности с одним именем, возникнет проблема. Для того чтобы избежать ее, в языке существует ключевое слово qualified, при помощи которого определяются те импортируемые модули, имена объектов которых приобретают вид: Модуль. Объект. Например, для модуля Tree:

module Main where
import qualified Tree

leafList = Tree.leafList

2. АБСТРАКТНЫЕ ТИПЫДАННЫХ
Использование модулей позволяет определять абстрактные типы данных, т. е. типы, внутренняя структура которых скрыта от их пользователя. Например, рассмотрим простейший словарь, по заданному слову возвращающий его значение:
module Dictionary where
data Dictionary = Dictionary [(String,String)]

getMeaning :: Dictionary -> String -> Maybe String
getMeaning [] _ = NothinggetMeaning ((word,meaning):xs) w | w == word = Just meaning
| otherwise = Nothing

Функция getMeaning по заданному словарю и слову возвращает найденное значение (с использованием типа Maybe). Сам словарь представляется списком пар. Как создавать словарь? Пользователь это-го модуля может определить функцию addWord, которая добавляет пару «слово–значение» в словарь и возвращает модифицированныйсловарь:
import Dictionary
addWord (Dictionary dict) word meaning = = Dictionary ((word,meaning):dict)
Здесь пользователь видит представление словаря в виде списка и может воспользоваться этим. Однако в дальнейшем мы можем захотеть изменить представление словаря. Список – довольно неэффективная структура данных для поиска, если он становится велик. Гораздо лучше использовать хеш-таблицы илидеревья поиска. Однако если представление типа Dictionary открыто, мы не можем изменить его без риска нарушить функционирование пользовательских программ. Сделаем тип Dictionary абстрактным, чтобы скрыть от пользователей модуля его внутреннее представление. Определим в модуле значение emptyDict, представляющее собой пустой словарь и функцию addWord. Тогда пользователи смогут общаться со значениямитипа Dictionary только с помощью разрешенных функций:

module Dictionary (Dictionary, getMeaning, addWord, emptyDict) where
data Dictionary = Dictionary [(String,String)]

getMeaning :: Dictionary -> String -> Maybe String
getMeaning [] _ = Nothing
getMeaning ((word,meaning):xs) w | w == word = Just meaning
| otherwise = Nothing
addWord (Dictionary dict)...