<p><a href="https://stackoverflow.com/questions/3271256/implement-an-immutable-deque-as-a-balanced-binary-tree/3274355#3274355">There are a number of purely functional deques that support $O(1)$ operations at each end</a>. None that I know of are "uniquely represented" - deques with the same number of items can have different shapes. </p>

<p>In the imperative case, doubly-linked lists are uniquely represented deques with constant-time operations.</p>

<p><a href="http://alexandria.tue.nl/repository/notdare/772185.pdf" rel="nofollow">Hoogerwoord, in "A Logarithmic Implementation of Flexible Arrays"</a>, showed that Braun trees have logarithmic deque operations, and they are purely functional and uniquely represented.</p>

<p>Is there a deterministic uniquely represented purely functional deque with $o(\log n)$ operations? </p>

CC BY-SA 3.0
2014-09-27T23:20:05.510Z
What are the advantages of unique representation?
Geoffrey Irving
CC BY-SA 3.0
2014-09-27T23:48:14.060Z
@GeoffreyIrving, one advantage of a unique representation is shown in [Hartline et al.'s "Characterizing History Independent Data Structures"](http://users.eecs.northwestern.edu/~hartline/papers/hist-indep-ISAAC-02.pdf) - they have some useful security properties.
jbapple
CC BY-SA 3.0
2014-09-29T06:31:39.023Z
Doubly-linked lists are only uniquely represented if one cannot compare pointers.
Andrej Bauer
CC BY-SA 3.0
2014-09-29T09:09:31.443Z
The same is true for Braun trees, and binary tries, of course. Nonetheless, this seems to be the terminology. https://www.google.com/search?q=%22uniquely+represented+dictionaries%22
jbapple
<ds.data-structures><functional-programming>
Purely functional uniquely-represented deques
jbapple
# Purely functional uniquely-represented deques

(Asked by: username_0 on 2014-09-27)

[There are a number of purely functional deques that support $O(1)$ operations at each end](https://stackoverflow.com/questions/3271256/implement-an-immutable-deque-as-a-balanced-binary-tree/3274355#3274355). None that I know of are "uniquely represented" - deques with the same number of items can have different shapes.

In the imperative case, doubly-linked lists are uniquely represented deques with constant-time operations.

[Hoogerwoord, in "A Logarithmic Implementation of Flexible Arrays"](http://alexandria.tue.nl/repository/notdare/772185.pdf), showed that Braun trees have logarithmic deque operations, and they are purely functional and uniquely represented.

Is there a deterministic uniquely represented purely functional deque with $o(\log n)$ operations?

**Tags:** ds.data-structures, functional-programming
> **Comments:**
> **username_1**: What are the advantages of unique representation?  
> **username_0**: @GeoffreyIrving, one advantage of a unique representation is shown in [Hartline et al.'s "Characterizing History Independent Data Structures"](http://users.eecs.northwestern.edu/~hartline/papers/hist-indep-ISAAC-02.pdf) - they have some useful security properties.  
> **username_2**: Doubly-linked lists are only uniquely represented if one cannot compare pointers.  
> **username_0**: The same is true for Braun trees, and binary tries, of course. Nonetheless, this seems to be the terminology. https://www.google.com/search?q=%22uniquely+represented+dictionaries%22  

---

## 0 answers

