1

Тема: Декомпозиція

Під час вивчення rust-а стикнувся із психологічною проблемою.
Ще в школі я добре засвоїв принцип алгоритмічної декомпозиції: складну задачу розкладаємо на ряд простих, розв'язуємо кожну з них - і задачу вирішено. Найпростіший варіант, для задач шкільного рівня - просто записуємо умову в код і переписуємо її, доки воно не запрацює. Додати процедури? Відстежуємо в тексті дієслова і додаємо відповідні процедури/функції. Об'єктна декомпозиція? Та те саме, тільки для іменників. Не все можна зробити оптимально, але в цілому виходить непогано.
А тепер - те, що у мене не виходить. rust - мова з потужною функціональною парадигмою, і там найефективніші конструкції виглядають як довгі ланцюжки методів, на кшталт

    statistics.iter()
              .map( |hashmap| hashmap.iter()
                                     .min_by_key(|tuple|tuple.1)
                                     .map(|tuple|*tuple.0)
                                     .unwrap() )
              .collect()

Тут маємо зовнішній ланцюжок statistics->iter->map->collect (якщо записувати "класичними" функціями, то collect (map(iter(statistics),lambda))).
і в другому параметрі map - лямбда-вираз з ланцюжком hashmap->iter->min_by_key->map->unwrap. І так, там ще дві лямбди всередині.
В цілому ж ця конструкція знаходить в масиві словників ключі із мінімальними значеннями в кожному словнику. Приблизно так:

(масив)statistics: з_кожним:
              перетворити( словник: з_кожним:
                                              знайти мінімум (значення),
                                              взяти відповідний ключ,
                                              обробити можливу помилку ),
              зібрати докупи

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

Подякували: 221VOLT, Betterthanyou2

2

Re: Декомпозиція

koala написав:

чи з часом моє сприйняття зміниться?

Людина до всього звикає :)

Щодо функціональщини, то треба сісти за підручник, помудохатись трохи з Haskell та Elixir теж не завадить. Ба, навіть у Ruby є подібні ланцюжки функцій.
На рахунок методики - чесно, не знаю, але щось має бути. Головне, пам'ятати правило ланцюжків методів:
кожен метод із ланцюжка змінює стан об'єкта, на якому він виконується, тобто повертає змінений об'єкт як результат виконання і передається на вхід наступному методу з ланцюжка.
Ну і практика, практика і ще раз практика.

Подякували: 221VOLT1

3

Re: Декомпозиція

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

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

чи існує методика декомпозиції задачі в функціональний код?

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

Подякували: 0x9111A, koala, 221VOLT, leofun014

4

Re: Декомпозиція

Якщо я правильно розумію пробему, то от вам тренажер. Можливо допоможе похитнути "функціональний" бар’єр

5 Востаннє редагувалося 221VOLT (11.12.2016 23:57:12)

Re: Декомпозиція

Master_Sergius написав:
koala написав:

чи з часом моє сприйняття зміниться?

Людина до всього звикає :)

Щодо функціональщини, то треба сісти за підручник, помудохатись трохи з Haskell та Elixir теж не завадить. Ба, навіть у Ruby є подібні ланцюжки функцій.
На рахунок методики - чесно, не знаю, але щось має бути. Головне, пам'ятати правило ланцюжків методів:
кожен метод із ланцюжка змінює стан об'єкта, на якому він виконується, тобто повертає змінений об'єкт як результат виконання і передається на вхід наступному методу з ланцюжка.
Ну і практика, практика і ще раз практика.

+1 до вашої промови)
зазначу лише, що якщо просто в elixir прийти - моментами можна обламатися, адже там можуть бути необхідними підпірки з erlang (без ерланга в еліксирі все ж нікуди)) )

Подякували: koala, Betterthanyou2

6 Востаннє редагувалося P.Y. (12.12.2016 01:24:47)

Re: Декомпозиція

ФП буває різне. Часто навіть у межах однієї мови існує декілька ідеологічно різних парадигм. Наприклад, хвостова рекурсія є близьким аналогом циклу, і багато з того, що стосується циклів у процедурних мовах, можна застосувати й до хвостової рекурсії. Перейшовши від Scheme до Clojure, якийсь час я продовжував писати алгоритми з хвостовою рекурсією, але згодом усвідомив переваги лінивих послідовностей (аналог ітераторів), правильним підходом для роботи з якими є побудова ланцюжка перетворень з використанням map, filter та інших лінивих функцій. Я б порівняв таку побудову з викликом кількох програм через пайп  — напр., прочитати файл, провести в ньому серію замін, вивести результат у три стовпчики — це все виглядатиме приблизно як

cat file.txt|sed s/qwerty/asdf/g|pr -3t

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

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

Подякували: 221VOLT, Betterthanyou2

7 Востаннє редагувалося P.Y. (12.12.2016 02:02:13)

Re: Декомпозиція

Наприклад, табличку множення у Clojure я б робив приблизно так:
1.

;; Вивести a*b=c для всіх a,b від 1 до 10....

2.

(->> ;; послідовність чисел від 1 до 10...
;; перетворити на список усіх комбінацій пар вхідних чисел....
;; Вивести a*b=c для кожної комбінації a,b....
)

3.

