如何在Haskell中编写Deque数据类型

Question

如何在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))
                 `

Answer 1

使用列表来实现Deque效率不高,但它可以工作.几点说明

除了键入错误之外,您似乎正在以其他语言的风格编写函数应用程序

front(reverse(a))

在Haskell中,parens只是用于分组.写这条线的Haskelly方式就越多

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的前几章做得很好.