An Investigation of the Laws of Traversals
An Investigation of the Laws of Traversals
复制标题
遍历定律的研究
DOI：
10.4204/eptcs.76.5
复制
发表时间：
2012
影响因子：
4.6
通讯作者：
Ondrej Rypacek
中科院分区：
文献类型：
--
作者：
Mauro Jaskelioff;Ondrej Rypacek
数据结构的遍历在编程中无处不在。因此，重要的是能够理解那些可遍历的结构并理解它们的代数性质。可遍历函子被麦克布赖德和帕特森描述为那些在任意应用函子上具有分配律的函子;然而，完全捕捉遍历背后的直觉的定律缺失了。本文试图通过提出刻画遍历的规律来弥补这种情况，这些规律捕捉了遍历背后的直觉。为了支持我们的主张，我们证明了有限容器在我们的意义上是可遍历的，并认为可遍历结构中的元素只访问一次。
Traversals of data structures are ubiquitous in programming. Consequently, it is important to be able to characterise those structures that are traversable and understand their algebraic properties. Traversable functors have been characterised by McBride and Paterson as those equipped with a distributive law over arbitrary applicative functors; however, laws that fully capture the intuition behind traversals are missing. This article is an attempt to remedy this situation by proposing laws for characterising traversals that capture the intuition behind them. To support our claims, we prove that finitary containers are traversable in our sense and argue that elements in a traversable structure are visited exactly once.