1 Востаннє редагувалося 221VOLT (20.05.2020 19:00:14)

Тема: Haskell -- калькулятор зворотнього польського запису [Стаття]

спочатку трішки теорії:

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

це означає, що спочатку ми записуємо числа,
а дію(знак операції) над цими числами(операндами) записуємо після чисел(операндів)
наприклад:

2 3 +

звичну нам зі школи інфіксну нотацію ми записуємо так:

2 + 3

тобто, дію(знак операції) над числами(операндами) ми записуємо поміж числами(операндами, аргументами)

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

2 + 2 * 2

дорівнює

2 + (2 * 2)

та не дорівнює

(2 + 2) * 2

у випадку з постфіксною нотацією порядок знаків операцій
однозначно вказує на порядок виконання операцій,
відповідно, використовувати дужки не потрібно:

2 2 2 + *

тут ми спочатку додаємо, далі перемножуємо

а тут ми спочатку перемножуємо, і далі додаємо

2 2 2 * +

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


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



на цьому теоретичну частину завершуємо,
переходимо до коду :)

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

calc1 :: (Num a, Read a) => String -> a
calc1 s = head $ foldl calc1h [] $ words s
  where
    calc1h (x:y:ys) "*" = (y * x):ys
    calc1h (x:y:ys) "+" = (y + x):ys
    calc1h (x:y:ys) "-" = (y - x):ys
    calc1h xs s2 = (read s2):xs

використання

ghci> calc1 "10 4 3 + 2 * -"
-4

чудово, наш калькулятор працює!
тільки відсутня операція розділити...

додаємо:

calc1 :: (Num a, Fractional a, Read a) => String -> a
calc1 s = head $ foldl calc1h [] $ words s
  where
    calc1h (x:y:ys) "*" = (y * x):ys
    calc1h (x:y:ys) "+" = (y + x):ys
    calc1h (x:y:ys) "-" = (y - x):ys
    calc1h (x:y:ys) "/" = (y / x):ys
    calc1h xs s2 = (read s2):xs

перевіримо роботу

ghci> calc1 "10 4 3 + 2 * -"
-4.0

ghci> calc1 "12 2 3 4 * 10 5 / + * +"
40.0

тепер розглянемо зміни,
і взагалі, як це все працює?

розпочнемо з декларації типу функції


String -> a

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


Num a

це клас типів, представниками якого є наступні типи: Double, Float, Int, Integer
тобто, по 2 типи цілих чисел та чисел з плаваючою комою (точкою) --
відповідно, наша функція може повертати число одного з цих типів


Fractional a

це клас типів, представниками якого є типи Double, Float,
цей клас типів потрібен при використанні ділення


Read a

потрібен нам для того, щоб зчитати зі строки "1" як число 1


(Num a, Fractional a, Read a)

повна декларація класів типів для типу a говорить нам та компілятору --
тип a повинен бути числом (цілим чи з плаваючою комою),
над ним може виконуватись операція ділення,
а також потрібна властивість (вміння) зчитати число цього типу(типів) зі строки (чи числа іншого типу)


так, ці всі типи і класи типів для людини, яка знайома лише з динамічною типізацію,
з роботою з php + js, виглядають незвично та страшно ))
та подивіться з іншої сторони -- через деякий час програміст звикає до написання декларації типів функцій,
і бонуси від цього суттєві --
нам не потрібно перевіряти типи даних змінних всередині функцій,
і ми ніколи не отримаємо в рантаймі такі неочікувані помилки, як в динамічно-типізованому js (1 + '1' = 11, не 2)
на місця ймовірних помилок нам вкаже компілятор, і просто не пропустить в рантайм, не скомпілює :)


розглянемо першу строку нашої функції-калькулятора

head $ foldl calc1h [] $ words s

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

head ( foldl calc1h [] (words s) )

продовжимо розбір

words s

розбиває строку по пробілу, тобто

ghci> words "1 2 3"
["1","2","3"]

далі, вираз

foldl calc1h [] s1

де s1 -- це наш список-результ виконання функції words,
означає наступне -- провести ліву згортку foldl (зліва направо),
з акумулятором(значенням ініціалізції) [] у якості першого аргументу функції calc1h,
та значенням з голови списку s1 у якості другого аргументу функції calc1h,
далі згортка записує значення редукції функції calc1h у якості нового акумулятора для наступної редукції згортки,
якщо список пустий -- згортка повертає це значення акумулятора :)
власне, тому цю функцію так і називають --
згортка = згортає список значень в одне значення, за допомогою певної функції, застосованої до кожного значення списку)


простіші приклади застосування згортки foldl

Прихований текст
ghci> foldl (/) 64 [4,2,4]
2.0

ghci> foldl (/) 3 []
3.0

ghci> foldl max 5 [1,2,3,4]
5

ghci> foldl max 5 [1,2,3,4,5,6,7]
7

ghci> foldl (\x y -> 2 * x + y) 4 [1,2,3]
43

