В поисках прямоугольного треугольника

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

® длины сторон являются це- лыми числами;

® длина каждой стороны мень- ше либо равна 10;

® периметр треугольника (то есть сумма длин сторон) ра- вен 24.

Треугольник называется прямо- угольным, если один из его углов яв- ляется прямым (равен 90 градусам).

 

Прямоугольные треугольники обладают полезным свойством: если возвести в квадрат длины сторон, образующих прямой угол, то сум- ма этих квадратов окажется равной квадрату стороны, противопо- ложной прямому углу. На рисунке стороны, образующие прямой угол, помечены буквами a и b; сторона, противоположная прямому углу, помечена буквой c. Эта сторона называется гипотенузой.

Первым делом построим все тройки, элементы которых мень- ше либо равны 10:

ghci> let triples = [(a,b,c) | c <– [1..10], b <– [1..10], a <– [1..10]]

Мы просто собираем вместе три списка, и наша производя- щая функция объединяет их в тройки. Если вы вызовете функцию triples в GHCi, то получите список из тысячи троек. Теперь добавим условие, позволяющее отфильтровать только те тройки, которые со- ответствуют длинам сторон прямоугольных треугольников. Мы также модифицируем эту функцию, приняв во внимание, что сторона b не больше гипотенузы, и сторона a не больше стороны b.

ghci> let rightTriangles = [ (a,b,c) | c <– [1..10], b <– [1..c], a <– [1..b], a 2 + b 2 == c 2]

 

ПРИМЕЧАНИЕ. В консоли интерпретатора GHCi невозможно определять программные сущности в нескольких строках. Но в данной книге нам иногда приходится разбивать определения на несколько строк, чтобы код помещался на странице. В противном случае книга оказалась бы такой широкоформатной, что для неё вам пришлось бы купить гигантский книжный шкаф!

Почти закончили. Теперь давайте модифицируем функцию, чтобы получить треугольники, периметр которых равен 24.

ghci> let rightTriangles' = [ (a,b,c) | c <– [1..10], b <– [1..c], a <– [1..b], a 2 + b 2 == c 2, a+b+c == 24]

ghci> rightTriangles' [(6,8,10)]

Вот и ответ! Это общий шаблон в функциональном программи- ровании. Вы берёте начальный набор решений и затем применяете преобразования и фильтруете их, пока не получите результат.

 

ТИПЫ И КЛАССЫ ТИПОВ

Поверь в типы

Мы уже говорили о том, что Haskell является статически типизированным языком. Тип каждого выражения известен во время компиляции – это за- лог безопасного кода. Если вы напишете программу, которая попытается поделить булевс- кий тип на число, то она даже не скомпилируется.

И хорошо, потому что уж лучше ловить такие ошибки на этапе компиляции, чем наблюдать, как ваша программа аварийно закры- вается во время работы! Всему в языке Haskell назначен свой тип, так что компилятор может сделать довольно много выводов о про- грамме перед её компиляцией.

В отличие от языков Java или Pascal, у Haskell есть механизм вывода типов. Если мы напишем число, то нет необходимости ука- зывать, что это число. Язык Haskell может вывести это сам, так что нам не приходится явно обозначать типы функций и выраже- ний.

Мы изучили некоторые основы языка, лишь вскользь упомянув о типах. Тем не менее понимание системы типов – очень важная часть обучения языку Haskell.

ЯВНОЕ ОПРЕДЕЛЕНИЕ ТИПОВ 47

Тип – это нечто вроде ярлыка, который есть у каждого выраже- ния. Он говорит нам, к какой категории относится данное выраже- ние. Выражение True – булево, "привет" – это строка, и т. д.

 

Явное определение типов

А сейчас воспользуемся интерпретатором GHCi для определения типов нескольких выражений. Мы сделаем это с помощью коман- ды:t, которая, если за ней следует любое правильное выражение, выдаст нам тип последнего. Итак...

ghci>:t 'a' 'a':: Char ghci>:t True True:: Bool

ghci>:t "ПРИВЕТ!" "ПРИВЕТ!":: [Char]

ghci>:t (True, 'a') (True, 'a'):: (Bool, Char) ghci>:t 4 == 5

4 == 5:: Bool

Мы видим, что:t печатает выражения, за которыми следу- ют:: и их тип. Символы:: озна- чают: «имеет тип». У явно указан- ных типов первый символ всегда в верхнем регистре. Символ 'a', как вы заметили, имеет тип Char. Несложно сообразить, что это сокращение от «character» – сим- вол. Константа True имеет тип Bool. Выглядит логично... Идём дальше.

Исследуя тип "ПРИВЕТ!", получим [Char]. Квадратные скобки ука- зывают на список – следовательно, перед нами «список символов». В отличие от списков, каждый кортеж любой длины имеет свой тип. Так выражение (True, 'a') имеет тип (Bool, Char), тогда как выражение ('a','b','c') будет иметь тип (Char, Char, Char). Выра- жение 4==5 всегда вернёт False, поэтому его тип – Bool.

 

У функций тоже есть типы. Когда мы пишем свои собственные функции, то можем указывать их тип явно. Обычно это считает- ся нормой, исключая случаи написания очень коротких функций. Здесь и далее мы будем декларировать типы для всех создаваемых нами функций.

Помните генератор списка, который мы использовали ранее: он фильтровал строку так, что оставались только прописные бук- вы? Вот как это выглядит с объявлением типа:

removeNonUppercase:: [Char] –> [Char]

removeNonUppercase st = [ c | c <– st, c `elem` ['А'..'Я']]

Функция removeNonUppercase имеет тип [Char] –> [Char]. Эта за- пись означает, что функция принимает одну строку в качестве па- раметра и возвращает другую в качестве результата.

А как записать тип функции, которая принимает несколько па- раметров? Вот, например, простая функция, принимающая три це- лых числа и складывающая их:

addThree:: Int –> Int –> Int –> Int addThree x y z = x + y + z

Параметры разделены символами –>, и здесь нет никакого раз- личия между параметрами и типом возвращаемого значения. Воз- вращаемый тип – это последний элемент в объявлении, а парамет- ры – первые три.

Позже мы увидим, почему они просто разделяются с помощью символов –>, вместо того чтобы тип возвращаемого значения как- то специально отделялся от типов параметров (например, Int, Int, Int –> Int или что-то в этом духе).

Если вы хотите объявить тип вашей функции, но не уверены, ка- ким он должен быть, то всегда можно написать функцию без него, а затем проверить тип с помощью:t. Функции – тоже выражения, так что:t будет работать с ними без проблем.