1. Серія контенту:
2. Цей контент є частиною серії: Функціональне програмування на Haskell
3. Права та ліва згортка: foldl1, foldr1
4. Узагальнення на випадок пустого списку: foldl, foldr
5. додаткові приклади
6. ++
7. concatMap
8. elem
9. filter, partition
10. intersperse, intercalate
11. прогони
12. обчислення згорток
13. дерева згорток
14. Рис. 1. Дерево списку [1,2,3,4]
15. Рис. 2. Дерево вираження 1 + (2 + (3 + (4 + 0)))
16. Рис. 3. Дерево вираження (((0 + 1) + 2) + 3) + 4
17. Згортка нескінченного списку
18. «Сувора» згортка foldl '
19. Рис. 4. Дерево вираження 1 + (2 + (3 + (4 + ...)))
20. Висновок
21. Ресурси для скачування

Функціональне програмування на Haskell

Серія контенту:

Цей контент є частиною # з серії # статей: Функціональне програмування на Haskell

https://www.ibm.com/developerworks/ru/library/?series_title_by=**auto**

Слідкуйте за виходом нових статей цієї серії.

Цей контент є частиною серії: Функціональне програмування на Haskell

Слідкуйте за виходом нових статей цієї серії.

Права та ліва згортка: foldl1, foldr1

Для початку ми розберемо дуже просту і поширену задачу і то, як вона вирішується в функціональних мовах програмування. Нехай потрібно знайти мінімальний елемент в списку. Запишемо рекурсивне визначення мінімального елемента:

1. Якщо список складається з одного елемента x, то мінімальний елемент - x.
2. Якщо список складається з двох і більше елементів, то можна порівняти перший елемент x з мінімальним елементом x 'серед решти в хвості xs. Якщо x менше або дорівнює x ', то мінімальний елемент - x, інакше - x'.

У другому випадку використовується обчислення мінімуму серед двох елементів, для якого можна виділити спеціальну функцію min.

min :: (Ord a) => a -> a -> a min xy = if x <= y then x else y

Ця функція, як і практично всі інші, з якими ми будемо працювати, вже є в Prelude (вона визначена для класу Ord).

Назвемо цікаву для нас функцію для пошуку мінімуму в списку minimum. Її визначення складатиметься з двох рівнянь, відповідних словесному опису вище.

minimum :: (Ord a) => [a] -> a minimum [x] = x minimum (x: xs) = min x (minimum xs)

Розглянемо, як це буде обчислюватися, на прикладі списку [3,1,9,0,5]:

minimum [3,1,9,0,5] = min 3 (minimum [1,9,0,5]) = min 3 (min 1 (minimum [9,0,5])) = min 3 (min 1 (min 9 (minimum [0,5]))) = min 3 (min 1 (min 9 (min 0 (minimum [5])))) = min 3 (min 1 (min 9 (min 0 5))) = min 3 (min 1 (min 9 0)) = min 3 (min 1 0) = min 3 0 = 0

Але якщо нам буде потрібно знайти в списку максимум? Міркування будуть точно такими ж:

max :: (Ord a) => a -> a -> a max xy = if x> = y then x else y maximum :: (Ord a) => [a] -> a maximum [x] = x maximum (x: xs) = max x (maximum xs) maximum [3,1,9,0,5] = max 3 (maximum [1,9,0,5]) = max 3 (max 1 (maximum [9, 0,5])) = max 3 (max 1 (max 9 (maximum [0,5]))) = max 3 (max 1 (max 9 (max 0 (maximum [5])))) = max 3 ( max 1 (max 9 (max 0 5))) = max 3 (max 1 (max 9 5)) = max 3 (max 1 9) = max 3 9 = 9

Простежується загальний шаблон: обчислення обох функцій засноване на тому, що за списком [x1, x2, ..., xn-1, xn] будується вираз

f x1 (f x2 (... (f xn-1 xn))),

де f - деяка функція, причому, якщо список має тип [a], то f повинна мати тип a -> a -> a. В одному випадку це min, а в іншому - max.

