#haskell #stack
Вопрос:
Я самообучающийся Хаскелл и реализовал стек следующим образом:
pop :: [a] -> [a]
pop [] = error "Cannot pop from an empty list!"
pop xs = init xs
push :: a -> [a] -> [a]
push = (:)
peek :: [a] -> a
peek [] = error "Cannot peek from an empty list!"
peek (x:xs) = last (x:xs)
isEmpty :: [Int] -> Bool
isEmpty [] = True
isEmpty xs = False
test :: [Int] -> Either String [Int]
test = fmap reverse . foldM step []
where step xs x | even x = Right (push x xs)
| odd x = do
var <- Right (pop xs)
if isEmpty var then Left "Successful"
else (if not (isEmpty var) then return xs else Left "Unsuccessful")
Нет никаких проблем с перемещением значения в стек, однако эта реализация не может выскочить из стека, как ожидалось, например:
Input: [0,2,3,1]
Output: Right [0,2]
Expected: Left "Successful"
Я думаю, что проблема кроется в do сегменте test функции, но я изо всех сил пытаюсь заставить ее работать. Заранее спасибо!
Комментарии:
1. Вы толкаете слева, но выглядываете и хлопаете справа. Это не то, как работает стек.
2. Кроме того, обратите внимание, что
doблок на самом деле не такой … делая что-либо вообще, вы просто снова удаляете значение, которое вы только что ввели в конструктор.Right3. Должен ли я изменить
push = (:)push x xs = xs [x]или сделать что-то сtestфункцией , чтобы она также нажимала справа?4. @слева примерно так, как я вижу. То, что я пытался там сделать, состояло в том, чтобы открыть стек, а затем немедленно проверить, пуст ли полученный стек или нет… так что, возможно
do, блок на самом деле так не работает?5. То, что вы описываете, кажется простым
isEmpty $ pop xs.
Ответ №1:
С помощью комментариев test функция теперь работает с использованием следующей реализации:
test :: [Int] -> Either String [Int]
test = fmap reverse . foldM step []
where step xs x | even x = Right (push x xs)
| odd x = if isEmpty (pop xs) then Left "Successful"
else (if not (isEmpty (pop xs)) then return (pop xs) else Left "Unsuccessful")