обратная польская нотация Haskell

Будучи новичком в haskell, я решил попробовать реализовать мини-функцию обратной полировки:

Принимает list типа int и строковый оператор ('*','+','/','-')

примените оператор к элементу tail и элементу tail-1

вернуть результирующий list с двумя удаленными элементами, участвующими в операции, и результирующий элемент, добавленный к хвосту как таковой:

Where e0 = original element at index 0

r = result of the operation:

result = [e0,e1,e2...r] (elements popped off: eN, eN-1)

Это код, который у меня есть до сих пор:

import Data.List
import System.IO

step :: [Int] -> String -> [Int]
step stack operator
    | (x:y:ys) "*" = (x * y):ys
    | (x:y:ys) "+" = (x + y):ys
    | (x:y:ys) "-" = (x - y):ys
    | (x:y:ys) "/" = (x / y):ys

И это дает мне следующую ошибку компиляции:

• Couldn't match expected type ‘[Char] -> Bool’
                  with actual type ‘[a3]’
    • The function ‘x : y : ys’ is applied to one argument,
      but its type ‘[a3]’ has none
      In the expression: (x : y : ys) "/"
      In a stmt of a pattern guard for
                     an equation for ‘step’:
        (x : y : ys) "/"

Я считаю, что это результат ошибки в моем синтаксисе, любая помощь приветствуется!


functional-programming haskell postfix-notation
person CertainlyNotAdrian    schedule 30.11.2018    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Вы правильно реализовали функцию, но ваш синтаксис немного неверен — вы использовали охранники, когда хотите использовать сопоставление с образцом:

  • Сопоставление с образцом используется, когда вы хотите разбить параметр на более мелкие части или обработать его в нескольких случаях; тогда как
  • Ограничители используются, когда вы хотите выбрать одну ветвь функции на основе логического условия, аналогично выражению if/then/else. (Поэтому условие защиты должно быть допустимым выражением типа Bool.)

В своем коде вы использовали охранники, но вам действительно нужно сопоставление с образцом, например:

step :: [Int] -> String -> [Int]
step (x:y:ys) "*" = (x * y):ys
step (x:y:ys) "+" = (x + y):ys
step (x:y:ys) "-" = (x - y):ys
step (x:y:ys) "/" = (x / y):ys

Однако это все равно выдаст ошибку:

* No instance for (Fractional Int) arising from a use of `/'
* In the first argument of `(:)', namely `(x / y)'
  In the expression: (x / y) : ys
  In an equation for `step': step (x : y : ys) "/" = (x / y) : ys

Эта ошибка достаточно очевидна: вы пытаетесь / преобразовать целое число, но целые числа не равны Fractional, поэтому вы не можете этого сделать. Если вам нужно целочисленное деление, вы можете заменить его на div x y, в противном случае вы можете изменить Int на Float в сигнатуре типа, чтобы разрешить нецелочисленные значения.

Однако даже после этого изменения остается небольшая ошибка: что произойдет, если в вашем списке меньше двух элементов или используется неподдерживаемый оператор? Здесь правильно выполнить сопоставление с шаблоном в конце, используя step _ _ = (something), где _ — это специальный синтаксис, который соответствует чему угодно. (Или вы также можете использовать step stack operator = (something), если вы хотите вернуться к stack и operator для чего-то вроде сообщения об ошибке.

EDIT: В комментариях ниже @chepner предложил другой способ сделать это, используя как сопоставление с образцом, так и защиту:

step :: [Int] -> String -> [Int]
step (x:y:ys) op
    | op == "*" = (x * y):ys
    | op == "+" = (x + y):ys
    -- etc.
    | otherwise = (some error case)

Это еще раз иллюстрирует разницу между ними: сопоставление с образцом используется для разложения первого аргумента на x, y и ys, а охранники используются с логическими условиями (при этом otherwise фактически определено в Prelude как равное True).

person bradrn    schedule 30.11.2018
comment
Также обратите внимание, что вам не обязательно использовать только одно или другое: например, допустимо step (x:y:ys) op | op == "*" = (x*y):ys; | op == "+" = .... - person chepner; 01.12.2018
comment
Хороший вопрос @chepner - могу ли я отредактировать его в своем ответе для полноты картины? - person bradrn; 01.12.2018
comment
@bradrn, пожалуйста :) - person CertainlyNotAdrian; 01.12.2018