Hi there, I am trying to build a graph using adjacency list. There may be duplicated edges in the source file, so my idea is to build a hash table where the key is node and data is a node set. I will read source file line by line and build the hash table on fly. However, set is immutable and addit…

There is no need to build a deep copy of a set to add a new element. When adding a new element, we only need to create new nodes for the node on the path to the new elements, and those nodes share the unmodified subtree with the original node. Thus only, O(ln n) new nodes are created when adding a n…

Not sure how much this helps, but have you considered using the wonderful ocamlgraph library, instead of a hash table?

To add to @octachron ’s remark, I think you may have the wrong mental image of trees such as immutable sets. The principle of adding an item to a set is comparable to building a list by successively cons’ing items onto the (front of the) list. (There is obviously a little more to it with a self-bal…

To add to @cvine ’s remark, a good way to get the right mental images of purely functional data structures is to read Chris Okasaki’s Purely Functional Data Structures book.

I am new to OCaml and functional programming, so I think it would be a good way to understand the language by implementing a graph by myself. Still, thank you for the recommendation and I will check it!

I understand that adding an element to a set is O(log n) if it relies on a binary balanced tree. However, the “huge overhead for rebuilding” I thought is that we need to deep copy the original set and then add the new element to the new set. Please correct me if I misunderstand the “immutable” pro…

Thank you for pointing my mistake, but I am still confused about this “immutable” property. Say am passing a set as an argument and call the function recursively as below let rec list_to_set (s : IntSet) (l : int list)= match l with [] -> s | h::t -> IntSet.add s h; list_to_set s t; If…

Cheers! I am going to check it :wink:

The diagrams in this section give a good picture of what @octachron is talking about. Notice the node sharing between the old and the new tree.

Thank you for the diagram. It is much clear now!

Best practice to build adjacency list

Learning

octachron May 11, 2022, 6:56am 3

I am not sure what you mean by “huge overhead for rebuilding original set”. Adding a new element to a set is efficient.

1 Like

Topic		Replies	Views
Type for mutable sets Learning	4	803	May 31, 2022
Implemented a set class as a naive unordered one-linked-list Learning	3	413	January 24, 2023
Question about code Ported from SML to OCaml Learning	4	469	January 9, 2024
Standardized mutable data structures Ecosystem	34	2658	October 29, 2022
Proposal for the replacement of Set and Map in the stdlib Community	6	635	April 3, 2025

Best practice to build adjacency list

Related topics