На этом шаге мы рассмотрим такое представление списочных структур.
Графическая нотация - это графическое представление списков, основанное на ссылочной структуре списков языка Haskell.
Оперативная память компьютера, на котором "работает" Haskell, логически разбивается на области, называемые списочными ячейками.
Эти области состоят из полей с именами head ("голова") и tail ("хвост"), каждое из которых содержит указатель (!). Указатель может ссылаться на другую списочную ячейку, на атом языка Haskell или быть "пустым", т.е. ни на что не указывать (в случае обозначения пустого списка).
Соединение ячеек памяти с помощью указателей образует цепочку ячеек, по которой можно передвигаться до атомарных объектов, попадая из предыдущей ячейки в следующую.
Замечание (важное). Каждый атом записывается в определённом месте памяти один единственный раз.
Списочную ячейку графически будем представлять прямоугольником, разделённым на поля, называемые head и tail. Указатель будем изображать в виде стрелки, начинающейся в одной из частей прямоугольника и заканчивающейся на изображении другой ячейки или атоме, адрес которого содержит соответствующий указатель.
Пустой указатель изобразим символом "N".
Примеры графической нотации.
1. Изобразим список [1,2,3,4] в графической нотации:
2. Изобразим список [[10],[10],[9]] в графической нотации двумя эквивалентными способами (обратите внимание на разное количество ячеек!):
3. Представим список [[1,2],[3]] в графической нотации:
Примеры построений точечных и списочных записей по графической.
1. Графическое представление:
Точечная запись : 1:2:3:[] Списочная запись: [1,2,3]
2. Графическое представление:
Точечная запись: (1:[]):((2:3:[]):[]) Списочная запись: [[1],[2,3]]
В заключение приведем еще несколько демонстрационных примеров.
-- Укажите прагматику приведённых ниже функций ---------------------------------------------- ud1:: [Integer] -> Bool ud1 lst = elem ((sum.tail.init) lst) lst ------------------------------------------ ud2:: [Integer] -> Bool ud2 lst = elem (product [1..minimum lst]) lst --------------------------------------------- ud3 lst = elem (sum (ud31 lst)) lst ----------------------------------- ud31:: [Integer] -> [Integer] ud31 [] = [] ud31 [x] = [] ud31 (x:y:xs) = y : ud31 xs --------------------------- ud4 lst = elem (a^b) lst where a = (head.tail) lst b = last lst ------------------------------ -- Неудачные тестовые примеры: ------------------------------ test1 = ud1 [1,2,3,4,9] test2 = ud2 [1,2,3,4,9] test3 = ud3 [1,2,6,4,9]
-- Решение задачи "Покер"... ------------------------------------------ res lst | elem 5 lst = 1 | elem 4 lst = 2 | elem 2 lst && elem 3 lst = 3 | elem 1 lst && elem 3 lst = 4 | elem 1 lst && (col 2 lst==2) = 5 | elem 2 lst && (col 1 lst==3) = 6 | True = 7 ------------------------------------------ col x lst | null lst = 0 | head lst==x = 1 + col x (tail lst) | True = col x (tail lst) ------------------------------------------ povt lst1 lst2 | null lst1 = [] | True = (col (head lst1) lst2) : povt (tail lst1) lst2 -------------------------------------------------------- -- Неудачные тестовые примеры: -------------------------------- test1 = col 4 [5,7,2,1,4,4]==2 && col 4 [5,7,2,1] ==0 -------------------------------- test2 = povt [1..5] [1,1,1,3,4] test3 = povt [1..5] [1,2,3,4,5] test4 = povt [1..5] [5,4,4,2,1] ------------------------------------------ test5 = res (povt [1..5] [2,2,3,3,4]) == 5 test6 = res (povt [1..5] [2,2,2,1,5]) test7 = res (povt [1..5] [2,2,2,1,1]) == 3 test8 = res (povt [1..5] [1,1,2,3,4]) == 6
На следующем шаге мы приведем перечень задач для самостоятельного решения.
