Started preparation of random access sequence topic.

bhehir · Aug 24, 2011 · f8d474c · f8d474c
1 parent b022a8e
commit f8d474c
Show file tree

Hide file tree

Showing 6 changed files with 93 additions and 2 deletions.
diff --git a/TODOLIST b/TODOLIST
@@ -1,5 +1,20 @@
+Ideas:
+- It's good to introduce the random access sequence problem with MTF
+  That, neither purely array nor the linked-list can perform well in
+  MTF (search for x, then remove x, and move x to the front).
+  Then we can introduced how to implement the random access sequence
+    including:
+	Numeric representation and binary tree solution;
+	Catenable list solution;
+  	Finger tree solution;
+  After that, we introduce about how to implement linked list in a settings
+  without pointer
+
+- Introduct BWT before MTF
+
+Backlogs:
 - Add ANSI C version BST
 - Review Python, Scheme BST
 - Add C++/C version of RBT
 - Add C/C++ version of AVL tree
-- Add MTF algorithm
+- Add MTF algorithm
diff --git a/datastruct/elementary/array/ref/ref.txt b/datastruct/elementary/array/ref/ref.txt
@@ -0,0 +1,5 @@
+Random access list:
+
+Purely Functional Random-Access Lists by Chris Okasaki. Functional Programming Languages and Computer Architecutre, June 1995, pages 86-95.
+
+http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#fpca95
diff --git a/datastruct/elementary/array/src/RAList.hs b/datastruct/elementary/array/src/RAList.hs
@@ -0,0 +1,62 @@
+{-
+    RAList.hs, Random Access List
+    Copyright (C) 2011, Liu Xinyu (liuxinyu95@gmail.com)
+
+    This program is free software: you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation, either version 3 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+-}
+
+module RAList where
+
+import Test.QuickCheck
+
+-- Based on Chris Okasaki's ``Purely Functional Datastructures''
+
+-- Different with Okasaki's original version, we denote leaf as 
+-- Node 1 x Empty Empty, so that the definition of binary tree
+-- is same as the normal binary tree with size augmented.
+
+-- Binary tree representation
+
+data Tree a = Empty 
+            | Node Int (Tree a) (Tree a) -- size, left, right
+
+-- Numeric representation, Binary numer
+data Digit a = Zero
+             | One (Tree a)
+
+-- The random access list is represented as a forest of binary trees.
+newtype RAList a = [Digit a]
+
+-- Auxilary functions
+size :: Tree a -> Int
+size Empty = 0
+size (Node sz _ _) = sz
+
+-- Precondition: rank t1 = rank t2
+link :: Tree a -> Tree a -> Tree a
+link t1 t2 = Node (size t1 + size t2) t1 t2
+
+cons :: a -> RAList a -> RAList a
+cons x ts = insertTree ts (Leaf 1 x 0 0) 
+
+insertTree :: RAList a -> Tree a -> RAList a
+insertTree [] t = [One t]
+insertTree (Zero:ts) t = One t : ts
+insertTree (One t' :ts)= Zero : insertTree (link t t') ts
+
+
+-- testing
+
+-- Reference
+-- [1]. Chris Okasaki. ``Purely Functional Random-Access Lists''. Functional Programming Languages and Computer Architecutre, June 1995, pages 86-95.
diff --git a/datastruct/elementary/list/README b/datastruct/elementary/list/README
@@ -0,0 +1,3 @@
+Topic: 
+  How to realize list in a settings without pointer, e.g. something like
+  the traditional BASIC, that list are implemented by array actually.
diff --git a/datastruct/elementary/queue/ref/ref.txt b/datastruct/elementary/queue/ref/ref.txt
@@ -0,0 +1,3 @@
+Catenable Double-Ended Queues by Chris Okasaki. International Conference on Functional Programming, June 1997, pages 66-74.
+
+http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#icfp97
diff --git a/transform/BWT/ref/memo.txt b/transform/BWT/ref/memo.txt
@@ -13,4 +13,7 @@ WIKI
 http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform
 
 Move-To-Front
-http://www.dgp.toronto.edu/~jstewart/378notes/13mtf/
+http://www.dgp.toronto.edu/~jstewart/378notes/13mtf/
+
+Finger tree
+http://www.soi.city.ac.uk/~ross/papers/FingerTree.pdf
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,3 @@
		Catenable Double-Ended Queues by Chris Okasaki. International Conference on Functional Programming, June 1997, pages 66-74.

		http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#icfp97