|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[10] Мы начали с определения очень простой функции listify, которая преобразует аргумент в одноэлементный список. Функция listify2 полностью эквивалентна функции listify за исключением способа ее определения. Результатом вычисления выражения fn х => [х] является функция, которая преобразует аргумент х в список [х] - точно так же, как это делает функция listify. Такое выражение, вырабатывающее функцию, мы можем применять к аргументу непосредственно (как в предпоследнем случае) или передать в качестве аргумента другой функции (как в последнем случае). Точно так же, как и при использовании fun, при использовании fn можно применять сопоставление с образцом: -( fn nil => nil I hd::tl => tl ) ([1,2,3]); >[2,3] : int list -(fn nil => nil I hd::tl=>tl)( []); >nil : int list Описание каждого случая здесь называется правилом, а такой способ определения функции - определением с помощью набора правил. Заметим, что безымянная функция не может быть рекурсивной, поскольку нет никакого способа сослаться на нее в процессе определения. Это одна из причин того, почему функции в ML тесно связаны с объявлениями: одна из целей привязки к функциональному значению состоит в том, чтобы ввести имя функции с тем, чтобы это имя могло быть использовано в определении функции. Упражнение 2.5.8 Рассмотрим следующую задачу: сколькими способами можно разменять сумму в £1 монетами достоинством в 1, 2, 5 10 20 и 50 пенсов. Предположим, что мы ввели некоторый порядок на множестве достоинств монет. Очевидно, что тогда выполняется следующее соотношение: =+ собов разменятьразменять сумму а,разменять сумму a - d, сумму а исполь-используя все типыиспользуя все n типов зуя n типов мо-монет, кроме перво-монет (где d есть нетгодостоинство монеты первого типа) Это соотношение может быть преобразовано в рекурсивное определение функции, если добавить случаи, описывающие завершение рекурсии. Именно, если а = 0, имеется ровно 1 способ размена; если а < 0 или n = 0, способов размена нет. Эти замечания позволяют записать следующее определение функции: fun first denom 1=1 I first denom 2=2 I firstdenom 3=5 I first denom 4 = 10 I first denom 5 = 20 I first denom 6 = 50; fun cc(0, ) = 1 I cc( ,0) = 0 I cc(amount, kinds) = if amount < 0 then 0 else cc( amount-(first denom kinds), kinds) + cc( amount, (kinds-1)); fun count change amount = cc(amount,6); Измените этот пример так, чтобы в нем использовался список достоинств монет (вместо функции f irst.denomj. Упражнение 2.5.9 Приведенный выше алгоритм плох в том смысле, что в нем выполняется много излишних вычислений. Можете ли вы предложить более быстрый алгоритм? (Это непростая задача, и вы можете пропустить ее при первом чтении). Упражнение 2.5.10 (Ханойские башни) Имеется три стержня (обозначим их A B и С). На, стержень A надето n дисков разного размера так, что внизу находится наибольший, над ним - чуть меньший, и т.д.; наверху находится самый маленький диск. Требуется перенести диски со стержня A на стержень С по следующим правилам: за один ход можно переложить с одного из стержней верхний диск на другой стержень при условии, что перекладываемый диск меньше диска, на который он кладется. Определите функцию, решающую эту задачу. 2.6 Полиморфизм и перегрузка Имеется одна тонкая, но важная деталь, которую нужно знать для понимания реализации полиморфизма в ML. Напомним, что полиморфным типом мы называем тип, в который входят переменные типа (в противоположность мономорфным типам, в которые такие переменные не входят). В предыдущем разделе мы определили полиморфную функцию как функцию, работающую с аргументами различных типов (из некоторого класса) единообразным способом. Ключевая идея состоит в том, что такую функцию "не интересуют" типы значений (или компонент значений); поэтому она работает независимо от этих значений, и, таким образом, допускает различные типы значений. Например, тип функции append есть a list * a list -> a list, что отражает тот факт, что функция append не интересуется типом элементов списка; единственное, 2.6. ПОЛИМОРФИЗМ И ПЕРЕГРУЗКА что требуется, это чтобы элементы обоих списков-аргументов имели одинаковый тип. Тип полиморфной функции всегда есть полиморфный тип; он задает бесконечное семейство типов, состоящее из типов, являющих частными случаями полиморфного типа (т.е. получаемых в результате замены переменных типа на какие-либо конкретные типы). Например, append может работать с аргументами типа int list, bool list, int*bool list и так далее до бесконечности. Обратите внимание на то, что полиморфизм не ограничивается функциями: пустой список nil является списком элементов любого типа, и поэтому типом nil является a list. Полиморфизм отличается от другого понятия - перегрузки (хотя, на первый взгляд, они схожи). Перегрузка связана со способом записи, а не со способом определения функции. Примером перегрузки может служить функция сложения, обозначаемая +. Мы записываем сложение целых чисел 2 и 3 как 2+3, а сложение действительных чисел 2.0 и 3.0 -как 2.0+3.0. Это может показаться похожим на случаи применения функции append к двум спискам целых чисел и двум спискам действительных чисел. Однако схожесть здесь лишь частичная: одна и та же функция append применяется для соединения списков любого типа, но алгоритм сложения целых чисел отличается от алгоритма сложения действительных чисел. (Если вы знакомы с обычным представлением чисел в компьютере, у вас это не вызовет сомнения). Таким образом, один и тот же символ + используется для обозначения двух различных функций - а не одной полиморфной функции. В каждом конкретном случае выбор функции, которую следует использовать, зависит от типа аргументов. В этом причина того, что нельзя просто написать fun plus(х,у) = х+у: компилятор должен знать типы х и у, чтобы определить, какая из двух функций сложения должна быть использована - и поэтому он не допускает такого определения. Способ решения этой проблемы состоит в явном указании типа аргументов функции plus; это записывается как fun plus(х:int, у:int) = х+у. Интересный факт состоит в том, что, если бы не было перегруженных функций, то никогда бы не возникала необходимость явно указывать типы10. Но для того, чтобы обеспечить возможность перегрузки, и для того, чтобы повысить надежность программы, ML позволяет вам явно указывать тип конструкции путем приписывания к нему типового выражения. Ниже мы приводим примеры использования явного указания типа: -fun plus(х,у) = х+у; Unresolvable overloaded identifier: + -fun plus(x:int,y:int) = x+y; 103a исключением случая использования частичных образцов, как. например, fun f{x, . . .} = X. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||