编程语言与软件工程2017michael.steindorfer.name
高效不可变集合
Efficient Immutable Collections
进阶 · 约 120 分钟读完前置知识：持久化数据结构、哈希 Trie 基础、位运算
导读
这篇博士论文研究如何高效实现不可变（持久化）集合数据结构，核心贡献包括 CHAMP——一种用位图压缩的哈希数组映射字典树，并构建了一系列可配置的高效不可变数据结构。论文引用并扩展了 Chris Okasaki 等人的经典工作。
HN 关注点：函数式编程与高效不可变数据结构的结合，以及这类结构如何在不大量复制的前提下保持操作性能。
后来怎么样
论文提出的 CHAMP 结构被 Scala 标准库采纳，成为 Scala 2.13 中 Vector 和 HashMap 的底层实现，是持久化集合领域被广泛采用的成果。
HN 评论精选
这几条评论里：支持 1 补充 3
补充介绍 CHAMP 的原理并分享自己的玩具实现和笔记
这是 Michael 的很棒的工作，是一系列可配置的数据结构。其中大部分底层是 CHAMP——一种压缩哈希数组映射字典树，本质上是基于插入对象的哈希构建的 trie，并用一种巧妙的位图技术进行压缩。我做了一个玩具实现来理解它的工作原理，附带的笔记可能有帮助：https://github.com/norswap/triemap
norswap查看英文原文
This is really cool work by Michael, a collection of configurable data structures. Underlying most of them is CHAMP - a compressed hash array map trie. Essentially it's a trie over the hash of the objects inserted in the map. It's compressed using a clever technique that involves bitmaps. A made a toy implementation of it to get a sense of how it works. There are some accompanying notes that you might find useful: https://github.com/norswap/triemap
支持高效不可变数据结构是函数式编程真正实用的关键
为什么这类研究重要？因为函数式编程的好处只有配合高效的不可变结构才能充分发挥。比如在 C++ 中可以做最基本意义上的函数式编程，很有趣，但代价很高，因为缺乏支持 FP 惯用法的高效数据结构。也有人尝试把这类结构引入 C++，但都不够成熟。FP 不只是关于函数和表达式，更重要的是让这些函数式操作在不大量复制的情况下保持高效——这正是数据结构研究的迷人之处。
hellofunk查看英文原文
To anyone wondering why stuff like this matters, it's because the benefits of functional programming reach new heights when coupled with efficient immutable structures. In C++, for example, you can do functional programming in the most basic sense of the word, and it's actually pretty fun. But it can be very expensive because you are not working on efficient data structures that support the mangling and idioms that make FP really shine. There have been interesting efforts to bring structures like this to C++ but nothing mature or known widespread. When people talk about FP, it's about a lot more than what you can do with functions and expressions; it's about making sure that these functional manipulations remain very fast without lots of copying, and that's what is so fascinating about data structure research: how it supports new ways to write programs.
补充推荐 Okasaki 的论文和著作作为延伸阅读
如果想深入了解这类数据结构，值得读 Chris Okasaki 的工作（本论文多次引用）。他的博士论文在这里：https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf，其中部分内容每个软件工程师都应该能看懂。他还就同一主题写了一本书。
amenghra查看英文原文
Chris Okasaki's work (cited several times in this thesis) is worth reading if you want to learn more about these kinds of data structures. His thesis is here: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf and parts of it should be easy to grok by every software engineer. Chris also wrote a book on the same topic.
补充指出论文中与 Clojure 相关的性能数据（3.5）
Clojure 开发者：你们要找的数字是 3.5，乍一看这个结果相当不错。
devrandomguy查看英文原文
Clojure devs: 3.5 is the figure you are looking for, and it does look very good, at first glance.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2017Hacker News 讨论帖266 分 · 38 评
同领域还值得读
Google 的软件工程（2017）
Software Engineering at Google (2017)
介绍了 Google 的软件工程实践，包括其单一代码库（monorepo）、几乎全部开发在主干进行而非分支、代码审查、构建系统 Blaze、协议缓冲区等工具与流程，并讨论了频繁重…
编程语言与软件工程2017 · 1,127 分 · 465 评 · 引用 15入门 · 约 45 分钟编辑精选Peter Naur：编程作为理论构建 (1985)
Peter Naur – Programming as Theory Building (1985)
Peter Naur 1985 年的经典论文《Programming as Theory Building》提出：编程的本质不是写代码或文档，而是在程序员头脑中构建对程序及其运行…
编程语言与软件工程2016 · 629 分 · 74 评入门 · 约 45 分钟编辑精选SciPy 1.0：Python 科学计算的基础算法
SciPy 1.0: fundamental algorithms for scientific computing in Python
这篇发表于 Nature Methods 的论文介绍了 SciPy 1.0——Python 科学计算生态的基石库，涵盖其核心算法模块（优化、积分、插值、线性代数等）、软件架构与社…
编程语言与软件工程2020 · 387 分 · 98 评入门 · 约 45 分钟编辑精选Lisp 的历史（1979）
History of Lisp (1979)
这是 Lisp 发明者 John McCarthy 于 1979 年为 HOPL（编程语言史）会议撰写的回顾文章，讲述 Lisp 的起源、设计动机与早期演进，文中也涉及 if 表…
编程语言与软件工程2018 · 352 分 · 44 评入门 · 约 45 分钟编辑精选使用 NumPy 进行数组编程
Array Programming with NumPy
这篇 Nature 文章介绍 NumPy 的数组编程模型及其在科学计算中的核心作用：以 ndarray 为中心，通过向量化操作让 Python 高效处理多维数组。
编程语言与软件工程2020 · 318 分 · 134 评入门 · 约 40 分钟编辑精选