Реалізація стека, черги і дека на мові F # у функціональному стилі

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

Стек

Перш за все почнемо зі стека. У F # основним типом даних для зберігання кількох однотипних елементів є не масив, а список. Якщо перед нами стоїть завдання перетворити список в стек, то які функції нам знадобляться?
 
По-перше, нам необхідна функція для додавання елемента в вершину стека. Ця функція традиційно називається push. Однак ця функція нас особливо не цікавить, оскільки вона дуже просто реалізується:
 
 
let push stk el = el :: stk

 
Досить проста функція, яка має тип 'a list — & gt; 'A — & gt; 'A list , однак не всі подальші функції дозволять поводитися з собою таким простим способом.
 
Куди цікавіше справа йде з виштовхуванням вершини з стека, особливо, якщо ми обмежуємо себе чистими функціями. Як же нам справитися з цим завданням?
 
 
Для цього достатньо згадати, що при визначенні функції pop завжди було два підходи: або виштовхувався об'єкт з вершини стека і одночасно віддалявся з нього, або спершу викликався метод для отримання значення вершини, а потім метод для видалення вершини.
 
Перший підхід не може бути виконаний у функціональному стилі, оскільки це явний приклад функції з побічним ефектом: значення стека повертається як результат функції, і його видалення є побічним ефектом.
Більш того, застосовуючи перший підхід, ми позбавляємося і детермінованості функції: застосування її до одного і того ж екземпляру стека дасть нам різний результат.
 
Так що зупинимося на другому підході. Для цього напишемо дві функції: head, яка буде повертати значення в вершині стека, і pop, яке повертатиме список, позбавлений вершини.
 
Будемо розбиратися з першою. Що нам необхідно повернути? Всього можливо два варіанти: стек порожній або стек не порожній. Якщо стек не порожній, то все ясно: виводимо елемент з вершини. А якщо стек порожній? Адже замість умовних операторів в F # використовується зіставлення шаблонів. У нас стоїть обмеження, що при застосуванні різних шаблонів повинні повертатися дані однакового типу. На допомогу приходять т. Н. опціональні типи , які приймають значення Some (x) або None .
 
Тепер ми можемо написати функцію:
 
let head stk =
 match stk with
 |[] -> None
 |hd :: _ -> Some(hd)

 
Якщо ми подивимося на тип функції head, ми побачимо, що вона має тип 'a list — & gt; 'A option , т. Е. Приймає список як параметр і повертає значення опционального типу.
Функція працює таким чином: прийнявши список stk, вона дивиться на його значення. Якщо він порожній, т. Е. Stk = [], то вона повертає None, що соответсвует того, що вершини у цього списку немає, якщо не порожній, то відділяє перший елемент списку від інших і повертає його у вигляді опционального типу. Знак підкреслення в зіставленні шаблонів означає, що функції неважливо, що повинно знаходитися в цьому місці.
При цьому наша функція є чистою: присутній детермінованість, відсутні побічні ефекти.
 
Дивлячись на цю функцію, тепер ми легко напишемо і функцію pop, яка буде в деякому роді симетрична, однак не потребуватиме в опціонально типі, оскільки роль None виконуватиме порожній список:
 
 
let pop stk =
 match stk with
 |[] -> []
 |_:: tl -> tl

 
Ця функція має тип: 'a list — & gt; 'A list
 
Таким чином, наступний код дає нам всі функції для роботи зі стеком.
 
let push stk el = el :: stk

let head stk =
 match stk with
 |[] -> None
 |hd :: _ -> Some(hd)

let pop stk =
 match stk with
 |[] -> []
 |_ :: tl -> tl

 
 

Черга

Черга відрізняється від стека тим, що додавання нового елемента відбувається в кінець списку, а витяг відбувається з початку черги. Реалізуємо функції add (додавання елемента в чергу), head (хто зараз стоїть в черзі) і delque (видалення елменти з черги). І якщо функції head і delque не викликають сумнівів, то спроба написати let head = que :: el приведе до помилки компіляції, оскільки оператор :: має тип 'a — & gt; 'A list — & gt; 'A list , т. Е. Лівий операнд не може бути списком.
 
