4k views

### How is algorithm complexity modeled for functional languages?

Algorithm complexity is designed to be independent of lower level details but it is based on an imperative model, e.g. array access and modifying a node in a tree take O(1) time. This is not the case ...
2k views

### Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration

I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations. Clojure provides persistent Vector,...
379 views

### Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?

I've read and been told way too many times that functional algorithms and data structures have an obligatory O(log(N)) slowdown in respect to their procedural (for-...
177 views

### rope data structure - undo operation

I was reading (wikipedia) about how the rope data structure might be suitable for a text editor. Within the article it mentions "If only nondestructive versions of operations are used, rope is a ...
414 views

### How to find point of maximum overlap in both X and Y Axis?

I was given a array R of n rectangles [each element in the array is a bottom left point(x1,y1) and a top right point (x2,y2)] , parallel to the axis, and an array P of n points [each element is a ...
67 views

### Calculate $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $a_i \geq u$ and $b_i \geq v$ maximizes

I have two datasets $A$ and $B$: $A = \{1, 5, -34, 34.34323, -23.5444, 9.43, ....\}$ $B = \{-0.5, 44, -0.243, -3455, 2.22221, -23.23, ....\}$ Those datasets contain a big amount of "random" numbers (...
371 views

### How would a priority queue be implemented in a functional programming language?

How would a priority queue be coded efficiently in a functional programming language? I'm new to functional programming, but I'm having difficulty understanding how a data structure that seems to ...
170 views

### Skip List estimate number of elements less than (or greater than) a value

I am looking for a thread safe data structure where an element can be searched in $O(\log n)$, for any value, $x$, the number of elements greater than (or less than) can be estimated in $O(\log n)$,...
96 views

### Can we implement every algorithm using only immutable variables?

Can we implement every algorithm using only immutable variables such that their space and time complexity is the same as using mutable variables?
67 views

### Is purely functional programming in some situations less efficient than imperative programming?

I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that ...