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
23 votes
0 answers
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 ...
MaiaVictor's user avatar
  • 4,047
19 votes
1 answer
964 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 ...
user avatar
6 votes
0 answers
326 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 ...
Ruan's user avatar
  • 203
6 votes
0 answers
64 views

Is it possible to reduce functional equations to SAT?

The problem of finding a solution for functional equations can be defined as: Let A0, A1, A2... An, B0, B1, B2... Bn, X be terms of the lambda calculus, all terms known, except for X, unknown. ...
MaiaVictor's user avatar
  • 4,047
6 votes
0 answers
105 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 ...
Jake's user avatar
  • 3,760
6 votes
0 answers
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 ...
Viclib's user avatar
  • 441
5 votes
0 answers
212 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 ...
JetNoBrains's user avatar
5 votes
0 answers
60 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: ...
jmite's user avatar
  • 29.5k
5 votes
0 answers
96 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 ...
user56834's user avatar
  • 3,492
5 votes
0 answers
64 views

Can we simulate any dependent datatype with `Eq`?

Consider the canonical homogeneous equality type: Eq : (A : Set) -> A -> A -> Set, with constructor ...
jmite's user avatar
  • 29.5k
4 votes
0 answers
45 views

Monad with a partial inverse, but not a comonad

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, ...
AndreA's user avatar
  • 141
4 votes
0 answers
119 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 ...
Guy Coder's user avatar
  • 5,071
3 votes
1 answer
167 views

Is “x' = f(x)” a programming paradigm?

I'm the author of GateBoy (a gate-level simulation of the original Game Boy hardware) and Metron (a C++ to Verilog translation tool). One big issue I had to work around for both projects is the ...
tanjent's user avatar
  • 66
3 votes
0 answers
100 views

Alternative to a CALL as a composition?

I've seen a numerous interesting abstract machines (i.e. CESK) and evaluators (diverse meta-circular S-expression evaluators, i.e. vau, COLA) and other models (concatenative, SK/Lambda calculus) which ...
artemonster's user avatar
3 votes
0 answers
161 views

Is there any programming system that enables reversible computations?

Better explained with examples, I need a programming system with the following characteristics: ...
dokkat's user avatar
  • 121
2 votes
0 answers
41 views

Is there a functional programming language with inherent change propagation?

Change propagation in programming environments is an add-on at the framework level such as React. There was a lot of work on dataflow virtual machines in the wake of Backus's Turing Award Lecture on ...
James Bowery's user avatar
2 votes
0 answers
71 views

The word "algebra" in category theory

I am currently learning category theory and a saying that I see a lot is that X is the algebra of something (e.g. Monoid is an algebra of something). Can someone explain to me what that means? Thanks!
thoughtpolice's user avatar
2 votes
0 answers
82 views

What is the category theory interpretation of higher order abstract syntax?

Suppose you have a simple sort of lambda calculus abstract syntax tree. The fine details don't really matter. ...
Molly Stewart-Gallus's user avatar
2 votes
0 answers
98 views

What's the meaning of linguistics?

In the programming language theory world, there are two important terminologies, i.e syntax, and semantics. I can understand these two terminologies: syntax is about sentence's structure (e.g. a valid ...
chansey's user avatar
  • 245
2 votes
0 answers
96 views

Compiling an impure language into a pure stack-based language

For a personal learning and fun project, I build an abstract virtual machine based on a stack. The instructions are simple and act on the top of the stack only. There are also stack operators such as <...
Foxy's user avatar
  • 255
2 votes
0 answers
60 views

Reducing Kleene's predecessor for Church numerals

I am trying to "reinvent" Kleene's predecessor myself. The following code snippet should be self-explanatory. The idea is to make a 2-tuple and count up from zero, i.e. ...
nalzok's user avatar
  • 1,071
2 votes
0 answers
88 views

Simulating extensible sums with dependent types?

ML-style languages have a concept of "extensible" or "open" sum types, where variants can be declared at any point, and there's not a fixed number of constructors for the type. They're usually used to ...
jmite's user avatar
  • 29.5k
2 votes
0 answers
123 views

Integer-array indexing (e.g. numpy.take) as function composition: where can I find more resources?

For context, one of Numpy's features is that an an array of integers can be passed as an index to an array, and this selects values at all of the specified positions, in any order with possible ...
Jim Pivarski's user avatar
2 votes
0 answers
44 views

How can one flip a stream using corecursion

Following is the definition of codata stream: codata Stream where hd : Stream −> A tl : Stream −> Stream For simplicity I assume I have just a ...
Imago's user avatar
  • 425
2 votes
0 answers
47 views

What is the difference between ADTs and ASDLs?

ASDL stands for Abstract Syntax Description Language (ASDL), whereby ADT stands for Algebraic data type. By looking at Python.asdl it appears to me to be the same thingy, just with different names, ...
denis631's user avatar
  • 133
2 votes
0 answers
285 views

Term for weak head normal forms that cannot be reduced in any environment

