# Questions tagged [functional-programming]

Functional programming is a programming paradigm which primarily uses functions as means for building abstractions and expressing computations that comprise a computer program.

75 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k views

### Can a calculus have incremental copying and closed scopes?

A few days ago, I proposed the Abstract Calculus, a minimal untyped language that is very similar to the Lambda Calculus, except for the main difference that substitutions are ...
• 4,137
1k views

### Why hasn't functional programming researched dynamic trees?

Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging ...
347 views

### Why most purely functional red-black trees are left-leaning?

Is there any particular reason for picking a left-leaning red-black tree over a regular red-black tree when trying to do a purely functional implementation? I've not researched very deeply into this ...
• 203
89 views

### Is it possible to reduce functional equations to SAT?

The problem of finding a solution for functional equations can be defined as: Let $A_0, A_1, A_2, \dots, A_n, B_0, B_1, B_2, \dots, B_n, X$ be terms of the $\lambda$-calculus, where all terms are ...
• 4,137
106 views

### Bounded existential polymorphism

In his "Types and Programming Languages", Pierce, at the very end, presents the most powerful system in the book: $F^{\omega}_{<:}$. He, however, does not explain how bounded existential ...
• 3,800
88 views

### What are the properties of the unsided fold?

Foldl and folr are 2 very important functions for FP and Haskell, but I have never heard much about the unsided fold: fold f [a,b,c,d] = (f (f a b) (f c d)) That ...
• 441
233 views

### Normalization-by-evaluation for untyped lambda calculus which results in 𝛽𝜂-normal form

Usual NbE algorithms for untyped lambda calculus, which use (P)HOAS to embed terms to a host language constructs, results in a beta-normal form of a terms. Is there algorithms to (efficiently) exploit ...
61 views

### Rules for consistency with mutual inductive families?

I'm trying to use a proof assistant to define a type and a relation that are mutually dependent on each other: ...
• 29.8k
101 views

### Difference between "functional programming languages" and "lambda calculus based languages"?

In "Can programming be liberated from the Von Neumann Style?", John Backus states: The main reason FP systems are considerably simpler than either conventional languages or lambda-calculus-based ...
• 3,982
65 views

### Can we simulate any dependent datatype with Eq?

Consider the canonical homogeneous equality type: Eq : (A : Set) -> A -> A -> Set, with constructor ...
• 29.8k
49 views

I have encountered a structure that looks like a monad with a one-sided inverse and some additional properties. I am not sure which properties of this structure are essential and which are accidental, ...
• 141
120 views

### Is there any research to indicate programmers are/are not moving to a hybrid of functional and object-oriented?

I am converting the OCaml Format module which does I/O and maintains state in a record with mutable values. As such it is a good candidate for me to convert to pure F#, pure C# and a hybrid. Since ...
• 5,101
53 views

• 239
1 vote
97 views

### What is the difference between self-rewriting program and program-with-updates-and-restart

I am reading about Goedel machine http://people.idsia.ch/~juergen/goedelmachine.html and especially the article about possible implementation (in the Scheme language) of this machine http://people....
• 1,401
1 vote
35 views

### Why in the Map Reduce Implementation, why not stream the records to the reducer (via TCP) as they are being produced by the mappers?

In the Map-Reduce implementation, the reducers start when all mappers finish their jobs. Why don't we stream the records from mappers to reducers while they are being processed instead? I think there ...
• 171
1 vote
51 views

### Can you use CPS to simulate state in a stateless programming language?

In a language supporting CPS, but no built in global state, we can represent a state based computation using a function. We call this function a state function. Assume the function takes three ...
1 vote
22 views

### How does the browser

I wondering how the browser's JS runtime implements these methods. I looked on the web and could not find any documentation. How does something like the V8 runtime actually work to implement these ...
• 111
1 vote
49 views

### Nested Function stuck on iteration update

I want to solve the Sparse Extended Information Filter Slam described by Dr. Sebestian Thrun in Probabilistic Robotics.I stuck in some nested function. The algorithm is described in page 309 in this ...
• 165
1 vote