1 Тема від _-_MAIBA_-_

  • _-_MAIBA_-_
  • Користувач
  • Поза форумом
  • Звідки: Львів
  • Дата реєстрації: 25.07.2012
  • Повідомлень: 24
    • Репутація: 5

Тема: Реалізація графів у функціональному програмуванні

Всім привіт! Давненько я вже не звертався за допомогою на цей форум :) Отже, відразу постановка проблеми: мені потрібно здійснити порівняння імперативної та функціональної реалізації Алгоритму Едмонда для знаходження "каркасу" мінімальної вартості для орієнтованого графа http://en.wikipedia.org/wiki/Edmonds%27_algorithm; імперативну мені дозволено взяти з інтернету, так як в університеті ми вивчали тільки функціональну мову, а ось якраз з нею(функціональною) і починаються проблеми: зрозуміло, що моя власна реалізація повинна бути як найефективнішою для вдалого порівняння, тобто потрібно "вгадати" як з описом класів, так і з підбором та реалізацією необхідних методів, в мене є декілька ідей (всім відомих) щодо представлення графів(ця бібліотека має бути написана мною власноруч), але вибрати найкращий саме для цього алгоритму важкувато, так як є відчутна нестача досвіду. Готових реалізацій не хочу, але кільком хорошим ідеям чи натякам був би радий!

2 Відповідь від yooll

  • yooll
  • Replace Group
  • Поза форумом
  • Звідки: Україна
  • Дата реєстрації: 17.07.2012
  • Повідомлень: 164
    • Репутація: 106

Re: Реалізація графів у функціональному програмуванні

Класи, методи, ... - ви точно функціональну мову програмування вивчали?

3 Відповідь від _-_MAIBA_-_

  • _-_MAIBA_-_
  • Користувач
  • Поза форумом
  • Звідки: Львів
  • Дата реєстрації: 25.07.2012
  • Повідомлень: 24
    • Репутація: 5

Re: Реалізація графів у функціональному програмуванні

yooll написав:

Класи, методи, ... - ви точно функціональну мову програмування вивчали?

Звичайно, що функціональну,називається Scala. Не до кінця розумію, що Ви маєте на увазі, але ж функціональна парадигма не заперечує існування класів, тим більше, що іншого способу описати структуру я не знаю. Поділіться, будь ласка, якщо це можна зробити іншим способом!

4 Відповідь від yooll

  • yooll
  • Replace Group
  • Поза форумом
  • Звідки: Україна
  • Дата реєстрації: 17.07.2012
  • Повідомлень: 164
    • Репутація: 106

Re: Реалізація графів у функціональному програмуванні

Scala - це поєднання функціональної та об'єктно-орієнтованої парадигм. Класи, методи - це те, що відноситься саме до ООП.
Функціональне програмування - це функції, виклик функцій, рекурсія і т.п.
Якщо активно використовувати класи, об'єкти, то може вийти порівняння імперативної і об'єктно-орієнтованої методологій. А завдання, я так зрозумів, звучить по іншому.

Подякували: _-_MAIBA_-_1

5 Відповідь від _-_MAIBA_-_

  • _-_MAIBA_-_
  • Користувач
  • Поза форумом
  • Звідки: Львів
  • Дата реєстрації: 25.07.2012
  • Повідомлень: 24
    • Репутація: 5

Re: Реалізація графів у функціональному програмуванні

yooll написав:

Scala - це поєднання функціональної та об'єктно-орієнтованої парадигм. Класи, методи - це те, що відноситься саме до ООП.
Функціональне програмування - це функції, виклик функцій, рекурсія і т.п.
Якщо активно використовувати класи, об'єкти, то може вийти порівняння імперативної і об'єктно-орієнтованої методологій. А завдання, я так зрозумів, звучить по іншому.

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

6 Відповідь від yooll

  • yooll
  • Replace Group
  • Поза форумом
  • Звідки: Україна
  • Дата реєстрації: 17.07.2012
  • Повідомлень: 164
    • Репутація: 106

Re: Реалізація графів у функціональному програмуванні

Граф краще задавати списком суміжних вершин (список - одне із базових понять ФП). А сам алгоритм записати у вигляді функції чи функцій.
Для прикладу можна погуглити задачі з графами на Haskell чи Lisp, якщо приклади на Scala знайти важко.

7 Відповідь від _-_MAIBA_-_

  • _-_MAIBA_-_
  • Користувач
  • Поза форумом
  • Звідки: Львів
  • Дата реєстрації: 25.07.2012
  • Повідомлень: 24
    • Репутація: 5

Re: Реалізація графів у функціональному програмуванні

yooll написав:

Граф краще задавати списком суміжних вершин (список - одне із базових понять ФП). А сам алгоритм записати у вигляді функції чи функцій.
Для прикладу можна погуглити задачі з графами на Haskell чи Lisp, якщо приклади на Scala знайти важко.

Дякую за допомогу, я ще просто був невпевнений, чи краще подавати граф списком суміжних вершин, чи рекурсивно(таким чином, щоб кожна вершина "дивилася" на ті, з якими суміжна), але в другому варіанті напевно ставався би баг, коли граф би не був зв'язним!

8 Відповідь від yooll

  • yooll
  • Replace Group
  • Поза форумом
  • Звідки: Україна
  • Дата реєстрації: 17.07.2012
  • Повідомлень: 164
    • Репутація: 106

Re: Реалізація графів у функціональному програмуванні

Що значить "дивилася"? Це через об'єкти?

9 Відповідь від _-_MAIBA_-_

  • _-_MAIBA_-_
  • Користувач
  • Поза форумом
  • Звідки: Львів
  • Дата реєстрації: 25.07.2012
  • Повідомлень: 24
    • Репутація: 5

Re: Реалізація графів у функціональному програмуванні

yooll написав:

Що значить "дивилася"? Це через об'єкти?

Ну це щось, як принцип конс-комірок, або ж списків, десь так:

class Top(name: String, neighbours: List[(Top, Int)])
// neighbours - це пари: суміжна вершина і відстань до неї(не забуваємо, що граф орієнтований)

class Graph(tops: List[Top])

10 Відповідь від yooll

  • yooll
  • Replace Group
  • Поза форумом
  • Звідки: Україна
  • Дата реєстрації: 17.07.2012
  • Повідомлень: 164
    • Репутація: 106

Re: Реалізація графів у функціональному програмуванні

Можна і так, але це більше по об'єктно-орієнтованому))