哈斯克尔：FIFO队列算法复杂度 [英] Haskell: FIFO queue algorithm complexity

问题描述

这是我尝试在FIFO队列：

This is my attempt at a FIFO queue:

type Queue a = [a] -> [a]

empty :: Queue a
empty = id

remove :: Int -> Queue a -> ([a], Queue a)
remove n queue = (take n (queue []), (\x -> drop n (queue x)));

add :: [a] -> Queue a -> Queue a
add elems queue = (\x -> queue (elems ++ x))

空创建一个空队列，删除采用第一个 N 队列中的元素，并返回队列中的其余部分的元组，而添加的第二个元素添加列表 elems 到队列中。

empty creates an empty queue, remove takes the first n elements of the queue and returns the rest of the queue as the second element of the tuple, and add adds the list elems to the queue.

这会不会添加/删除1元素 O（1）时间和n个元素在 O（N）时间？

Will this add/remove 1 element in O(1) time and n elements in O(n) time?

推荐答案

今天我向您有效地实施达差异表 。 （参见： DLIST ）

What you have implemented effectively amounts to difference lists. (See: dlist.)

差异表允许廉价的追加，但不幸的是你的去除需要线性时间。它如果我们重写code稍微变得更加清晰：

Difference lists allow for cheap appends, but unfortunately your removal will take linear time. It becomes more clear if we rewrite your code slightly:

type Queue a = [a] -> [a]

empty :: Queue a
empty = id

toList :: Queue a -> [a]
toList q = q []

fromList :: [a] -> Queue a
fromList = (++)

remove :: Int -> Queue a -> ([a], Queue a)
remove n q = (xs, fromList ys)
  where
    (xs, ys) = splitAt n (toList q)

add :: [a] -> Queue a -> Queue a
add xs q = (++ xs) . q

请注意，我已经做了转换，并从列表中多一点明确的比它在你的code。你清楚地看到你的去除code中的核心之间的了ToList 被包围曝光和 fromlist里。

Note that I have made the conversion to and from lists a bit more explicit than it was in your code. You clearly see that the core of your removal code gets bracketed between toList and fromList.

这篇关于哈斯克尔：FIFO队列算法复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！