(->> (range 1 11);; послідовність чисел від 1 до 10
;; перетворити на список усіх пар чисел:
((fn[ns]
  (->> ns
    ;; перетворити кожен елемент на список пар його з кожним елементом ns...
    ;; перетворити список списків пар на список пар....
  )
))
;; Вивести a*b=c для кожної комбінації a,b:
(map (fn[[a b]](str a "*" b "=" (* a b))))
(map println)
dorun
)

4.

(->> (range 1 11);; послідовність чисел від 1 до 10
;; перетворити на список усіх пар чисел:
((fn[ns]
  (->> ns
    ;; перетворити кожен елемент вхідного списку на список пар його з кожним елементом ns:
    (map (fn[n] (map #(list n %1) ns)))
    (apply concat);; перетворити список списків пар на список пар
  )
))
;; Вивести a*b=c для кожної комбінації a,b:
(map (fn[[a b]](str a "*" b "=" (* a b))))
(map println)
dorun
)
Подякували: koala, 221VOLT, Betterthanyou3

8 Востаннє редагувалося iovchynnikov (12.12.2016 17:52:58)

Re: Декомпозиція

Перейти досить легко, достатньо припинити думати про алгоритми і почати бачити лише дані та трансформації даних.

Приклад: порахувати кількість слів у реченні.
Думаємо алгоритмічно: int i, foreach word i++
Думаємо лише про трансформації даних:
1 трансформація: text.split(' ')
2 трансформація: записуємо слова у кортежі зі значенням 1 => (word, 1)
3 трансформація: стискаємо кортежі, сумуємо 1ці => reduce((tuple1,tuple2)-> tuple1._2 + tuple2._2). Отримуємо кількість слів у тексті.
Приклад, звичайно, досить "сокирний" :) але показує як перейти від створення додаткових змінних та петель до суто мислення "трансформаціями".

Кожна трансформація це і є декомпозиція. Тільки не алгоритму, а перетворення даних з постаті А до Б.

Мозок перебудовується через 10-15 застосувань.

Подякували: koala, 221VOLT, Betterthanyou, leofun014

9

Re: Декомпозиція

iovchynnikov написав:

3 трансформація: стискаємо кортежі, сумуємо 1ці => reduce((tuple1,tuple2)-> tuple1._2 + tuple2._2).

А я наївно думав, що редьюс має повертати тип елементу колекції. Щоб повернений результат без проблем передався в наступний виклик. Поясніть, якщо не важко, як воно насправді є?

Подякували: 221VOLT1

10

Re: Декомпозиція

reduce (він же fold чи accumulate) - це аналог змінної-акумулятора, в яку на кожній ітерації записується результат операції із черговими даними ітератора, а в результаті маємо суму (накопичений масив чи ще щось).
В rust стандартний приклад:

fold(0, |acc, &x| acc + x);

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

reduce((sum,tuple)-> sum + tuple._2)
Подякували: 0x9111A, 221VOLT, iovchynnikov, leofun014

11 Востаннє редагувалося koala (12.12.2016 23:18:03)

Re: Декомпозиція

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

І ще - чи існує якесь функціональне рішення, коли треба ітератори розвести по парних/непарних у дві окремі гілки? Бо наразі у мене виходить щось некрасиве, із додатковою булевою змінною на початку, map-ом з if-ом всередині і all(|_|true) в кінці, щоб змусити ітератор пройти всю структуру. А enumerate створює додаткові map-и, щоб потім позбутися номерів, та й перевірка залишку (навіть у формі &1) не дуже красиво виглядає.

P.S. Забив у цій задачі на функціональщину, розв'язалася у два подвійних цикли :)

Подякували: 221VOLT, leofun012

12

Re: Декомпозиція

koala написав:

P.S. Забив у цій задачі на функціональщину, розв'язалася у два подвійних цикли :)

Мабуть воно іще й по швидкості разів в десять обганяє функціональщину :)

Подякували: 221VOLT, leofun012

13

Re: Декомпозиція

Torbins написав:
koala написав:

P.S. Забив у цій задачі на функціональщину, розв'язалася у два подвійних цикли :)

Мабуть воно іще й по швидкості разів в десять обганяє функціональщину :)

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

Подякували: 221VOLT1

14

Re: Декомпозиція

koala написав:

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

Вангую непідходящі типи, але екстрасенс з мене так собі.

Подякували: 221VOLT1

15

Re: Декомпозиція

quez написав:
koala написав:

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

Вангую непідходящі типи, але екстрасенс з мене так собі.

Та ситуація в rust, як я розумію, така (Iterator - це такий трейт, певний аналог інтерфейсу)

a         //Vec<X>
.iter()   //Iter<X> as Iterator<X>
.map(...)  // Map<Iter<X>,Y> as Iterator<Y>
.filter(...) // Filter<Map<Iter<X>>,Y> as Iterator<Y>> as Iterator<Y>
.collect::<Z>()  //Z

І це я не враховую різні обгортки, в які можна це збирати. Це все сміття збирає компілятор (якому можна навіть не вказувати Z) і викидає при оптимізації. Але якщо я хочу взяти шматок з середини ланцюжка - починаються проблеми. Принаймні, поки що.

Подякували: 221VOLT1