h**c
发帖数: 1979 | 1 看OCaml实现哈希表也要用到mutability:
https://github.com/lucasaiu/ocaml/blob/
master/stdlib/hashtbl.ml
能用纯粹的函数式方法实现吗？难道函数式语言把side
effect藏到程序员看不到的地方就算完事了？ |
w***g
发帖数: 5958 | 2 藏到garbage collector. 纯fp数据结构那篇博士论文是少有的博士论文神作。
：
：看OCaml实现哈希表也要用到mutability: https://github.com/lucasaiu/ocaml/
blob/master/stdlib/hashtbl.ml。能用纯粹的函数式方法实现吗？难道函数式语言把
side |
h**c
发帖数: 1979 | 3 Out of sight, out of mind? 而且我的问题是如何实现哈希表这种常用结构。
【在 w***g 的大作中提到】
: 藏到garbage collector. 纯fp数据结构那篇博士论文是少有的博士论文神作。
:
: ：
: ：看OCaml实现哈希表也要用到mutability: https://github.com/lucasaiu/ocaml/
: blob/master/stdlib/hashtbl.ml。能用纯粹的函数式方法实现吗？难道函数式语言把
: side
|
w***g
发帖数: 5958 | 4 在语言层面可以做到纯函数。各种树都能做别说哈希表了。比如哈希表插入函数，输入
为哈希表和需要插入的对象，输出为一个*新的*哈希表。因为建了一个新的表，所以不
存在inplace
更新这个操作。但是从实现上，新表和老表通过reference共享了绝大部分内容，所以
空间代价还是O(1). 有点像docker用的那个洋葱文件系统。所有更新操作都通过包洋葱
实现。
一路摊过去。gc在背后收拾没用了的东西。
纯fp和imperative有点像数学上的对偶关系，本质是同一个东西，但表面上套路完全不
一样，没法直接翻译。比如插元素，它非要说是建新表，但背地里其实还是插元素。比
如算数列的一个元素，它非给你构造出一个无穷数列，到最后其实还是只算了一个元素
。说白了就是迂。
：Out of sight, out of mind? 而且我的问题是如何实现哈希表这种常用结构。
： |
h***n
发帖数: 1275 | 5 语言实现和语言，不是同样的东西
【在 w***g 的大作中提到】
: 在语言层面可以做到纯函数。各种树都能做别说哈希表了。比如哈希表插入函数，输入
: 为哈希表和需要插入的对象，输出为一个*新的*哈希表。因为建了一个新的表，所以不
: 存在inplace
: 更新这个操作。但是从实现上，新表和老表通过reference共享了绝大部分内容，所以
: 空间代价还是O(1). 有点像docker用的那个洋葱文件系统。所有更新操作都通过包洋葱
: 实现。
: 一路摊过去。gc在背后收拾没用了的东西。
: 纯fp和imperative有点像数学上的对偶关系，本质是同一个东西，但表面上套路完全不
: 一样，没法直接翻译。比如插元素，它非要说是建新表，但背地里其实还是插元素。比
: 如算数列的一个元素，它非给你构造出一个无穷数列，到最后其实还是只算了一个元素
|
g****t
发帖数: 31659 | 6 输出为(previous表的地址，diff）
这样旧表仍然是immutable的。这样可以吗？
Fp和imperative确实很多时候其实就是时域信号以及频域类似的关系。但是也有非常多
corner cases.
例如矩阵求逆写FP我觉得难度极大。fortran的库有
太多利用inplace改变矩阵元素的挖内存技巧了。
(我本科毕业设计本想沿着大三的课题
做AI,结果老板给
了本fortran数值计算书让改写成c plus plus。弄得我丢了半条命）
: 在语言层面可以做到纯函数。各种树都能做别说哈希表了。比如哈希表插
入函数
，输入
: 为哈希表和需要插入的对象，输出为一个*新的*哈希表。因为建了一个新
的表，
所以不
: 存在inplace
: 更新这个操作。但是从实现上，新表和老表通过reference共享了绝大部
分内容
，所以
: 空间代价还是O(1). 有点像docker用的那个洋葱文件系统。所有更新操作
都通过
包洋葱
: 实现。
: 一路摊过去。gc在背后收拾没用了的东西。
: 纯fp和imperative有点像数学上的对偶关系，本质是同一个东西，但表面
上套路
完全不
: 一样，没法直接翻译。比如插元素，它非要说是建新表，但背地里其实还
是插元
素。比
: 如算数列的一个元素，它非给你构造出一个无穷数列，到最后其实还是只
算了一
个元素
【在 w***g 的大作中提到】
: 在语言层面可以做到纯函数。各种树都能做别说哈希表了。比如哈希表插入函数，输入
: 为哈希表和需要插入的对象，输出为一个*新的*哈希表。因为建了一个新的表，所以不
: 存在inplace
: 更新这个操作。但是从实现上，新表和老表通过reference共享了绝大部分内容，所以
: 空间代价还是O(1). 有点像docker用的那个洋葱文件系统。所有更新操作都通过包洋葱
: 实现。
: 一路摊过去。gc在背后收拾没用了的东西。
: 纯fp和imperative有点像数学上的对偶关系，本质是同一个东西，但表面上套路完全不
: 一样，没法直接翻译。比如插元素，它非要说是建新表，但背地里其实还是插元素。比
: 如算数列的一个元素，它非给你构造出一个无穷数列，到最后其实还是只算了一个元素
|
h*i
发帖数: 3446 | 7 函数式编程本来就是用来追求更高层的抽象，更面向应用的，为什么要用函数式语言自
己实现这些数据结构？
常用数据结构应该是在语言层面提供的功能。下面是如何实现的，应用程序员不用管那
么多。同样，矩阵操作，这些都应该用标准的库，或是硬件厂商提供的库来做。
函数式编程是在底层库基础上提供的方便应用编程的一种用户界面而已。
【在 h**c 的大作中提到】
: 看OCaml实现哈希表也要用到mutability:
: https://github.com/lucasaiu/ocaml/blob/
: master/stdlib/hashtbl.ml
: 能用纯粹的函数式方法实现吗？难道函数式语言把side
: effect藏到程序员看不到的地方就算完事了？
|
h**c
发帖数: 1979 | 8 我给的例子是标准库里的啊，你去问标准库的作者为什么要用函数式语言写一个哈希表
【在 h*i 的大作中提到】
: 函数式编程本来就是用来追求更高层的抽象，更面向应用的，为什么要用函数式语言自
: 己实现这些数据结构？
: 常用数据结构应该是在语言层面提供的功能。下面是如何实现的，应用程序员不用管那
: 么多。同样，矩阵操作，这些都应该用标准的库，或是硬件厂商提供的库来做。
: 函数式编程是在底层库基础上提供的方便应用编程的一种用户界面而已。
|
l*********s
发帖数: 5409 | 9 the ratio of library programmers to application programmers is less than 1:
100, practically nobody cares.
【在 h**c 的大作中提到】
: 我给的例子是标准库里的啊，你去问标准库的作者为什么要用函数式语言写一个哈希表
|
j****n
发帖数: 1046 | 10 哪篇文章？想拜读一下
【在 w***g 的大作中提到】
: 藏到garbage collector. 纯fp数据结构那篇博士论文是少有的博士论文神作。
:
: ：
: ：看OCaml实现哈希表也要用到mutability: https://github.com/lucasaiu/ocaml/
: blob/master/stdlib/hashtbl.ml。能用纯粹的函数式方法实现吗？难道函数式语言把
: side
|
|
|
h*i
发帖数: 3446 | 11 不是文章，而是本书，博士论文很长的。
https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
但目前实用的函数式数据结构都不是okasaki的这种，而是从Bagwell的ideal hash
tree发展出来的。 https://lampwww.epfl.ch/papers/idealhashtrees.pdf
Bagwell的ideal hash tree本来不是immutable的，Rich Hickey发现它可以很容易变成
immutable的，所以就在这个基础上搞了immutable的vector, map,等等，作为Clojure
的基础数据结构。然后其他的FP语言，比如Scala也开始效仿，在ideal hash tree的基
础上搞了自己的immutable的数据结构。
【在 j****n 的大作中提到】
: 哪篇文章？想拜读一下
|
j****n
发帖数: 1046 | 12 谢谢，“老程序”员表示这世界变化快。
Clojure
【在 h*i 的大作中提到】
: 不是文章，而是本书，博士论文很长的。
: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
: 但目前实用的函数式数据结构都不是okasaki的这种，而是从Bagwell的ideal hash
: tree发展出来的。 https://lampwww.epfl.ch/papers/idealhashtrees.pdf
: Bagwell的ideal hash tree本来不是immutable的，Rich Hickey发现它可以很容易变成
: immutable的，所以就在这个基础上搞了immutable的vector, map,等等，作为Clojure
: 的基础数据结构。然后其他的FP语言，比如Scala也开始效仿，在ideal hash tree的基
: 础上搞了自己的immutable的数据结构。
|
g****t
发帖数: 31659 | 13 git 基本上就是immutable的吧。类似的东西我觉得没有那么不常见。
什么数据都可以挂到git。所以我觉得immutable data structure不难理解。
【在 j****n 的大作中提到】
: 谢谢，“老程序”员表示这世界变化快。
:
: Clojure
|
d******c
发帖数: 2407 | 14 更早的应该是Log structured storage, 数据库都是用的这个，几十年了。
http://blog.notdot.net/2009/12/Damn-Cool-Algorithms-Log-structured-storage
【在 g****t 的大作中提到】
: git 基本上就是immutable的吧。类似的东西我觉得没有那么不常见。
: 什么数据都可以挂到git。所以我觉得immutable data structure不难理解。
|
h**c
发帖数: 1979 | 15 有人专门写了本书，解释如何用rust实现链表
http://cglab.ca/~abeinges/blah/too-many-lists/book/
【在 l*********s 的大作中提到】
: the ratio of library programmers to application programmers is less than 1:
: 100, practically nobody cares.
|
h*i
发帖数: 3446 | 16 Storage and in memory data structure are completely different thing.
【在 d******c 的大作中提到】
: 更早的应该是Log structured storage, 数据库都是用的这个，几十年了。
: http://blog.notdot.net/2009/12/Damn-Cool-Algorithms-Log-structured-storage
|
m****o
发帖数: 182 | 17 根据在哪？Scala的Vector是基于优化版本的finger tree（2-3 tree）实现的。concat
，append，prepend都是O(1)，random access是O(logn)。
Clojure
【在 h*i 的大作中提到】
: 不是文章，而是本书，博士论文很长的。
: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
: 但目前实用的函数式数据结构都不是okasaki的这种，而是从Bagwell的ideal hash
: tree发展出来的。 https://lampwww.epfl.ch/papers/idealhashtrees.pdf
: Bagwell的ideal hash tree本来不是immutable的，Rich Hickey发现它可以很容易变成
: immutable的，所以就在这个基础上搞了immutable的vector, map,等等，作为Clojure
: 的基础数据结构。然后其他的FP语言，比如Scala也开始效仿，在ideal hash tree的基
: 础上搞了自己的immutable的数据结构。
|
h*i
发帖数: 3446 | 18 根据在代码里面：
https://github.com/scala/legacy-svn-scala/commit/
2a6427441622e1c94d36eb2d962a85cdc5591f90#diff-
ef59ae1920818cddd42a380fc636af4f
上面是Scala的immutable hashmap实现的第一个commit，时间是2010年3月7日。Commit
message:
"- new immutable HashMap implementation based on a hash trie. this is the
first iteration, more optimizations will be added later."
另见
https://en.wikipedia.org/wiki/Hash_array_mapped_trie
Clojure的公开发布是在2007年10月16日，从公开的第一天就有immutable HAMT，因为
Clojure的数据结构完全是建立在HAMT的基础上的。Rich Hickey花两年时间主要用来研
究这个了。
concat
【在 m****o 的大作中提到】
: 根据在哪？Scala的Vector是基于优化版本的finger tree（2-3 tree）实现的。concat
: ，append，prepend都是O(1)，random access是O(logn)。
:
: Clojure
|
n*****3
发帖数: 1584 | 19 赞 专家, 有理有据!
Commit
【在 h*i 的大作中提到】
: 根据在代码里面：
: https://github.com/scala/legacy-svn-scala/commit/
: 2a6427441622e1c94d36eb2d962a85cdc5591f90#diff-
: ef59ae1920818cddd42a380fc636af4f
: 上面是Scala的immutable hashmap实现的第一个commit，时间是2010年3月7日。Commit
: message:
: "- new immutable HashMap implementation based on a hash trie. this is the
: first iteration, more optimizations will be added later."
: 另见
: https://en.wikipedia.org/wiki/Hash_array_mapped_trie
|
d******c
发帖数: 2407 | 20 他说git也是completely different thing吧。
我们是在比较广义的角度，说这种追加不修改的方式，和git和log structure有相似之
处，不是说git和log structure是更早的immutable data structure.
【在 h*i 的大作中提到】
: Storage and in memory data structure are completely different thing.
|
