Tagged Questions
36
votes
5answers
4k views
Doubly Linked List in a Purely Functional Programming Language
How does one go about doing doubly linked lists in a pure functional language? That is, something like Haskell where you're not in a Monad so you don't have mutation. Is it possible? (Singly linked ...
34
votes
8answers
2k views
Purely functional data structures for text editors
What would be good purely functional data structures for text editors? I want to be able to insert single characters into the text and delete single characters from the text with acceptable ...
31
votes
8answers
7k views
Haskell's algebraic data types
I'm trying to fully understand all of Haskell's concepts.
In what ways are algebraic data types similar to generic types, e.g., in C# and Java? And how are they different? What's so algebraic about ...
26
votes
5answers
2k views
What is the benefit of purely functional data structure?
There are large number of texts on data structures, and libraries of data structures code. I understand that purely functional data structure is easier to reason about. However I have trouble to ...
26
votes
8answers
1k views
Immutable data structures performance
I don't get how can something as a Set be immutable and still have an acceptable performance.
From what I've read in F# Sets internally use Red Black Trees as their implementation. If each time we ...
22
votes
1answer
914 views
What should I use Clojure's finger trees for?
Clojure's new contrib library group has a finger tree library. What are the use cases for finger trees in clojure? When should finger trees be used instead of one of clojure's other peristent data ...
20
votes
4answers
872 views
Implement an immutable deque as a balanced binary tree?
I've been thinking for a while about how to go about implementing a deque (that is, a double-ended queue) as an immutable data structure.
There seem to be different ways of doing this. AFAIK, ...
18
votes
3answers
2k views
What is the Zipper data structure and should I be using it?
The question is simple: I cannot understand the Zipper data structure.
My question is related to its uses with a Tree.
I want to understand how can I change the tree node using zipper. And how not ...
17
votes
5answers
509 views
How is memory-efficient non-destructive manipulation of collections achieved in functional programming?
I'm trying to figure out how non-destructive manipulation of large collections is implemented in functional programming, ie. how it is possible to alter or remove single elements without having to ...
17
votes
5answers
2k views
N-queens in Haskell without list traversal
I searched the web for different solutions to the n-queens problem in Haskell but couldn't find any that could check for unsafe positions in O(1) time, like that one that you keep an array for the / ...
16
votes
6answers
7k views
Why can I define structures and classes within a function in C++?
I just mistakenly did something like this in C++, and it works. Why can I do this?
int main(int argc, char** argv) {
struct MyStruct
{
int somevalue;
};
MyStruct s;
...
15
votes
8answers
1k views
Are some data structures more suitable for functional programming than others?
In Real World Haskell, there is a section titled "Life without arrays or hash tables" where the authors suggest that list and trees are preferred in functional programming, whereas an array or a hash ...
15
votes
1answer
990 views
Purely functional soft heap
Are there any implementations of a purely functional soft heap data structure in any language?
15
votes
2answers
885 views
Zipper like data structure with more then one cursor
The Zipper data structure is great when one wants to traverse a tree and keep the current position, but what data structure one should use if they want to track more then one position?
Let me explain ...
15
votes
1answer
1k views
Functional data structures in C++
Does anyone know of a C++ data structure library providing functional (a.k.a. immutable, or "persistent" in the FP sense) equivalents of the familiar STL structures?
By "functional" I mean that the ...
