# Purely Functional Data Structures的笔记(22)

## 按有用程度按页码先后最新笔记

• ### 展开 收起 第1页

2013-10-12 15:09   4人喜欢

• ### 展开 收起 第14页

函数式与命令式数据结构的主要区别： In particular, when we update an imperative data structure we typically accept that the old version of the data structure will no longer be available, but, when we update a functional data structure, we expect that both the old and new versions of the data structure will be available for further processing.

2013-03-16 13:04

• ### 展开 收起 第180页

Consider the following representation for catenable double-ended queues, or c-deques. A c-deque is either shallow or deep. A shallow c-deque is simply an ordinary deque, such as the banker's deques of Section 8.4.2. A deep c-deque is decomposed into three segments: a front, a middle, and a rear.

2012-08-01 11:34

• ### 展开 收起 第172页

More formally, we represent tries over binary trees as datatype α : Map = TRIE of α : option x α : Map Map M.Map Notice that this is a non-unifonn recursive type, so we will need polymorphic recursion in the functions over this type. 。。。

2012-08-01 11:26

• ### 展开 收起 第170页

An unsuccessful search in a trie might exit after examining only a few characters, whereas an unsuccessful search in a hash table must examine the entire string just to compute the hash function! 照此说法，trie树的性能应该比hash map还要好了？

2012-08-01 11:25

• ### 展开 收起 第169页

We abstract away from the particular representation of these edge maps by assuming that we are given a structure M implementing finite maps over the base type. Then the representation of a trie is simply datatype α : Map = TRIE of α : option x α : Map M.Map

2012-08-01 11:22

• ### 展开 收起 第168页

Binary search trees work well when comparisons on the key or element type are cheap. This is true for simple types like integers or characters, but may not be true for aggregate types like strings. 精辟！

2012-08-01 11:19

• ### 展开 收起 第158页

We obtain an efficient implementation of catenable lists that supports all op- erations in 0(1) amortized time by bootstrapping an efficient implementation of FIFO queues. 用tree来实现一个list？

2012-08-01 09:33

• ### 展开 收起 第156页

The second class of data-structural bootstrapping is structural abstraction, which is typically used to extend an implementation of collections, such as lists or heaps, with an efficient join function for combining two collections.

2012-08-01 09:32

• ### 展开 收起 第149页

For these reasons, we will often present code as if Standard ML supported non-uniform recursive function definitions, also known as polymorphic recursion [Myc84]. 多态递归？？？

2012-07-31 17:33

<前页 1 2 3