In my understanding, a lambda expression is a normal form (NF) when it has no redexes. For instance, $\lambda x.x$ is a NF, but $(\lambda x.x)y$ is not. A lambda expression is a weak head normal form (...
user avatar
2 votes
0 answers
521 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 ...
Alecto Irene Perez's user avatar
2 votes
0 answers
36 views

numeric stability of map reduce operations

I am building a small library for computing information retrieval metrics for classifiers (precision, recall, f1, accuracy, whatever). Typically each metric is built by calculating a single value for ...
matanster's user avatar
  • 341
2 votes
0 answers
77 views

Functional Core Language representation of tuples

I am writing a compiler for a simple subset of standard ML (just for fun) and I am stuck on how to represent the core language (I should mention that I write it in Haskell probably). Basically what I ...
wirrbel's user avatar
  • 163
2 votes
0 answers
52 views

Structural induction in non-local program transformation

Assume a functional language and a specialization operation (pulling out sub-expressions): let f x y = (h 23 x) + (g 42 y) becomes ...
choeger's user avatar
  • 610
2 votes
0 answers
117 views

Defunctionalization and known arity function calls by pointer

Defunctionalization is nice for higher order functions where it is completely necessary to avoid runtime support, but in some cases it's favourable to use function pointers instead (since they don't ...
kvanbere's user avatar
  • 121
2 votes
0 answers
31 views

How does supercompilers relate to macro tree transducers?

Supercompilers can be used as a generalisation of deforestation of a functional program. Macro Tree Transducers composition can be used to the same effect, using a completely different approach. What ...
dokkat's user avatar
  • 121
1 vote
0 answers
46 views

Lambda calculus with unordered application

In lambda calculus, $\lambda xy.\phi$ isn't in general equivalent to $\lambda yx.\phi$. However, it seems possible to imagine a calculus which replaces application with something like specification, ...
SEC's user avatar
  • 221
1 vote
0 answers
46 views

Is there any formalization of GADTs implemented in OCaml?

There are papers that describe how generalized algebraic datatypes (GADTs) are encoded in core Haskell (System FC)[1][2], but I could not find any documentation on how OCaml formalizes/implements/...
Apoorv's user avatar
  • 639
1 vote
0 answers
62 views

Shallow Binding with static scope, is it possible?

I'm new in programming, I'm currently studying programming languages. I'm trying to implement Shallow Binding with static scope, starting from an abstract syntax (producing a programming language ...
Alexander Pisanoff's user avatar
1 vote
0 answers
48 views

Delayed "let" in SICP

In section 3.5.4 , i saw this block: ...
user137213's user avatar
1 vote
0 answers
45 views

Should I use Dr. Racket for learning Scheme?

I've been fiddling with software development for a couple of years and in trying to get into the gist of things I came across SICP, which uses Scheme. Basically what I want to do at this stage is to ...
Pablo Aguirre de Souza's user avatar
1 vote
0 answers
40 views

Can a lambda expression be beta-equal to beta-normal forms?

Given a Lambda Expression Term T can it be beta-equal to two different Lambda Terms T1 and T2, both T1 and T2 are in beta-normal form?
javesh bhardwaj's user avatar
1 vote
0 answers
123 views

Constraint based analysis: understanding the program $[[ \text{fn} \ x => [x]^1]^2 [ \text{fn} \ y => [y]^3]^4]^5$

I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter 1.4 Constraint Based Analysis says the following: 1.4 Constraint ...
The Pointer's user avatar
1 vote
0 answers
26 views

N-dimensional generalization of map and reduce?

Is there any conceptual generalization of higher-order functions like map and reduce but for N-dimensional objects (e.g. arrays or tensors)? For mapping, I guess it would be a point-wise ...
nohamk's user avatar
  • 175
1 vote
0 answers
92 views

Is there a known way to make an efficient, compact, and fully persistent stack or queue?

In the world of mutable/ephemeral data structures and imperative programming languages, one of the classic ways to implement a stack or queue is to use array doubling: use mutation to fill up or empty ...
dfeuer's user avatar
  • 409
1 vote
0 answers
49 views

Relationship between left identity and associativity

In an effort to better-grok monads I have reviewed many "Everything you need to know about Monads" tutorials out in the wild, but I feel like my understanding is still coming up a bit short. While ...
user avatar
1 vote
0 answers
157 views

Predecessor function with recursive types

I am defining the type Nat of natural numbers a recursive sum type: $$ Nat = \mu X. Unit \oplus X$$ Now, I have defined zero ...
Noel Arteche's user avatar
1 vote
0 answers
89 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....
TomR's user avatar
  • 1,381
1 vote
0 answers
34 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 ...
toantruong's user avatar
1 vote
0 answers
48 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 ...
PyRulez's user avatar
  • 766
1 vote
0 answers
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 ...
Eric's user avatar
  • 111
1 vote
0 answers
43 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 ...
Encipher's user avatar
  • 167
1 vote
0 answers
33 views

What extent of difference is considered significant in runtime?

I have a task to test the time required to evaluate a specialised function and a generalized function that aims to get the same output, and conclude whether there is a speed advantage of using one ...
Prashin Jeevaganth's user avatar
1 vote
0 answers
108 views

Is an inputless program redundant?

Are there useful programs that don't take inputs from a user, environment etc. such as key input, or the current time? A program that computed/printed out predefined data could be turned into a file, ...
Tobi's user avatar
  • 291