14
votes
3answers
1k views

How do purely functional programming languages deal with fast changing data?

What data structures can you use so you can get O(1) removal and replacement? Or how can you avoid situations when you need said structures?
-1
votes
1answer
208 views

Is there any practical algorithm / data-structure that can't be done with non-recursive Lambda Calculus augmented with foldl?

In my search for a practical non-turing complete programming language, I've been paying attention to lambda-calculus with disallowed self-application - that is, x x forbidden. After taking that ...
2
votes
3answers
225 views

Why it is `(cons 1 (cons 2 (cons 3 nil)))` and not `(cons 3 (cons 2 (cons 1 nil)))` for [1,2,3]?

Is there any special reason that to construct list in Scheme you use (cons 1 (cons 2 (cons 3 nil))) instead of (cons 3 (cons 2 (cons 1 nil))) ? While the first seems more obvious because it ...
3
votes
2answers
371 views

Is there any particular reason for the use of lists over queues in functional programming languages?

Most functional programming languages such as Scheme and Haskell use lists as their main data structure. Queues are identical to lists, except for the fact appending to the end - not to the begin - ...
9
votes
2answers
669 views

Uses of persistent data structures in non-functional languages

Languages that are purely functional or near-purely functional benefit from persistent data structures because they are immutable and fit well with the stateless style of functional programming. But ...
16
votes
2answers
1k views

What's the difference in content between Chris Okasaki's 1996 thesis and 1999 book, Purely Functional Data Structures?

I want to read Purely Functional Data Structures. I've easily found the thesis (which is freely available as a PDF), but see that there's a book available also. So I'd like to know what the ...
3
votes
3answers
406 views

Internal Mutation of Persistent Data Structures

To clarify, when I mean use the terms persistent and immutable on a data structure, I mean that: The state of the data structure remains unchanged for its lifetime. It always holds the same data, ...
7
votes
3answers
528 views

A deque based on binary trees

This is a simple immutable deque based on binary trees. What do you think about it? Does this kind of data structure, or possibly an improvement thereof, seem useful? How could I improve it, ...
8
votes
5answers
2k views

Data structures in functional programming

I'm currently playing with LISP (particularly Scheme and Clojure) and I'm wondering how typical data structures are dealt with in functional programming languages. For example, let's say I would like ...
7
votes
6answers
3k views

Which self balancing binary tree would you recommend?

I'm learning Haskell and as an exercise I'm making binary trees. Having made a regular binary tree, I want to adapt it to be self balancing. So: Which is most efficient? Which is easiest to ...