什么是 DList？

发布于 2024-09-11 17:44:38 字数 166 浏览 6 评论 0原文

我尝试用谷歌搜索这个内容，但我得到的只是一些小名人的故事。鉴于缺乏文档，什么是 D列表？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

夜声 2024-09-18 17:44:38

这是一个差异列表，类似于“差异列表作为函数”

scala> val (l1, l2, l3) = (List(1, 2, 3), List(4, 5, 6), List(7, 8, 9))
l1: List[Int] = List(1, 2, 3)
l2: List[Int] = List(4, 5, 6)
l3: List[Int] = List(7, 8, 9)

高效的前置：

scala> l1 ::: l2 ::: l3
res8: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

低效的附加。这将创建一个中间列表 (l1 ++ l2)，然后 ((l1 ++ l2) ++ l3)

scala> l1 ++ l2 ++ l3  // inefficient
res9: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

DList 存储追加内容，并且只需要创建一个完整列表，有效调用：

scala> List(l1, l2, l3) reduceRight ( _ ::: _) 
res10: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

It's a Difference List, along the lines of "Difference List as functions"

scala> val (l1, l2, l3) = (List(1, 2, 3), List(4, 5, 6), List(7, 8, 9))
l1: List[Int] = List(1, 2, 3)
l2: List[Int] = List(4, 5, 6)
l3: List[Int] = List(7, 8, 9)

Efficient prepending:

scala> l1 ::: l2 ::: l3
res8: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

Inefficient appending. This creates an intermediate list (l1 ++ l2), then ((l1 ++ l2) ++ l3)

scala> l1 ++ l2 ++ l3  // inefficient
res9: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

DList stores up the appends, and only needs to create one complete list, effectively invoking:

scala> List(l1, l2, l3) reduceRight ( _ ::: _) 
res10: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

回复收藏 0 原文

大姐，你呐 2024-09-18 17:44:38

差异列表是一种类似列表的数据结构，支持O(1)追加操作。

追加和其他修改列表的操作是通过修改函数的函数组合来表示的，而不是直接复制列表。

来自 Haskell 的 dlist 库的示例：

-- Lists as functions
newtype DList a = DL { unDL :: [a] -> [a] }

-- The empty list
empty       = DL id

-- The append case: composition, a la Hughes
append xs ys = DL (unDL xs . unDL ys)

-- Converting to a regular list, linear time.
toList      = ($[]) . unDL

该技术至少可以追溯到 Hughes 84，列表的新颖表示及其应用函数“reverse”，R. John Hughes，1984。其中，他建议将列表表示为函数，并附加为函数组合，从而允许反向运行在线性时间内。来自论文：

在此处输入图像描述

在此输入图像描述

Difference lists are a list-like data structure that supports O(1) append operations.

Append, and other operations that modify a list are represented via function composition of the modification functions, rather than directly copying the list.

An example, from Haskell's dlist library:

-- Lists as functions
newtype DList a = DL { unDL :: [a] -> [a] }

-- The empty list
empty       = DL id

-- The append case: composition, a la Hughes
append xs ys = DL (unDL xs . unDL ys)

-- Converting to a regular list, linear time.
toList      = ($[]) . unDL

The technique goes back at least to Hughes 84, A novel representation of lists and its application to the function "reverse", R. John Hughes, 1984., where, he proposes representing lists as functions, and append as function composition, allowing e.g. reverse to run in linear time. From the paper:

enter image description here

回复收藏 0 原文