Проблема знову вирішується з використанням зіставлення шаблонів, однак тепер у нас в хід вводяться рекурсивні функції для того, щоб дістатися до кінця. Якщо чергу порожня, то їй все одно, додавати з кінця або з початку, оскільки їх немає, так що додамо в початок, який одночасно буде кінцем. Якщо ж список не порожній, то розіб'ємо його на перший елемент і всі інші, і застосуємо рекурсивно нашу функцію до решти елементам списку.
 
let rec add que el = 
 match que with
 |[] -> el :: []
 |hd :: tl -> hd :: (add tl el) 

 
Таким чином, повний набір функцій для черги має вигляд:
 
let rec add que el = 
 match que with
 |[] -> el :: []
 |hd :: tl -> hd :: (add tl el) 

let  head que =
 match que with
 |[] -> None
 |hd :: _ -> Some(hd)

let delque que =
 match que with
 |[] -> []
 |_ :: tl -> tl

 
 

грудня

Найбільш цікава структура даних — це дек, або двунаправленная чергу, т. Е. Додавання і видалення елементів може відбуватися як з початку, так і з кінця. За аналогією з функціями head і pop для стека введемо функції tail і delend для дека. Тут реалізація вже буде цікавіше. Нам потрібен останній елемент, однак у функціональному програмуванні немає циклів. Як нам бути? Знову на допомогу приходить рекурсія, проте рано радіти.
Якщо ми напишемо зовсім по аналогії:
 
 
let rec tail deq =
 match deq with
 |[] -> None
 |_ :: tl -> tail tl

 
то ми успішно отримаємо None для будь-якого аргументу . Це пов'язано з тим, що будь-який список в F # представимо у вигляді a = a :: [] , т. Е. Якщо ми послідовно будемо розмотувати клубок списку, то в кінці кінців у нас нічого не залишиться.
Ця проблема вирішується додаванням всього лише одного умови, якщо згадати, що оператор :: має тип 'a — & gt; 'A list — & gt; 'A list , т. Е. Операнд, що стоїть ліворуч від ::, повинен мати тип елемента списку, а не бути самим списком, тому змінимо код наступним чином:
 
let rec tail deq =
 match deq with
 |[] -> None
 |hd :: [] -> Some(hd)
 |_ :: tl -> tail tl

 
Змінена функція тепер працюватиме правильно, оскільки рекурсія закінчиться на останньому елементі дека і благополучно поверне його.
 
З цим розібралися, а що нам робити з функцією delend? Нам треба замінити останній елемент списку, але як це зробити? Давайте вспонить, що оператор :: повертає список і є асоціативним праворуч, що дозволяє розглянути наступний код:
 
 
let rec delend deq =
 match deq with
 |[] -> []
 |hd1 :: hd2 :: [] -> hd1 :: []
 |hd :: tl -> hd :: (delend tl)

 
Ось він, наш шуканий код. Завдяки оператору :: в правій частині ми не втратимо початок списку, а рекурсія закінчиться на передостанньому елементі списку, створивши новий список без колишнього останнього елемента.
 
Таким чином, для дека ми отримуємо наступний набір функцій:
 
let addbegin deq el = el :: deq

let rec addend deq el = 
 match deq with
 |[] -> el :: []
 |hd :: tl -> hd :: (add tl el) 

let  head deq =
 match deq with
 |[] -> None
 |hd :: _ -> Some(hd)

let delbegin que =
 match que with
 |[] -> []
 |_ :: tl -> tl

let rec tail deq =
 match deq with
 |[] -> None
 |hd :: [] -> Some(hd)
 |_ :: tl -> tail tl

let rec delend deq =
 match deq with
 |[] -> []
 |hd1 :: hd2 :: [] -> hd1 :: []
 |hd :: tl -> hd :: (delend tl)

 
Дякуємо за увагу! Будь код, написаний в даній статті, може бути перевірений в будь-якому середовищі, що допускає програмування під F #
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.