а що таке calc1h ?
це наша допоміжна функція (helper),
визначення якої ми написали всередині нашої головної функції,
скориставшись службовим словом-конструкцією where :)

розглянемо перший рядок функції calc1h

calc1h (x:y:ys) "*" = (y * x):ys

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

якщо першим аргументом буде список з мінімум двома значеннями
(наприклад, [1,2] -- у такому разі паттерн матчинг даної клаузи виглядає як
(1:2:[]), тобто x = 1, y = 2, ys = [] ),

а другим аргументом буде строка з одного символу "*",
то ця клауза матчиться, і виконується вираз (y * x):ys

тобто перемножуємо y та x і додаємо результат в голову списку ys


якщо ж клауза не матчиться -- переходимо вниз, до наступної клаузи,
пробуємо матчити її))

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

calc1h xs s2 = (read s2):xs

тут ми зчитуємо строку s2 як число, і додаємо це значення в голову списка xs,
і повертаємо цей список, оскільки в хаскелі, в ФП кожна функція щось повертає


примітка: говорити "функція повертає" в ФП є не зовсім коректно,
правильніше -- відбувається редукція - обчислення,
в результаті якого один вираз (функція з агрументами)
замінюється іншим виразом (результатом обчислення),
тобто відбувається спрощення виразів


ghci> head [1,2,3]
1

оце і все) оце і весь калькулятор зворотнього польського запису,
постфіксної нотації :)

а тепер покажіть аналогічний по функціональності калькулятор,
написаний на динамічно-типізованому js без паттерн матчинга,
подивимось на ту купу рядків і разом посміємось :)

Подякували: 0xDADA11C7, leofun01, /KIT\, koala, P.Y., fed_lviv6

2

Re: Haskell -- калькулятор зворотнього польського запису [Стаття]

Динамічно типізований Python без зіставлення з шаблонами, зате з eval, f-string-ами та зрізами:

def calc1(s):
    stack = []
    for item in s.split():
        if item in "+-*/":
            y,x = stack[-2:]
            stack[-2:]=[eval(f'{y}{item}{x}')]
        else:
            stack.append(item)
    return stack.pop()
Подякували: 0xDADA11C7, /KIT\, leofun01, P.Y., 221VOLT5

3 Востаннє редагувалося 221VOLT (21.05.2020 02:10:02)

Re: Haskell -- калькулятор зворотнього польського запису [Стаття]

погоджусь, Python також буває лаконічним
мені його декілька разів радили)

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

відповідно, ймовірність падіння в рантаймі
програми на пайтоні вища, ніж програми на хаскелі

нехай пайтон грамотніше спроектований, ніж js/php,
над ним довше думали, краще попрацювали і продовжують працювати --
все ж таки динамічна типізація = додавання 5 яблук до 2 кішок = 7 ??чого? :)



а якщо додамо операцій?
в тому числі, з різною кількістю операндів

calc1 :: (Num a, Floating a, Fractional a, Read a) => String -> a
calc1 s = head $ foldl calc1h [] $ words s
  where
    calc1h (x:y:ys) "*" = (y * x):ys
    calc1h (x:y:ys) "+" = (y + x):ys
    calc1h (x:y:ys) "-" = (y - x):ys
    calc1h (x:y:ys) "/" = (y / x):ys
    calc1h (x:y:ys) "^" = (y ** x):ys
    calc1h (x:xs) "ln" = (log x):xs
    calc1h xs "sum" = [sum xs]
    calc1h xs s2 = (read s2):xs
ghci> calc1 "2.7 ln"
0.9932517730102834

ghci> calc1 "10 10 10 10 sum 4 /"
10.0

ghci> calc1 "10 10 10 10 10 sum 4 /"
12.5

ghci> calc1 "10 2 ^"
100.0

ghci> calc1 "43.2425 0.5 ^"
6.575902979819578

як виглядатиме дописана програма на пайтоні?

думаю, при ускладненні функціональності цієї програми
код пайтона розростатиметься набагато швидше
(відсутність декларування типів нівелюється спагетті з if-ів)) )

а якщо в строці у нас помилка?
пайтон перемножуватиме utf8 символ(букву) та число,
хаскель скаже, що не можна зчитати букву як число,
імхо дописати обробку такої помилки на хаскелі простіше

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


о, десь ще бачив цікаву задачу на виправлення пропущених дужок,
здається на erlang рішення писав, треба пошукати і додати сюди )

4

Re: Haskell -- калькулятор зворотнього польського запису [Стаття]

Ой, а може, спробуємо написати функцію, що вміє дужки розкривати і інфіксні оператори виконувати? Ну і різні там sum над списками робити. Ось як це виглядає на Python:

calc2=eval
#демонстрація
print(calc2("(2+2)*2+sum([1,3,5])**.5")

На вашому полі Python грає не дуже добре, але тримається. Пограйте на полі Python.

5

Re: Haskell -- калькулятор зворотнього польського запису [Стаття]

якщо мова чисто про eval
http://hackage.haskell.org/package/plug … skell.html

а про парсання дужок з помилками(пропущеними) я вище вже написав :)

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