我们可以读一个列表,因为它在Haskell中被反转了吗？

Question

在Haskell中,当我们将一个列表传递给一个函数时,我们可以逐个读取它的元素,如下例所示:

check_acceptance :: Automaton -> Int -> [Char] -> Bool
check_acceptance a i (cs:c) = get_next_state c new_state (transitions a) where new_state = get_next_state cs i (transitions a)  

是否有可能通过执行以下操作来读取它(但实际上是避免反转它):

check_acceptance a i (c:cs) = ...

非常感谢您的帮助!

Answer 1

使用列表时,不:从列表末尾读取有效地需要反转列表或类似的东西.但是,并非所有数据结构都如此挑剔.Data.Sequence提供了一种类型,就像列表一样,在前面提供O(1)元素插入(尽管这个O(1)是分摊的O(1),这意味着任何特定的插入都可以是任意昂贵的,但是在很多插入中的平均值非常大可预测的性能),但不像列表也提供(摊销)O(1)在后面查看和删除.