2

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

2 回答 2

6

使用列表来实现 Deque 效率不是很高，但它可以工作。几点注意事项

除了类型错误，您似乎正在以其他语言的风格编写函数应用程序

front(reverse(a))

在 Haskell 中，括号只是用于分组。写那行的更 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的前几章在这方面做得很好。

于 2011-04-25T20:04:54.747 回答
1

实际上，我的 Final 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
于 2011-05-04T02:16:24.967 回答