这篇笔记介绍不可变数据, Persistent Data Structure 和 Immutable.
但是不深入数据结构实现, 函数式编程理论.
定义
https://en.wikipedia.org/wiki/Persistent_data_structure
In computing, a persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure.
编程语言
FP: Haskell, Clojure, Elixir
类库: immutable-js
概念的区别
http://vkostyukov.ru/posts/designing-a-pfds/
Immutability and persistent are quite similar terms, which often substitute each other. We say immutable vector (in Scala) but mean persistent vector (in Clojure): both implementations are based on the same abstract data structure Bit-Mapped Vector Trie but named differently. Although, there is a slight difference between immutability and persistence as they apply to data structures.
- Persistent data structures support multiple versions
- Immutable data structures aren't changeable
优势
http://stackoverflow.com/a/4400389/883571
http://www.quora.com/What-are-the-advantages-and-disadvantages-of-immu...
- 多线程安全, 可靠
- 对于需要多份数据的情况, 可以重用结构
- 函数式编程
劣势
http://concurrencyfreaks.blogspot.sg/2013/10/immutable-data-structures...
- 使用门槛
- 需要编程语言实现好的 GC
底层实现
- Clojure
Clojure 的数据结构实现
Understanding Clojure's Persistent Vectors, pt. 1
http://hypirion.com/musings/understanding-persistent-vector-pt-1
- Haskell
Haskell lists are represented as singly linked list
haskelldata [] a = [] | a : [a]
http://stackoverflow.com/a/15063181/883571
http://i.stack.imgur.com/Y1Ajv.png
- Paper
A Functional Approach to Standard Binary Heaps
http://arxiv.org/pdf/1312.4666v1.pdf
写法
- Clojure
有变量. 但是复合数据结构是不可变的
clojure(def x 1) (defn p []x)(p) (def x 2) (p)
- Haskell
没有变量的写法, 只能用 let 定义表达式 alias name
或者在 do notation 里有赋值, 但底层不是赋值
https://en.wikibooks.org/wiki/Haskell/do_notation
haskelldo x1 <- action1x2 <- action2action3 x1 x2
haskellaction1 >>= \ x1 ->action2 >>= \ x2 ->action3 x1 x2
- Elixir
变量被引用就是不可变的值(不过在 process 级别有私有数据)
iex(6)> a = 1
1
iex(7)> b = fn -> IO.puts a end
#Function<20.90072148/0 in :erl_eval.expr/5>
iex(8)> b.()
1
:ok
iex(9)> a = 2
2
iex(10)> b.()
1
:ok
性能问题
- Performance
http://www.quora.com/Is-object-immutability-in-functional-programming-...
- GHC
Data immutability forces us to produce a lot of temporary data but it also helps to collect this garbage rapidly.
https://wiki.haskell.org/GHC/Memory_Management
- React 的性能优化
jsshouldComponentUpdate: function(nextProps, nextState) {return true; }
https://facebook.github.io/react/docs/advanced-performance.html
immutable-js
http://facebook.github.io/immutable-js/docs/#/
https://github.com/intelie/immutable-js-diff
https://github.com/intelie/immutable-js-patch
seamless-immutable
This level of backwards compatibility requires ECMAScript 5 features like Object.defineProperty and Object.freeze to exist and work correctly, which limits the browsers that can use this library to the ones shown in the test results below. (tl;dr IE9+)
object.freeze
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Glob...
jsvar o = Object.freeze(obj);
然而没有复用数据结构, 将会有性能问题:
https://medium.com/google-developers/javascript-application-architectu...
Well, you technically could use Object.freeze() to achieve immutability, however, the moment you need to modify those immutable objects you will need to perform a deep copy of the entire object, mutate the copy and then freeze it. This is often too slow to be of practical use in most use-cases.
怎样编写程序
- sum
haskellfoldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs
- maximum
haskellmaximum' :: (Ord a) => [a] -> a maximum' [] = error "maximum of empty list" maximum' [x] = x maximum' (x:xs) = max x (maximum' xs)
- white/for
http://www.haskellforall.com/2012/01/haskell-for-c-programmers-for-loo...
haskellwhile :: (Monad m) => m Bool -> m a -> m () while cond action = doc <- condwhen c $ doactionwhile cond actionfor :: (Monad m) => m a -> m Bool -> m b -> m c -> m () for init cond post action = doinitwhile cond $ doactionpost
- model
elm-- manage the model of our application over time model : Signal Model model =Signal.foldp update initialModel actions.signal
https://github.com/evancz/elm-todomvc/blob/master/Todo.elm#L314
