The functional-programming tag has no wiki summary.
0
votes
0answers
52 views
Constraint-Based Type Inference with Algebraic Data [closed]
I am working on an expression based language of ML genealogy, so it naturally needs type inference >:)
Now, I am trying to extend a constraint-based solution to the problem of inferring types, based ...
10
votes
1answer
304 views
Programming languages with canonical functions
Are there any (functional?) programming languages where all functions have a canonical form? That is, any two functions that return the same values for all set of input is represented in the same way, ...
3
votes
3answers
192 views
Automatic proofs or model checking in an extremely simplified functional language
Imagine a stripped down functional programming language, that has the following properties
The only value type is an integer
There are no side effects
Functions are defined as a single expression, ...
4
votes
3answers
306 views
What are the relationships between Functional Reactive Programming, Automatic Differentiation, Self-Adjusting Computation and Partial Evaluation?
Self-adjusting computation seems to be related to all of the other topics, but I would like to get a clearer sense of how they all relate. For example, do any of them subsume or obsolete any of the ...
-6
votes
1answer
215 views
What function has the signature $ A \times \left ( B + C \right ) \rightarrow \left ( A \times B \right ) + \left ( A \times C \right ) $?
$ A \times \left ( B + C \right ) $ is isomorphic to $ \left ( A \times B \right ) + \left ( A \times C \right ) $, right? That means there's a function from one to the other and another function ...
9
votes
2answers
260 views
What persistent data structure for a set of partially ordered elements?
I need to store sets of elements of type a. Type a is partially ordered, so comparing $a_1$ and $a_2$ can return smaller, greater, equal or incomparable.
One problem with hashtables is that two equal ...
6
votes
0answers
255 views
What is the origin and meaning of the phrase “Lambda the ultimate?”
I've been messing around with functional programming languages for a few years, and I keep encountering this phrase.
I understand what lambda means, the idea of an anonymous function is both simple ...
-5
votes
3answers
217 views
How can I call functions that are not “first-class functions”?
I mean, is there an antonym for "first-class function"?
6
votes
1answer
214 views
Implications of the rule of cumulativity in the Calculus of Constructions
Please help me understand some type theory research.
As suggested in "Type Checking with Universes" by Robert Harper and Robert Pollack, we can add the following rule to our otherwise standard COC or ...
5
votes
2answers
190 views
With equirecursive types are there downsides to making all types potentially recursive?
By this I mean to ask, is it a bad idea to have all type constructor term expressions abstracted with $\mu$ just in case they need to be recursive? For example,
$Bool : Type;$
$Bool = (\mu Bool' ...
6
votes
1answer
119 views
Prior work on finding domain-theoretic suprema of equivalent total functions?
In slightly more down-to-earth terms, this question is sort of about lazy evaluation in functional programming - except that it's more ambitious in general than just seeking what a typical Haskell ...
8
votes
3answers
942 views
Bootstrapping a Finger Tree Structure
After working with 2-3 finger trees for quite a bit I have been impressed by their speed in most operations. However, the one issue I have run into is the large overhead associated with the initial ...
3
votes
3answers
993 views
Is it possible to generate a collision free hash function from an equality function?
I'm wondering if it's possible to go from an arbitrary equality function:
Eq :: (obj, obj) -> bool
to an identity/collision-free hash function:
Id :: obj -> int
Where Id has the ...
1
vote
2answers
141 views
Automated transformation into spigot algorithm?
Is there any research on transforming 'standard' algorithms into spigot algorithms?
I'd be happiest with automated transformations, but happy to learn about any research in this area.
For my ...
7
votes
1answer
203 views
Functional Sparse-Matrix with good performance?
While writing a Petri Net program, I was faced with a choice about data structures to represent the graph. Adjacency lists (i.e. lists enumerating the arcs into and out of individual places or ...
8
votes
1answer
2k views
Category theory, computational complexity, and combinatorics connections?
I have been trying to read “Pearls of Functional Algorithm design”, and subsequently “The Algebra of Programming”, and there is an obvious correspondence between recursively (and polynomially) defined ...
11
votes
2answers
579 views
Purely Functional Equivalent of B-Tree?
I am exploring the idea of writing a DBMS in purely functional way. The traditional data structure used for indexing is B-Tree. I'd like to know some purely functional equivalent of B-Tree that would ...
15
votes
4answers
484 views
How are imperative languages more different from each other than functional languages?
I'm reading Simon Peyton Jones's The Implementation of Functional Programming Languages and there's one statement that surprised me a little bit (on page 39):
To a much greater extent than is the
...
3
votes
1answer
283 views
Confluently Persistent String Data Structure
I'm looking for a confluentially persistent data structure for a string - so far I'm looking at finger trees. That is, how would I resolve two edits to the same base tree, and would I be able to ...
7
votes
1answer
411 views
How do I choose a functional dictionary data structure?
I've read a bit about the following data structures:
Bagwell's Ideal Hash Tries
Larson's Dynamic hash tables
Red-Black trees
Patricia trees
...and I'm sure there are a lot of others out there. ...
20
votes
2answers
385 views
Can the cost of GC be neglected when analyzing the running time of worst-case data structures specified in a garbage-collected programming language?
I just realized that I have been assuming the answer to my question is "yes" but I don't have a good reason. I imagine that maybe there is a garbage collector that provably introduces only $O(1)$ ...
13
votes
2answers
508 views
Difference lists in functional programming
The question What's new in purely functional data structures since Okasaki?, and jbapple's epic answer, mentioned using difference lists in functional programming (as opposed to logic programming), ...
15
votes
3answers
1k views
Reader, Writer monads
Let $C$ be a CCC. Let $(\times)$ be a product bifunctor on $C$. As Cat is CCC, we can curry $(\times)$:
$curry (\times) : C \rightarrow(C \Rightarrow C)$
$curry (\times) A = \lambda B. A \times B$
...
10
votes
3answers
283 views
Which algorithms can be expressed using a total functional language with data parallel operators?
Imagine a functional programming language whose only data types are numerical scalars and arbitrary nestings of arrays. The language lacks any means of unbounded iteration, so the following are ...
11
votes
1answer
237 views
Associative hash mixing
Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths ...
22
votes
2answers
1k views
What are the outstanding questions in purely functional data structures?
This question is inspired by another question about what's new in PFDS since the publication of Okasaki's book in 1998.
I'll start with two questions I have:
Is there a purely functional set data ...
159
votes
5answers
33k views
What's new in purely functional data structures since Okasaki?
Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few:
IntMap (also invented by ...
10
votes
1answer
319 views
What are the theoretical limits of the Stratego Programming Language?
Stratego is a programming transformation language/Rewriting DSL.
Anthony Sloane has done some work doing an implementation that runs on Scala.
What are the theoretical limits of Stratego as a ...
4
votes
2answers
241 views
Given the following set of LISP primitives, is it possible to extend the eval function to evaluate defmacro?
In this paper McCarthy sets out the following primitives: QUOTE, CAR, CDR, CONS, EQUAL, ATOM, COND, LAMBDA and LABEL.
He then sets up the following abbreviations: T, NIL, DEFUN, NULL, CADR, LIST, ...
23
votes
7answers
1k views
Higher-order algorithms
Most of the well-known algorithms are first-order, in the sense that their input and output are "plain" data.
Some are second-order in a trivial way, for example sorting, hashtables or the map and ...
4
votes
2answers
367 views
Proof of a unique homomorphism from an initial object
What is the proof that there is only one homomorphism from an initial object to another object?
17
votes
2answers
718 views
Are lambda calculus and combinatory logic the same?
I am currently reading "Lambda-Calculus and Combinators" by Hindley and Seldin. I'm not an expert, but have always taken an interest in lambda calculus because of involvement with functional ...
11
votes
2answers
410 views
Simple balanced trees with O(1) concat?
In Purely Functional Worst Case Constant Time Catenable Sorted Lists, Brodal et al. present purely functional balanced trees with O(1) concatenate and O(lg n) insert, delete, and find. The data ...