Вираз f x1 (f x2 (... (f xn-1 xn))) називається правою сверткой (right fold) списку [x1, x2, ..., xn] за допомогою функції f.

За аналогією можна ввести ліву згортку (left fold):

f (f ((f x1 x2) ...) xn-1) xn.

У більш звичною інфіксной записи права і ліва згортка виглядають так (нагадаємо, що застосування функції можна записати інфіксне, якщо взяти ім'я функції в зворотні лапки ``):

x1 `f` x2 (... (` f` (xn-1 `f` xn))), (((x1` f` x2) `f` ...)` f` xn-1) `f `xn.

На прикладах для мінімуму і максимуму видно, що зручно домовитися, що згортка списку з одного елемента дорівнює цьому елементу.

Як ви могли здогадатися, для мінімуму і максимуму різниці між цими пакунками немає, тому що для всіх a, b і c

a `min` (b` min` c) = (a `min` b)` min` c, a `max` (b` max` c) = (a `max` b)` max` c.

Результат від розстановки дужок не залежить; тобто операції min і max асоціативні. У загальному випадку згортка здійснюється неассоціатівное операцією, тому важливо розрізняти ліву і праву згортку. Крім того, як ми побачимо далі, обчислення лівої і правої згортки значно відрізняється.

Функціональний підхід заохочує винесення часто використовуваних шаблонів в функції вищого порядку; в даному випадку ми можемо узагальнити визначення функції minimum, замінивши в ньому min на довільну функцію f. Назвемо узагальнену функцію foldr1:

foldr1 :: (a -> a -> a) -> [a] -> a foldr1 f [x] = x foldr1 f (x: xs) = fx (foldr1 f xs)

foldr1 обчислює праву згортку, тому її можна також називати правою сверткой.

Запишемо тепер ліву згортку foldl1.

foldl1 :: (a -> a -> a) -> [a] -> a foldl1 f [x] = x foldl1 f (x: (y: ys)) = foldl1 f (fxy: ys)

В Prelude визначені саме такі функції.

Тут результат згортки передається вглиб рекурсивних викликів у вигляді голови списку.

Якщо переписати наші визначення minimum і maximum через згортки, то отримаємо

minimum = foldr1 min maximum = foldr1 max

(Нагадаємо, що рівняння minimum = foldr1 min еквівалентно minimum xs = foldr1 min xs.)

Крім того, можна використовувати визначення:

minimum = foldl1 min maximum = foldl1 max

Зверніть увагу на відмінності в другому рівнянні для foldr1 і foldl1: значенням foldr1 f (x: xs) вважається результат застосування f, а значенням foldl1 f (x: (y: ys)) - результат застосування такої самої функції foldl1.

Якщо результатом рекурсивного виклику функції вважається результат виклику тієї ж функції, то така рекурсія називається хвостовій , А функція - хвосторекурсівной.

Таким чином, foldl1, на відміну від foldr1, хвосторекурсівна.

У функціональних мовах хвостова рекурсія має наступний практичний сенс: якщо рекурсивний виклик хвостовій, то інтерпретатор може не розміщувати елементи в стеку. Розглянемо характерний приклад визначення:

length :: [a] -> Int length [] = 0 length (x: xs) = length xs + 1

Ця функція обчислює довжину списку.

Така рекурсія не є хвостовий, тому що значенням length (x: xs) вважається результат застосування (+), а не length. Ситуацію можна змінити, якщо ввести допоміжну функцію length ', яка накопичує результат в своєму аргументі:

length xs = let length 'n [] = n length' n (x: xs) = length '(n + 1) xs in length' 0 xs

Але позбулися ми від проблеми переповнення стека? Насправді, в силу ленивости Haskell, обчислення (n + 1) буде до останнього відкладатися! Ми залишимо поки подробиці і повернемося до нашого розгляду згорток.

Розглянемо функцію:

paren :: String -> String -> String paren xy = concat [ "(", x, "*", y, ")"]

З нею зручно простежити, як будуються праві і ліві згортки:

ghci> foldr1 paren [ "a", "b", "c", "d"] "(a * (b * (c * d)))" ghci> foldl1 paren [ "a", "b", " c "," d "]" (((a * b) * c) * d) "

Якщо операція, по якій проводиться згортка, асоціативна, то можна просто думати про розстановку оператора між елементами. наприклад,

foldr1 (+) [x1, x2, ..., xn] = x1 + x2 + ... + xn, foldr1 (*) [x1, x2, ..., xn] = x1 * x2 * ... * xn.

Значить, foldr1 (+) і foldr1 (*) висловлюють суму і твір:

ghci> foldr1 (+) [1..5] 15 ghci> foldr1 (*) [1..5] 120

Узагальнення на випадок пустого списку: foldl, foldr

Повернемося до прикладу функції length з попереднього розділу. Її можна теж розглядати як праву згортку деякою функцією f. Однак для порожнього списку length [] = 0, в той час, як наші визначення foldr1 і foldl1 взагалі не спрацьовують для [].

Розумно розширити значення згортки для порожнього списку, спираючись в рекурсивном визначенні на цей випадок. Назвемо узагальнені функції foldr і foldl:

foldr :: (a -> b -> b) -> b -> [a] -> b foldr f x0 [] = x0 foldr f x0 (x: xs) = fx (foldr f x0 xs) foldl :: ( b -> a -> b) -> b -> [a] -> b foldl f x0 [] = x0 foldl f x0 (x: xs) = foldl f (f x0 x) xs

Таким чином, базове значення x0 як би дописується в початок (при foldl) або в кінець (при foldr) списку, після чого вже проводиться згортка; якщо контактів немає, то результатом згортки вважається x0.

f x1 (f x2 (... (f xn-1 (f xn x0)) ...)), f (f (... (f (f x0 x1) x2) ...) xn-1) xn.

Зверніть увагу на відмінності в типах foldl1 і foldl, foldr1 і foldr.

Нехай функція довжини повинна виражатися через ліву згортку функцією f (n, x), де x - елемент списку, а n - накопичене значення згортки. Довжина не залежить від значень елементів і збільшується на 1 при переході до наступного елементу, тому:

fnx = n + 1.

маємо:

length :: [a] -> Int length = foldl (\ n _ -> n + 1) 0

Це визначення автоматично буде хвосторекурсівним, тому що ліва згортка хвосторекурсівна. Якщо нас це не сильно турбує, то, очевидно, ми можемо замінити ліву згортку на праву.

Відповідно до нового визначенням foldl можна дати більш акуратне визначення foldl1:

foldl1 f (x: xs) = foldl fx xs

приклад:

ghci> foldr paren "1" [ "a", "b", "c", "d"] "(a * (b * (c * (d * 1))))" ghci> foldl paren "1" [ "a", "b", "c", "d"] "((((1 * a) * b) * c) * d)"

Розумно вимагати, щоб узагальнені згортки foldr і foldl узгоджувалися з пакунками foldr1 і foldl1. Це накладає певні обмеження для базового значення, яке відповідає нагоди порожнього списку.

Для будь-якого без порожнього списку xs

foldl fx xs = foldl1 f xs

буде виконуватися, тільки якщо для всіх x

fxx = x;

такий елемент x0 називається лівої одиницею операції f. (Ця термінологія заснована на аналогії з множенням на 1.)

Аналогічно, якщо для всіх не порожніх xs

foldr fx xs = foldr1 f xs,

то необхідно, щоб для всіх x виконувалося

fxx = x;

тобто x0 повинен бути правою одиницею f.

Наприклад, для множення лівої і правої, одиницею буде 1, а для складання - 0. Тому функції sum і product вводяться наступним чином:

sum :: (Num a) => [a] -> a sum = foldr (+) 0 product :: (Num a) => [a] -> a product = foldr (*) 1

Факторіал можна записати у вигляді:

fac :: Integral a => a -> a fac n = product [1..n]

Аналогічно, для логічного І та логічного АБО:

and :: [Bool] -> Bool and = foldr (&&) True or :: [Bool] -> Bool or = foldr (||) False

Зверніть увагу: True - це одиниця для логічного І, а False - це одиниця для логічного АБО.

Для конкатенації двох списків використовується бінарний оператор ++ (ми ще розглянемо, як реалізувати її через згортки). Одиницею у конкатенації є порожній список []. Значить, конкатенацію n списків можна записати у вигляді:

concat :: [[a]] -> [a] concat = foldr (++) []

У операції не обов'язково повинна бути ліва або права одиниця - це можжет вказувати на те, що потрібно використовувати foldl1 і foldr1.

додаткові приклади

amean

Вище ми вже визначили функції для обчислення суми і довжини списку. Розумно записати функцію для обчислення середнього арифметичного:

amean xs = let s = sum xs n = (fromIntegral.length) xs in s / n

Але що відбувається при обчисленні? Спочатку ми проходимо весь список, обчислюючи суму, а потім знову проходимо його, обчислюючи довжину.

Можна відразу накопичувати результат в парі, яке береже суму елементів і їх кількість. Якщо згортка права, то першим аргументом згортати функції повинен бути поточний елемент, а другим - накопичене значення. Тут згортка буде здійснюватися функцією

Y x (y, n) -> (x + y, n + 1)

(Щоб не плутатися, запам'ятайте, що в правій згортку накопичене значення стоїть праворуч, а в лівій - зліва.)

Отримуємо функцію:

amean :: (Fractional a) => [a] -> a amean xs = s / n where (s, n) = foldr (\ x (y, n) -> (x + y, n + 1)) ( 0,0) xs

Якщо ви пам'ятаєте, що таке uncurry:

amean = uncurry (/). foldr (\ x (y, n) -> (x + y, n + 1)) (0,0)

Для порожнього списку [] функція буде обчислювати 0/0 і давати значення NaN (Not a Number, невизначеність числовий результат). Якщо це неприйнятно, то краще, звичайно, доопределить:

amean [] = 0

Або видавати помилку при порожньому списку.

Тепер ми випишемо компактні визначення для стандартних функцій, використовуючи згортки.

++

Як реалізувати операцію конкатенації ++?

Щоб обчислити xs ++ ys, можна додавати до початку ys по одному елементу xs, починаючи з кінця.

Як перейти від цієї ідеї до пакунку?

• Слова «по одному елементу xs» вказують, що згортається xs.
• Далі, «починаючи з кінця» означає, що згортка права.
• «Додавати до ys» говорить про те, що ys буде вихідним значенням.
• Операції приєднання вперед відповідає (:).

Це буквально оформляється в рівняння:

(++) :: [a] -> [a] -> [a] (++) xs ys = foldr (:) ys xs reverse

Звернення списку можна визначити рекурсивно:

reverse [] = [] reverse (x: xs) = (reverse xs) ++ [x]

наприклад,

reverse [1,2,3] = reverse [2,3] ++ [1] = = reverse [3] ++ [2] ++ [1] = = reverse [] ++ [3] ++ [2 ] ++ [1] = = [] ++ [3] ++ [2] ++ [1] = = [3,2,1]

Видно, що ми здійснюємо праву згортку функцією Y xy -> y ++ [x]. Звідси:

reverse = foldr (\ xy -> y ++ [x]) []

Ми отримали акуратний код, заснований на визначенні звернення списку, однак приєднання в кінець ++ [x] - дорога операція, на відміну від зняття і додавання голови.

Розглянемо інший варіант: нехай є списки xs і ys. На початковому етапі xs буде вихідним списком, а ys - порожнім. Ми будемо послідовно знімати голову з xs і додавати до ys. Як тільки xs буде порожнім списком, ys буде містити елементи xs, записані в зворотному порядку.

На прикладі списку [1,2,3] це виглядає так:

xs ys 1: 2: 3: [] [] 2: 3: [] 1: [] 3: [] 2: 1: [] [] 3: 2: 1: []

Запис у вигляді рекурсивної функції:

reverse xs = iter xs [] where iter [] ys = ys iter (x: xs) ys = iter (x: ys) xs

Тут результат накопичується в ys; початкове значення - []. Згортка ліва, тому що ми проходимо xs від початку до кінця. Маємо функцію для згортки Y ys x -> x: ys, тобто flip (:). Отримуємо остаточне рішення:

reverse :: [a] -> [a] reverse = foldl (flip (:)) []

- для великих списків це набагато швидше, ніж варіант з правого сверткой!

map

У попередній статті ми вже розібрали, що таке відображення списку, а також записали рекурсивне визначення:

map _ [] = [] map f (x: xs) = fx: map f xs

Після прикладів вище, нескладно розібратися, що тут виробляється права згортка функцією Y x xs -> fx: xs. Більш компактно її можна записати у вигляді (:). f.

map :: (a -> b) -> [a] -> [b] map f = foldr ((:). f) []

concatMap

Функція concatMap працює як map, але також склеює результати відображення:

concatMap f [x1, x2, ..., xn] = f x1 ++ f x2 ++ ... ++ f xn.

Завдання вирішується аналогічно map. Звертати потрібно функцією Y x xs -> fx ++ xs, яка більш компактно записується бесточечно як (++). f.

concatMap :: (a -> [b]) -> [a] -> [b] concatMap f = foldr ((++). f) []

elem

elem x xs - предикат, що виражає приналежність x списку xs. Рекурсивне визначення:

elem x [] = False elem x (x ': xs) = if x == x' then True else elem x xs

Очевидна запис через згортку:

elem :: (Eq a) => a -> [a] -> Bool elem x = foldl (\ sx '-> if x' == x then True else s) False

filter, partition

Функція filter f xs для предиката f і списку xs обчислює список, що містить елементи, які задовольняють предикату. Вона схожа на map, тільки функція згортки буде не приєднувати fx до хвоста, а перевіряти значення fx і в залежності від нього приєднувати x:

filter :: (a -> Bool) -> [a] -> [a] filter f = foldr (\ x xs -> if fx then x: xs else xs) []

partition повертає пару з двох списків: задовольняє і не задовольняє предикату.

partition :: (a -> Bool) -> [a] -> ([a], [a]) partition f = foldr iteratee ([], []) where iteratee x (xs, xs ') = if fx then (x: xs, xs ') else (xs, x: xs')

приклад:

ghci> partition Data.Char.isUpper "Avoid success at all costs" ( "A", "void success at all costs") ghci> filter Data.Char.isUpper "Avoid success at all costs" "A"

intersperse, intercalate

Функція intersperse повинна приймати елемент x і список xs і повертати список, в якому x стоїть між кожним елементом xs.

Реалізація може спиратися на послідовне приєднання до порожнього списку елементів xs. Причому якщо приєднання здійснюється до непорожньої списку, то перед черговим елементом приєднується x.

intersperse :: a -> [a] -> [a] intersperse x = foldr f [] where fx 'xs = x': if null xs then xs else x: xs

intercalate працює схожим чином, але розміщує даний список між списками і склеює результат (тип [a] -> [[a]] -> [a]). Реалізація така ж, тільки: потрібно замінити на ++.

intercalate x = foldr f [] where fx 'xs = x' ++ if null xs then xs else x ++ xs

З іншого боку, краще використовувати визначення:

intercalate :: [a] -> [[a]] -> [a] intercalate x xs = concat $ intersperse x xs

приклади:

ghci> intersperse '' "Avoid success at all costs" "A voidsuccessatallcosts" ghci> intercalate "" [ "Avoid", "success", "at", "all", "costs"] "Avoid success at all costs"

прогони

Окремо варто розглянути прогін (scan) - близьку до пакунку операцію, яка замість одного згорнутого значення повертає список послідовних згорток. Для лівого прогону

scanl f x0 [x1, x2, ...] = [x0, x0 `f` x1, (x0` f` x1) `f` x2, ...]

першим елементом прогону буде початкове значення, а останнім - результат лівої згортки.

Визначення scanl:

scanl :: (a -> b -> a) -> a -> [b] -> [a] scanl _ x0 [] = [x0] scanl f x0 (x: xs) = x0: scanl f (f x0 x) xs

За аналогією з тим, як foldl1 був визначений через foldl:

scanl1 :: (a -> a -> a) -> [a] -> [a] scanl1 _ [] = [] scanl1 f (x: xs) = scanl fx xs

приклад:

ghci> scanl1 paren [ "a", "b", "c"] [ "a", "(a * b)", "((a * b) * c)"] ghci> scanl paren "1" [ "a", "b", "c"] [ "1", "(1 * a)", "((1 * a) * b)", "(((1 * a) * b) * c ) "]

Як можна здогадатися, правий прогін повинен містити початкове значення в якості останнього елемента і результат правої згортки в якості першого.

scanr :: (a -> b -> b) -> b -> [a] -> [b] scanr _ x0 [] = [x0] scanr f x0 (x: xs) = fxx ': (x': xs ') where (x': xs ') = scanr f x0 xs scanr1 :: (a -> a -> a) -> [a] -> [a] scanr1 _ [] = [] scanr1 _ [x0] = [x0] scanr1 f (x: xs) = fxx ': (x': xs ') where (x': xs ') = scanr1 f xs

приклад:

ghci> scanr1 paren [ "a", "b", "c"] [ "(a * (b * c))", "(b * c)", "c"] ghci> scanr paren "1" [ "a", "b", "c"] [ "(a * (b * (c * 1)))", "(b * (c * 1))", "(c * 1)", " 1 "]

Зверніть увагу, що, за угодою, прогони scanl1 і scanr1 порожнього списку визначені та є рівними порожньому списку, а згортки foldl1 і foldr1 для порожніх списків не визначені.

обчислення згорток

До теперішнього моменту ми практично не вдавалися в відмінності між правою і лівою сверткой в ​​разі асоціативної операції. Тепер розберемося докладніше, що відбувається при обчисленні.

Ми покажемо в цьому розділі ситуації, в яких проявляється специфіка ледачих обчислень. Не хвилюйтеся - це більше мотивують приклади, і вони випереджають серйозна розмова про обчисленнях, який чекає нас в наступних статтях.

дерева згорток

Розглянемо згортку списку [1,2,3,4] за допомогою (+). Якщо згадати, що запис [1,2,3,4] - це просто скорочення для 1: (2: (3: (4: []))), то дерево списку виглядає так:

Рис. 1. Дерево списку [1,2,3,4]

Правою згортку foldr (+) 0 [1..4] відповідає вираз 1 + (2 + (3 + (4 + 0))) з наступним деревом:

Рис. 2. Дерево вираження 1 + (2 + (3 + (4 + 0)))

Тобто в дереві порожній список [] був замінений на початкове значення 0, а конструктори: у вузлах - на операцію +. Лівою сверткой буде (((0 + 1) + 2) + 3) + 4 з наступним деревом:

Рис. 3. Дерево вираження (((0 + 1) + 2) + 3) + 4

При правої згортку дерево будується зверху вниз. На нашому прикладі можна зробити висновок, що обчислення проводиться знизу вгору (тобто, потрібно рекурсивно спуститися вниз дерева, і вже звідти виробляти складання), але це лише тому, що (+) є суворої по обом аргументів. Для несуворого оператора це не обов'язково так.

Згортка нескінченного списку

Розглянемо

kxy = x

Звернемо цією функцією нескінченний список з усіх позитивних цілих чисел. Права згортка дасть 1:

foldr1 k [1 ..] = (\ xy -> x) 1 (foldr1 k [2 ..]) = 1

Але для лівої згортки дерево буде будуватися нескінченно, і результат не буде знайдений:

foldl1 k [1 ..] = foldl1 k (k 1 2) [3 ..] = = foldl1 k (k (k 1 2) 3) [4 ..] = = foldl1 k (k (k (k 1 2 ) 3) 4) [5 ..] = = ...

Зауважте, що операція асоціативна - для всіх x, y, z виконується

(X `k` y)` k` z = x `k` y = x, x` k` (y `k` z) = x.

Тому вся справа в прийнятому порядку обчислення.

При лівої згортку дерево будується знизу вгору, і останні елементи знаходяться в вершині. Значить, для нескінченного списку ліву згортку обчислити не можна.

«Сувора» згортка foldl '

Цікаво розглянути обчислення для суворої операції і кінцевого, але досить великого списку:

foldr1 (+) [1..10 ^ 6] = (+) 1 (foldr1 (+) [2..10 ^ 6]) = = (+) 1 ((+) 2 (foldr1 (+) [3. .10 ^ 6])) = = (+) 1 ((+) 2 ((+) 3 (foldr1 (+) [4..10 ^ 6]))) = = ...

Функція (+) вимагає, щоб обидва аргументи були обчислені. Як ми вже помітили, в цьому випадку наступне дерево будується до кінця, а потім вже обчислюється від низу до верху:

Рис. 4. Дерево вираження 1 + (2 + (3 + (4 + ...)))

При обчисленні заповнюється стек, і вираз на кшталт foldr1 (+) [1..10 ^ 6] може взагалі не вирахували - буде видано повідомлення «Exception: stack overflow».

Але з foldl1 інша справа:

foldl1 (+) [1..10 ^ 6] = foldl (+) ((+) 1 2) [3..10 ^ 6] = = foldl (+) ((+) ((+) 1 2) 3 ) [4..10 ^ 6] = = foldl (+) ((+) ((+) ((+) 1 2) 3) 4) [5..10 ^ 6] = = ...

Вираз ((+) ((+) ((+) 1 2) 3) ...) буде тягнутися по ходу обчислень не тому, що не може бути обчислено, а тому, що прийнятий порядок редукції вказує, що редукується лівий зовнішній редекс - тут це застосування аргументу [i..10 ^ 6].

У той же час, в енергійному мовою обчислення буде проводитися відразу, так що там ліва (як ми вже переконалися, хвосторекурсівная) згортка точно буде краще. (Однак в енергійному мовою наш приклад, що переповнює стек, теж не буде нешкідливим - там вираз на кшталт [1..10 ^ 6] буде відразу обчислено в список з мільйона елементів.)

Як вирішити проблему в ледачому мовою? У Haskell є спеціальна функція:

seq :: a -> b -> b

яка спочатку призводить перший аргумент в слабку головний нормальну форму (СГНФ), тобто редукує до отримання зовнішньої частини - значення функції або конструктора, а потім повертає другий.

Таким чином, якщо в seq xy вираз x міститиметься в y як подвираженія, то в результаті ми отримаємо y з наведеним подвираженіем x.

Тому можна визначити «суворе застосування функції»:

f $! x = x `seq` fx

Повернемося до визначення:

foldl f x0 (x: xs) = foldl f (fxx) xs

Тут нас цікавить виділена частина, позначимо її за red. Визначимо foldl 'таким чином, щоб red редуцировалось:

foldl ':: (a -> b -> a) -> a -> [b] -> a foldl' f x0 (x: xs) = let red = f x0 x in seq red $ foldl 'f red xs foldl1 ':: (a -> a -> a) -> [a] -> a foldl1' f (x: xs) = foldl 'fx xs

Завдяки такому підходу до обчислення, foldl 'іноді називається «суворої лівої сверткой».

В результаті foldl '(+) 0 [1..10 ^ 6] воно не наповнюється стек, на відміну від foldl (+) 0 [1..10 ^ 6] - можете перевірити в своїй системі на досить великому списку доданків.

Але насправді «суворе застосування» $! або «сувора згортка» foldl "не співвідносяться безпосередньо зі строгістю. Як ми вже помітили, приведення в СГНФ просто дає вираз, в якому немає редекса на верхньому рівні, це не те ж саме, що і повна редукція!

foldl 'добре працює для (+) і інших найпростіших випадків. Якщо мова йде про більш складних функціях, то в міру проходу списку в пам'яті точно також будуть накопичуватися відкладені обчислення. Для нескінченного списку результат ми взагалі не отримаємо.

У foldr ж відкладені обчислення накопичуються тільки у вигляді застосування foldr до хвоста списку.

Таким чином, хоча foldl і хвосторекурсівен, це корисно тільки в енергійних мовами, а для ледачих мов на зразок Haskell кращий foldr, але в простих випадках можна імітувати енергійність через foldl '.

Тепер ми можемо переглянути наші приклади. У визначенні length функцію foldl можна замінити на foldl ':

length = foldl '(\ n _ -> n + 1) 0

Крім того, можна перевести amean на foldl '. Наївний підхід був би таким:

amean '= uncurry (/). foldl '(\ (y, n) x -> (x + y, n + 1)) (0,0)

Але foldl 'буде тільки давати СГНФ для (x + y, n + 1), де зовнішнім рівнем є конструктор пари. Тобто (x + y, n + 1) вже знаходиться в СГНФ! Для потрібного ефекту seq потрібно застосовувати для x і n:

amean '= uncurry (/). foldl '(\ (y, n) x -> x `seq` n` seq` (x + y, n + 1)) (0,0)

У GHC є розширення bang patterns , Яке дозволяє вказувати шаблон! P, такий, що вираз при зіставленні з ним наводиться в СГНФ. Якщо використовувати ghc з прапором -XBangPatterns, то можна обійтися записом:

amean '= uncurry (/). foldl '(\ (! y,! n) x -> (x + y, n + 1)) (0,0)

На закінчення скажемо, що визначення foldr, foldl, foldr1, foldl1, scanr, scanl, scanr1, scanl1 можна знайти в Prelude. foldl 'і foldl1' є в Data.List .

Висновок

Ідея згортки може бути застосована для багатьох типів даних крім списків; наприклад, згортки визначені для Data.Map и Data.Set .

Якщо функція має на увазі згортку, то набагато краще висловлювати її через зумовлені функції fold, ніж щоразу виписувати рекурсивні визначення - код з пакунками легше читати, писати і аналізувати (при наявності відповідного досвіду).

У пакунку простежується «поділ обов'язків» між функцією вищого порядку і передається функцією, якої виробляється згортка.

Функція начебто fold піклується про те, як працювати з ресурсом і переходити до наступного елементу структури даних, тому називається перечіслітеля (enumerator).

Навпаки, передана fold функція нічого не знає про ресурс і піклується тільки про елементарну операції над елементами, цю функцію можна назвати ітеріруемой (iteratee).

Наприклад, функція

Data.Set.fold (+) 0

обчислює суму елементів множини. fold тут є перечіслітеля і відповідає за вилучення елементів структури даних і реалізує загальну схему згортки, а (+) є ітеріруемой функцією і може тільки переводити пару чисел в їх суму.

0 в цьому прикладі є ініціалізувалися значенням (seed) і також відноситься до ітеріруемому.

Таким чином, ітеріруемое є пару з функції і не започатковано значення (в сумах і творах останнім грає роль акумулятора).

Цей підхід дозволяє будувати досить складні згортки.

Наостанок наведемо (неповний) список мов, в яких також можна знайти згортки - безпосередньо або через додаткові модулі і бібліотеки. Замість слова fold в назвах функцій і відповідних операцій може вживатися reduce або accumulate.

• Clojure: reduce ;
• Common Lisp: reduce ;
• C ++: std :: accumulate ;
• Erlang: foldl , foldr ;
• Maxima: lreduce, rreduce ;
• OCaml: List.fold_left, List.fold_right ;
• Perl 5: reduce ;
• Perl 6: reduction metaoperator ;
• Python: reduce , functools.reduce ;
• Ruby: enum.inject, enum.reduce ;
• Scala: foldLeft, foldRight, reduceLeft, reduceRight ;
• Scheme R6RS: fold-left , fold-right ;
• Standard ML: foldl , foldr .

Документи, що додаються файли: fph04.lhs .

Ресурси для скачування

Схожі тими

Підпішіть мене на ПОВІДОМЛЕННЯ до коментарів