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.

50 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
22
votes
0answers
639 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 ...
19
votes
1answer
787 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 ...
6
votes
0answers
58 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. ...
6
votes
0answers
95 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 ...
5
votes
0answers
41 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: ...
5
votes
0answers
72 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 ...
5
votes
0answers
59 views

Can we simulate any dependent datatype with `Eq`?

Consider the canonical homogeneous equality type: Eq : (A : Set) -> A -> A -> Set, with constructor ...
5
votes
0answers
76 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 ...
4
votes
0answers
47 views

Inferring ranking functions in a general code graph with partial information

Let me define the notion of call graph: A program consists on a set of functions $f,g,h,\ldots$ where each function $n$ is as a mapping $n: D^l \to D^m$. Here $D$ is the datatype representing ...
4
votes
0answers
251 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 ...
4
votes
0answers
114 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 ...
3
votes
0answers
96 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 ...
3
votes
0answers
156 views

Is there any programming system that enables reversible computations?

Better explained with examples, I need a programming system with the following characteristics: ...
2
votes
0answers
43 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 ...
2
votes
0answers
36 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 ...
2
votes
0answers
38 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, ...
2
votes
0answers
79 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 (...
2
votes
0answers
402 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 ...
2
votes
0answers
32 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 ...
2
votes
0answers
58 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 ...
2
votes
0answers
50 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 ...
2
votes
0answers
103 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 ...
2
votes
0answers
29 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 ...
1
vote
0answers
32 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 ...
1
vote
0answers
35 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 ...
1
vote
0answers
37 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 ...
1
vote
0answers
30 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
vote
0answers
31 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 ...
1
vote
0answers
40 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
0answers
19 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 ...
1
vote
0answers
23 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 ...
1
vote
0answers
31 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 ...
1
vote
0answers
106 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, ...
1
vote
0answers
62 views

Tricks, Tips and Nontrivial Insights with Higher-Order Functions

Many years ago I briefly skimmed a physical book (or perhaps a preprint?) on programming in Racket that included lots of really unique uses of map and ...
1
vote
0answers
388 views

How to get from factorial to a y-combinator?

In one of his conference talks Jim Weirich derives the applicative form of the y-combinator by refactoring a partial definition of factorial. The starting point in his talk is different than what ...
1
vote
0answers
48 views

How to reduce this with all 4 of normal applicative by-name by-value?

Given mult = \x -> \y -> x*y I am trying to reduce (mult (1+2)) (2+3) with each of the strategies: normal-order ...
1
vote
0answers
72 views

Algorithm for the function “drop” in a binary random-access list

In the book Purely Functional Data Structures by Okasaki, exercise 9.1 asks: Write a function drop of type ...
0
votes
1answer
80 views

Applying FP/Categorical terminology to non-FP languages

In my continuing effort to finally wrap my brain around advanced FP/categorical concepts, I've been reading dozens of articles and tutorials; what I have concluded is that: 1) Category Theory and ...
0
votes
0answers
40 views

Is this proof of the map fusion law correct?

I am reading Functional Programming in Scala, where I have been asked to prove the map fusion law. Since Scala is what I am familiar with, I am using as my notation a kind of pseudo-Scala. Here is ...
0
votes
0answers
34 views

Evaluation of function

Is this the right approach to the question or am I off-track? Function: let rec collect f = function | [] -> [] | x::xs -> f x @ collect f xs;; Question: ...
0
votes
0answers
39 views

What is the point-free version of f(x,y)?

What is the point-free version of f(x, y) ? Is it just f or some kind of function composition, since when curried there is an implicit function which is made ...
0
votes
0answers
53 views

How to collect free/bound variables in Lambda Calculus?

I am building a simple interpreter for untyped lambda calculus, currently trying to implement alpha-reduction. According to this document on LC: Alpha-reduction is used to modify expressions of ...
0
votes
0answers
33 views

Trying to determine Fixed Points

I'm basically trying to solve 4.2 (Taken from Semantics with Applications) As I see it, the functional F will be defined like so: ...
0
votes
0answers
32 views

What is the output of the program if the values are passed by value and-result and name?

I just want to make sure I'm doing this correctly. The first part is asking what the output is if the values are pasted by value-result and address of z[w] is computed at the time of the call. I got: ...
0
votes
0answers
47 views

Proof problem in Haskell with take and drop

Im learning Haskell and i want to prove take m (drop n xs) = drop n (take (m+n) xs) and drop m (drop n xs) = drop (m+n) xs Somebody can help me please? :)
0
votes
0answers
32 views

How is this defined in an iterative style?

This is the so-called recursive style: And this is the so-called iterative style: It seems like it is defined recursively to me. The function doesn't hide the next call of the function defined in it ...
0
votes
0answers
34 views

What is the nomenclature or theory for determining an overall status of multiple enumerations?

I am writing a method which evaluates multiple status enumerations and determines an overall status. I'm looking for what this process might be called and perhaps some theory on it. It may be best to ...
0
votes
0answers
34 views

Analysis of the reduction of a function using (outermost) graph-reduction

I want to determine the time and space complexity of the following functions: ...
0
votes
0answers
131 views

what is the connection between evaluation context and call by value?

I been reading about $\lambda$-calculus and related stuff, but I got some confusions which i want to clarify. The call by value reduction is expressed with two rules $$ \frac{e_1 \rightarrow e_1'}{...
0
votes
0answers
41 views

How would one prove that the following scheme definition is an ordered stream of integers

How would one prove that the following scheme definition is an ordered stream of integers (define integers (cons-stream 1 (add-streams ones integers)))