Композиция функций Haskell с использованием foldl

Я определил в haskell следующую функцию:

step :: [Int] -> [Char] -> [Int]
step stack str
    | str == "*" =  remaining ++ [x*y] 
    | str == "+" =  remaining ++ [x+y]
    | str == "-" =  remaining ++ [x-y]
    | str == "/" =  remaining ++ [x `div` y]
    | otherwise = stack ++ [read str :: Int] 
    where x = (last . init) stack
          y = (last stack)
          remaining = (init . init) stack

Эта функция принимает целочисленный массив [10, 4, 3] и строковый оператор *, применяет оператор к последним двум элементам в массиве и возвращает следующий массив [10, 7].

Это часть промежуточной функции, конечный результат - функция оценщика с обратной полировкой.

Как я могу использовать step функцию, которую я определил, и foldl для выполнения следующих действий:

Возьмите строку примера: "10 4 3 + 2 * -".

Добавляйте каждый элемент в строку, пока не встретится первый оператор:

10, 4, 3 Затем примените оператор к двум элементам на вершине стека и поместите результат в стек:

10, 7.

Продолжайте до тех пор, пока не будет оценен окончательный ответ (-4)

Ответ:

Для полноты картины я пришел к этой функции с помощью @talex.

rpn :: String -> Int
rpn input = head result
    where arr = words input
          result = foldl step [] arr

fold haskell foldleft
person CertainlyNotAdrian    schedule 03.01.2019    source источник
comment
Какая у вас очередь?   -  person n. 1.8e9-where's-my-share m.    schedule 03.01.2019
comment
@ n.m. Я уточнил вопрос   -  person CertainlyNotAdrian    schedule 03.01.2019
comment
Независимо от чего вы используете список в обратном порядке. Естественный способ реализовать стек - разместить его вершину в начале списка, а не в конце.   -  person n. 1.8e9-where's-my-share m.    schedule 03.01.2019
comment
@ n.m. мне кажется более естественным реализовать стек, используя возрастающие индексы, а не постоянно добавлять в начало   -  person CertainlyNotAdrian    schedule 03.01.2019
comment
@ n.m. будет ли способ, которым я его реализовал, несовместим с использованием foldl?   -  person CertainlyNotAdrian    schedule 03.01.2019
comment
Fold принимает функцию, которая работает с двумя вещами, и превращает ее в функцию, которая работает со списком вещей. Итак, если вам нужна функция, которая работает со списком оцепенений, вы начинаете с функции, которая работает с двумя числами.   -  person n. 1.8e9-where's-my-share m.    schedule 03.01.2019
comment
@ n.m. это тоже было мое понимание, но задача настаивает на том, что я использую пошаговую функцию в форме, описанной выше.   -  person CertainlyNotAdrian    schedule 03.01.2019
comment
Ваше чувство искажено отсутствием опыта.   -  person n. 1.8e9-where's-my-share m.    schedule 03.01.2019
comment
Вы пытаетесь реализовать постфиксную нотацию, таким образом вопрос становится намного проще. Также ваша step функция по сути foldr   -  person Denis Babochenko    schedule 03.01.2019
comment
Извините, вы, конечно, можете использовать свертку, вы сворачиваете не список чисел, а строки списка RPN. Извините за путаницу. Дело в стеке по-прежнему остается. Вы делаете это задом наперед.   -  person n. 1.8e9-where's-my-share m.    schedule 03.01.2019
comment
Операции стека сопоставляют 1: 1 операции со списком примитивов. empty = []; top = head; push = (:); pop = tail. Все это O (1). last, init и (++) не являются примитивными операциями, все они O (N).   -  person n. 1.8e9-where's-my-share m.    schedule 03.01.2019
comment
Обращение списка также позволяет использовать сопоставление с образцом для определения x, y и remaining без необходимости использования предложения where: step (x:y:remaining) "*" = x*y : remaining и т. Д.   -  person chepner    schedule 04.01.2019

Ответы (1)


arrow_upward
1
arrow_downward 

foldl step [] ["10",  "4", "3", "+", "2", "*", "-"]

[] вот начальный стек.

Если вы переписываете свой шаг следующим образом, он будет работать быстрее:

step :: [Int] -> [Char] -> [Int]
step stack str
        | str == "*" =  (x*y):remaining 
        | str == "+" =  (x+y):remaining
        | str == "-" =  (x-y):remaining
        | str == "/" =  (x `div` y):remaining
        | otherwise = (read str :: Int):stack
        where x = head $ tail stack
              y = head stack
              remaining = tail $ tail stack
person talex    schedule 03.01.2019
comment
last равно O(n), но head O(1) то же самое для _5 _ / _ 6_ - person talex; 03.01.2019
comment
Также init требуется память для новой копии списка, а tail - просто указатель возврата на неизменяемую структуру. - person talex; 03.01.2019