Unknown - haskell-notes

Зачем нам такая функция? Помните в самом конце четвёртой главы в упражнениях мы составляли бес-

конечные потоки. Мы делали это так:

data Streama =a :& Streama

constStream ::a -> Streama

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> letinfinity =fix Succ

*Nat Data.Function>infinity < Succ Zero

False

С помощью функции fix можно выразить любую рекурсивную функцию. Посмотрим как на примере

функции foldNat, у нас есть рекурсивное определение:

foldNat ::a ->(a ->a) -> Nat ->a

foldNat z

s

Zero

=z

foldNat z

s

( Succn)

=s (foldNat z s n)

Необходимо привести его к виду:

x =f x

Слева и справа мы видим повторяются выражения foldNat z s, обозначим их за x:

x :: Nat ->a

x Zero

=z

x ( Succn)

=s (x n)

Теперь перенесём первый аргумент в правую часть, сопоставление с образцом превратится в case-

выражение:

x :: Nat ->a

x =\nat -> casenat of

Zero

->z

Succn

->s (x n)

В правой части вынесем x из выражения с помощью лямбда функции:

x :: Nat ->a

x =(\t ->\nat -> casenat of

Zero

->z

Succn

->s (t n)) x

Смотрите мы обозначили вхождение x в выражении справа за t и создали лямбда-функцию с таким ар-

гументом. Так мы вынесли x из выражения.

Получилось, мы пришли к виду комбинатора неподвижной точки:

x :: Nat ->a

x =f x

wheref =\t ->\nat -> casenat of

Zero

->z

Succn

->s (t n)

Приведём в более человеческий вид:

foldNat ::a ->(a ->a) ->( Nat ->a)

foldNat z s =fix f

wheref t =\nat -> casenat of

Zero

->z

Succn

->s (t n)

Комбинатор неподвижной точки | 83

5.6 Краткое содержание

Основные функции высшего порядка

Мы познакомились с функциями из модуля Data.Function. Их можно разбить на несколько типов:

• Примитивные функции (генераторы функций).

id

=\x ->x

const a =\ _ ->a

• Функции, которые комбинируют функции или функции и значения:

f .g

=\x ->f (g x)

f $x

=f x

( .*.) ‘on‘ f =\x y ->f x .*.f y

• Преобразователи функций, принимают функцию и возвращают функцию:

flip f =\x y ->f y x

• Комбинатор неподвижной точки:

fix f = letx =f x

in

x

Приоритет инфиксных операций

Мы узнали о специальном синтаксисе для задания приоритета применения функций в инфиксной форме:

infixl3 #

infixr6 ‘op‘

Приоритет складывается из двух частей: старшинства (от 1 до 9) и ассоциативности (бывает левая и

правая). Старшинство определяет распределение скобок между разными функциями:

infixl6 +

infixl7 *

1 +2 *3 ==1 +(2 *3)

А ассоциативность – между одинаковыми:

infixl6 +

infixr8 ^

1 +2 +3 ==(1 +2) +3

1 ^2 ^3 ==

1 ^(2 ^3)

Мы узнали, что функции ( $) и ( .) стоят на разных концах шкалы приоритетов функций и как этим

пользоваться.

5.7 Упражнения

• Просмотрите написанные вами функции, или функции из примеров. Можно ли их переписать с по-

мощью основных функций высшего порядка? Если да, то перепишите. Попробуйте определить их в

бесточечном стиле.