:: Angle
-> Point -> Point
norm
:: Point
-> Point
translate
:: Vector -> Point -> Point
...
5.5 Комбинатор неподвижной точки
Познакомимся с функцией fix или комбинатором неподвижной точки. По хорошему об этой функции
следовало бы рассказать в разделе обобщённые функции. Но я пропустил её нарошно, для простоты изло-
жения. В этом разделе градус сложности резко подскакивает, если вы ранее не встречались с этой функцией
она может показаться вам очень необычной. Для начала посмотрим на её тип:
Prelude> :m +Data.Function
Prelude Data.Function> :t fix
fix :: (a -> a) -> a
Странно fix принимает функцию и возвращает значение, обычно всё происходит наоборот. Теперь по-
смотрим на определение:
fix f = let x = f x
in
x
Если вы запутались, то посмыслу это определение равносильно такому:
fix f = f (fix f)
Функция fix берёт функцию и начинает бесконечно нанизывать её саму на себя. Так мы получаем, что-то
вроде:
f (f (f (f (... ))))
Зачем нам такая функция? Помните в самом конце четвёртой главы в упражнениях мы составляли бес-
конечные потоки. Мы делали это так:
data Stream a = a :& Stream a
constStream :: a -> Stream a
constStream a = a :& constStream a
82 | Глава 5: Функции высшего порядка
Если смотреть на функцию constStream очень долго, то рано или поздно в ней проглянет функция fix. Я
нарошно не буду выписывать, а вы мысленно обозначьте (a :& ) за f и constStream a за fix f. Получилось?
Через fix можно очень просто определить бесконечность для Nat, бесконечность это цепочка Succ, ко-
торая никогда не заканчивается Zero. Оказывается, что в Haskell мы можем составлять выражения с такими
значениями (как это получается мы обудим попозже):
ghci Nat
*Nat> m + Data.Function
*Nat Data.Function> let infinity = fix Succ
*Nat Data.Function> infinity < Succ Zero
False
С помощью функции fix можно выразить любую рекурсивную функцию. Посмотрим как на примере
функции foldNat, у нас есть рекурсивное определение:
foldNat :: a -> (a -> a) -> Nat -> a
foldNat z
s
Zero
= z