Unknown - haskell-notes

label a =fmap (m M.!) a

wherem = M.fromList $flip zip [’a’ ..] $nub $elems a

11.4 Ленивее некуда

Мы выяснили, что значение может редуцироваться только при сопоставлении с образцом и в специальной

функции seq. Функцию seq мы можем применять, а можем и не применять. Но кажется, что в декомпозиции

мы не можем уйти от необходимости проведения хотя бы одной редукции. Оказывается можем, в Haskell для

этого предусмотрены специальные ленивые образцы (lazy patterns). Они обозначаются знаком тильда:

lazyHead ::[a] ->a

lazyHead ~(x :xs) =x

Перед скобками сопоставления с образцом пишется символ тильда. Этим мы говорим вычислителю: до-

верься мне, здесь точно такой образец, можешь даже не проверять дальше. Он и правда дальше не пойдёт.

Например если мы напишем такое определение:

lazySafeHead ::[a] -> Maybea

lazySafeHead ~(x :xs) = Justx

lazySafeHead []

= Nothing

Если мы подставим в эту функцию пустой список мы получим ошибку времени выполнения, вычислитель

доверился нам в первом уравнении, а мы его обманули. Сохраним в модуле Strictи проверим:

Prelude Strict> :!ghc --make Strict

[1 of1] Compiling Strict

( Strict.hs, Strict.o )

Strict.hs :67 :0 :

Warning: Patternmatch(es) are overlapped

Inthe definition of‘lazySafeHead’ :lazySafeHead [] = ...

Prelude Strict> :l Strict

Ok, modules loaded : Strict.

Prelude Strict>lazySafeHead [1,2,3]

Just1

Prelude Strict>lazySafeHead []

Just *** Exception: Strict.hs :(67,0) -(68,29) : Irrefutable

pattern failed for pattern (x :xs)

При компиляции нам даже сообщили о том, что образцы в декомпозиции пересекаются. Но мы были

упрямы и напоролись на ошибку, если мы поменяем образцы местами, то всё пройдёт гладко:

Prelude Strict> :!ghc --make Strict

[1 of1] Compiling Strict

( Strict.hs, Strict.o )

Prelude Strict> :l Strict

Ok, modules loaded : Strict.

Prelude Strict>lazySafeHead []

Nothing

188 | Глава 11: Ленивые чудеса

Отметим, что сопоставление с образцом в letи whereвыражениях является ленивым. Функцию lazyHead

мы могли бы написать и так:

lazyHead a =x

where(x :xs) =a

lazyHead a =

let(x :xs) =a

in

x

Посмотрим как используются ленивые образцы при построении потоков, или бесконечных списков. Мы

будем представлять функции одного аргумента потоками значений с одинаковым шагом. Так мы будем пред-

ставлять непрерывные функции дискретными сигналами. Считаем, что шаг дискретизации (или шаг между

соседними точками) нам известен.

f : R → R ⇒ fn = f ( nτ ) ,

n = 0 , 1 , 2 , ...

Где τ – шаг дискретизации, а n пробегает все натуральные числа. Определим функцию решения диффе-

ренциальных уравнений вида:

dx = f ( t )

dt

x (0) = ˆ

x

Символ ˆ x означает начальное значение функции x . Перейдём к дискретным сигналам:

xn−xn− 1 = f

τ

n,

x 0 = ˆ

x

Где τ – шаг дискретизации, а x и f – это потоки чисел, индекс n пробегает от нуля до бесконечности

по всем точкам функции, превращённой в дискретный сигнал. Такой метод приближения дифференциаль-

ных уравнений называют методом Эйлера. Теперь мы можем выразить следующий элемент сигнала через

предыдущий.

xn = xn− 1 + τ fn, x 0 = ˆ

x

Закодируем это уравнение:

-- шаг дискретизации

dt :: Fractionala =>a

dt =1e-3

-- метод Эйлера

int :: Fractionala =>a ->[a] ->[a]

int x0 (f :fs) =x0 :int (x0 +dt *f) fs

Смотрите в функции int мы принимаем начальное значение x0 и поток всех значений функции пра-

вой части уравнения, поток значений функции f ( t ). Мы помещаем начальное значение в первый элемент

результата, а остальные значения получаем рекурсивно.

Определим две вспомогательные функции:

time :: Fractionala =>[a]

time =[0, dt ..]

dist :: Fractionala => Int ->[a] ->[a] ->a

dist n a b =( /fromIntegral n) $