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.
378
questions
7
votes
1
answer
358
views
How is the definition of monads in category theory equivalent to the definition in functional programming?
In Haskell, Monad is a class of type constructors which act on types that have the following functions implemented:
...
- 235
0
votes
0
answers
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 ...
- 101
1
vote
2
answers
603
views
Mutation considered harmful, but is there a safe set
Functional programming does not have mutation. Mutation is usually harmful, however mutation is sometimes beneficial. e.g. Creating a [random number] generator.
In the same way that ...
- 138
5
votes
2
answers
560
views
Why don't imperative languages like C or Go support Haskell-like parametric polymorphism?
Why don't imperative languages support parametric polymorphism as powerful as whats in Haskell and OCaml?
More specifically if I call a function foo(x) that ...
- 243
5
votes
1
answer
528
views
Mathematical equivalent of reduce()?
filter() in functional programming can be thought of as being analogous to an equation that filters the range of the variable.
map() can be through of as a function mapping domain to codomain.
...
7
votes
2
answers
483
views
Why are the laws of an applicative functor defined the way they are?
Let's recall the definition of an applicative functor. Throughout this question, I write $x: T$ to denote that the value $x$ has type $T$.
Definition: An applicative functor consists of a type ...
- 203
4
votes
1
answer
416
views
How do you represent LISP as mathematical / logical model?
I asked this in stackoverflow, but the question probably fits here better.
This question arose from the objection that LISP is regarded as a functional language with some simple principles, namely ...
- 385
4
votes
1
answer
397
views
Type Inference and Generalization
I've been trying to understand type inference for Hindley-Milner-based languages, and I'm struggling to understand how generalization works. Let's say I have the following program in Haskell:
...
- 215
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 ...
- 379
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 ...
- 341
7
votes
1
answer
155
views
Can literals in functional languages be thought of as functions from the empty type?
A while ago, I think on Stack Overflow, I saw someone say that Haskell literals can be thought of as functions that don't operate on anything. This makes sense to me but I remember someone else ...
- 73
4
votes
1
answer
78
views
Inline caching in not object oriented languages
I've been recently studying inline caching as a technique to optimize method dispatch in object oriented languages. Basically, the idea is that one can remember what was previously dispatched and ...
- 2,230
2
votes
2
answers
103
views
Does proofs are programs apply to any functional program?
Does Curry howard correspondence, apply to all Functional Program, e.g. in Haskell. i.e. Is it possible to write Equivalent Haskell programs, to COQ proofs?
- 21
3
votes
5
answers
735
views
functional programming in terms of Set
I'm writing some notes about functional programming, so I'd want to describe some features of the category theory.
I visited wiki page about Category of Set, and I found this:
"The epimorphisms in ...
- 31
7
votes
2
answers
763
views
Higher-ranked polymorphism without explicit application or subtyping?
So, I'm familiar with two main strategies of having higher-ranked polymorphism in a language:
System-F style polymorphism, where functions are explicitly typed, and instantiation happens explicitly ...
- 29.5k
9
votes
2
answers
1k
views
λ -calculus : What is the most efficient in memory representation of functions?
I would like to compare performance of function encoded (Church's / Scott's) vs classically encoded (assembler / C) data structures.
But before I do that I need to know how efficient is / can be ...
- 243
38
votes
3
answers
5k
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 ...
- 581
0
votes
0
answers
46
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:
...
- 123
4
votes
1
answer
164
views
What is the name of this type of function composition?
If standard function composition is defined as:
(define compose
{ (B → C) → (A → B)
→ (A → C) }
F G -> (λ X (F (G X))))
What type of ...
2
votes
1
answer
74
views
Formally proving properties of fold function
Recall the fold function for lists:
$fold(f,z,[x,xs]) = fold(f,f(z,x),xs)$
$fold(f,z,[]) = z$
I want to formally proof that if $f$ is associative, commutative and idempotent (meaning $f(x,y) = f(x,...
- 2,230
1
vote
0
answers
47
views
How Do I Fix This Function? [closed]
I need help with my CS homework, and I don't quite know what to do..
The problem is to define a function and return a string as shown as:
...
- 11
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, ...
- 291
3
votes
1
answer
659
views
What type of function is main()?
As the functions are of 2 type:1.Pre-defined/library functions,2.User defined functions.
What type of function is main() function?
This doubt comes in my mind while writing a program we define the ...
- 222
1
vote
0
answers
870
views
What is a "pure recursive approach" [closed]
I am working on a homework assignment to create a function and it says to use a "pure recursive approach". I am trying to piece together what is actually meant by this. I am aware a recursive function ...
- 111
2
votes
1
answer
552
views
What makes data flow analysis higher level than control flow analysis?
I feel understanding why data flow is higher level than control flow is key to writing good code (and convincing others during code reviews). I find this repeatedly when arguing why my functional ...
- 173
4
votes
1
answer
867
views
Prove foldl fusion law
I have proven the foldr Fusion Law as follows:
Given f is strict, f a = b and ...
- 141
8
votes
2
answers
241
views
Why Church-encoded types aren't sufficient to express inductive proofs?
I've heard some claims that the calculus of constructions without inductive types isn't powerful enough to express proofs by induction. Is that correct? If so, why isn't the Church-encoding sufficient ...
- 4,047
4
votes
1
answer
58
views
Description of lists with functions in LISP
I have been given the following implementation of basic list functions in LISP:
...
- 2,230
6
votes
1
answer
125
views
Can we express the program to find last element of a list as a catamorphism?
So I've got a bit of category theory under my belt, and I am reading a few papers about calculating functional programs. I've expressed programs like summing a list as a catamorphism, and I've fused ...
- 95
11
votes
1
answer
656
views
Alternatives to Defunctionalization
Defunctionalization is a transformation first described 1972 by John C. Reynolds to eliminate higher-order functions. Are there alternative transformations (more efficient?) to eliminate higher-order ...
- 361
5
votes
1
answer
151
views
strong reduction of $\lambda$-terms, useful?
As we know many programming languages and systems don't implement the strong reduction of $\lambda$-terms, instead they do weak reduction (no reduction under abstraction).
I recently experimented ...
- 1,072
6
votes
1
answer
588
views
Lazy concatenative functional language
Can the idea of concatenative programming languages be extended to call-by-need evaluation strategy?
I see some problems that I will explain with few examples. I will use a prefix instead of a ...
- 475
8
votes
2
answers
460
views
Total functional programming language without an static type checker
All papers with the subject of total functional programming make use of some kind of static type checking to ensure totality. This make sense considering hoy easily is to make a language Turing-...
- 475
11
votes
1
answer
184
views
Can properties such as memory usage of a function be expressed in a dependently typed language?
Suppose one wants to reason about properties of code beyond things like totality and functional purity - one also cares about the memory consumption, or algorithmic complexity of a function. Can this ...
2
votes
2
answers
119
views
Lambda Calculus Prove Equality Excessive (Haskell-oriented)
I'm on a lambda calculus with parametric polymorphism a la Hindley-Milner Haskell-oriented course and I'm currently facing this exercise which I got stuck on.
Prove that $(\forall m\downarrow, n\...
- 45
0
votes
1
answer
99
views
Language Features Not Translatable into Lambda Calculus
Haskell is said to be a pure language because the language features are directly translatable into lambda calculus.
My question is: for languages considered to be non-pure functional languages (e.g. ...
user30564
2
votes
2
answers
2k
views
Lambda Calculus Type Inference
I'm currently trying to learn how to infer most general types on lambda calculus, and due to the lack of information on the subject I could find on Google I'm forced to attempt what I think is logical ...
- 45
10
votes
3
answers
3k
views
Are the words "expression" and "term" interchangeable in programming language theory?
When describing the syntax of a given programming language the words "expression" and "term" are often used to seemingly describe the same things. Are these words interchangeable in the context of ...
- 223
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 ...
- 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
...
- 610
4
votes
1
answer
113
views
In what cases is graph rewriting not enough to avoid duplicate work?
As I understand, evaluating something like the following in normal order evaluation is inefficient due to duplicate work:
...
user23039
19
votes
3
answers
4k
views
How to make a language homoiconic
According to this article the following line of Lisp code prints "Hello world" to standard output.
(format t "hello, world")
Lisp, which is a homoiconic language,...
- 459
3
votes
1
answer
160
views
Does the closure of a function include the actual parameter passed to the function?
A closure of a function includes the environment when calling the function.
Does the environment included in a closure of a function include the actual parameters for the function?
If I am correct, ...
- 4,775
11
votes
4
answers
1k
views
What are common formal techniques for proving functional code correct?
I want to provide proofs for parts of a Haskell program I'm writing as part of my thesis. So far however, I failed to find a good reference work.
Graham Hutton's introductory book Programming in ...
- 273
5
votes
1
answer
199
views
What are some possible "functional" memory structures?
With my thin knowledge on embedded systems, compilers, and computer architectures, I know that the basics of computer memory(physical) are sort of like an array, with addressing which work like ...
- 239
5
votes
1
answer
376
views
Why is Church-Rosser so important for basing programming languages on lamdba-calculus?
So, I know Church-Rosser has 2 thesis:
CR1: If $ E_1 \leftrightarrow E_2 $, then there exists an Expression E so $ E_1 \rightarrow E $ and $ E_2 \rightarrow E $
CR2: If $ E \rightarrow N $ (with N ...
- 137
10
votes
2
answers
215
views
Is there a paradigm for composing "incremental update" functions in a pure dataflow style?
I don't know the correct terminology for asking this question, so I'll describe it with lots of words instead, bear with me.
Background, just so we're on the same page: Programs often contain caches -...
- 103
6
votes
1
answer
290
views
Safe way to explicitly define new types instead of using Algebraic data types for my functional language
Question:
As I'm working on a Hindley-Milner typed lambda calculus, in order to make it usable I need to add some types such as list and pairs. The way I currently do it is, I have an ...
- 643
1
vote
3
answers
654
views
Should a pure function take all of the functions it calls as arguments?
After Wikipedia, if a function is pure, then:
[it] always evaluates the same result value given the same argument value(s).
So: if a function, let's call it f,...
- 119
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 ...
JC Saenz