[Haskell-cafe] trees and pointers

Sergey Mironov ierton at gmail.com
Wed Jul 14 16:08:36 EDT 2010

Hi cafe! I have a question of C-to-Haskell type:)

Imagine web application wich allows users to browse some shared
filesystem located at the server.
Application stores every users's position within that filesystem
(current directory or file).

In C this can be implemented with the help of following data types:

struct tree_node {
	union item {
		// some file data
		struct file *file;

		// struct dir has link to another list of tree_node
		struct dir *dir;
	int type;

	// List of tree_nodes
	struct tree_node *next;
	struct tree_node *prev;

struct user {
	struct tree_node *position;

	// List of users
	struct user *next;
	struct user *prev;

This implementation will give us
1) O(1) time to insert to shared tree
2) O(1) time to access user's current position

Is it possible to reach this requirements in haskell?

For example, managing distinct tree type like

data TreeNode = File | Dir [TreeNode]

will lead to failure of req. 2 (have to traverse this
tree to find each user's position).

Also one could manage several zipper types (one for every user):

data TreeNodeCtx = Top | TreeNodeCtx {
	left :: [TreeNode],
	right :: [TreeNode],
	up :: TreeNodeCtx

data TreeNodeZ = TreeNodeZ {
	ctx :: [TreeNodeCtx]
	pos :: TreeNode

It works for one user but not for many because of req. 1 (have to
insert new item into
several zippers).

Any ideas?


More information about the Haskell-Cafe mailing list