Блог

как написать в Haskell очередь с двойным завершением («deque»). Структура данных должна иметь функции emptyDeque, front, back, removeFront, removeBack, addFront, addBack и isEmpty, а затем отображать двустороннюю очередь между -> и <- .

это то же самое, но для очереди:

 module Queues (Queue, emptyQueue, front, remove, add, isEmpty)
   newtype Queue a = Queue [a]
   emptyQueue = Queue []
   front  (Queue (x:xs)) = x
   front (Queue []) = error("No front of empty queue")
   add (Queue xs) x = Queue (xs    [x])
   remove (Queue (x:xs)) = Queue xs
   remove (Queue []) = error("Nothing on queue to remove")
   isEmpty (Queue []) = True
   isEmpty (Queue (x:xs)) = False
   showElems [] = ""
   showElems (x:xs) = " "    (Prelude.show x)    (showElems xs)
   showQueue (Queue a) = "<"    (showElems a)    " >"
   instance (Show a) => Show (Queue a) where show = showQueue
  

Я придумал, правильно ли это?

 module Deques (Deque, emptyDeque, front, back, removeFront, removeBack , addFront, addBack, isEmpty)
newtype Deque a = Deque [a]
emptyQueue = Queue []
reverses (x:xs) = (reverses xs)    [x]
front (Deque (x:xs)) = x
front (Deque []) = error("No front of empty Deque")
back (Deque a) = front(reverse(a))
back (Deque []) = error("No back of empty Deque")
addBack (Deque xs) x = Deque (xs    [x])
addFront (Deque xs) x = Deque ([x]    xs)
removeFront (Deque (x:xs)) = Deque xs
removeFront (Deque []) = error("Nothing on Deque to remove")
removeBack (Deque a) = reverses(removeFront(reverses(a))
                 `
  

Использование списков для реализации Deque не очень эффективно, но это может сработать. Несколько замечаний

Помимо ошибок типа, вы, похоже, пишете приложение-функцию в стиле других языков

 front(reverse(a))
  

В Haskell скобки предназначены просто для группировки. Более простой способ написания этой строки был бы

 front (reverse a)
  

или даже

 front $ reverse a
  

Еще одно замечание: добавление чего-либо в начало списка очень типично в Haskell

 [x]    xs -- The weird way
x : xs -- The canonical way
  

Однако добавление в конец списка — это некрасиво.

 xs    [x] -- No better way for normal lists. This is inefficient
  

У вас довольно хорошее начало, но вам следует попытаться ознакомиться с уникальной парадигмой и стилем Haskell. Первые несколько глав Learn You a Haskell хорошо справляются с этой задачей.

На самом деле вот моя окончательная реализация Deque, которая отлично работает

 module Deques (Deque, emptyDeque, front, back, removeFront, removeBack, addFront, addBack, isEmpty) where

    newtype Deque a = Deque [a]

    backwards (Deque []) = Deque []

    backwards (Deque a) = Deque( reverse a )

    emptyDeque = Deque []

    front (Deque (x:xs)) = x
    front (Deque []) = error("No front of empty Deque")

    back (Deque a) = front( backwards (Deque a))
    back (Deque []) = error("No back of empty Deque")

    addBack (Deque xs) x = Deque (xs    [x])
    addFront (Deque xs) x = Deque (x : xs)

    removeFront (Deque (x:xs)) = Deque xs
    removeFront (Deque []) = error("Nothing on Deque to remove")

    removeBack (Deque a) = backwards( removeFront( backwards (Deque a) ))
    removeBack (Deque []) = error("Nothing on Deque to remove")

    isEmpty (Deque []) = True
    isEmpty (Deque (x:xs)) = False

    showElems [] = ""
    showElems (x:xs) = " "    (Prelude.show x)    (showElems xs)
    showDeque (Deque a) = "<"    (showElems a)    " >"

    instance (Show a) => Show (Deque a) where show = showDeque