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.
387
questions
4
votes
1
answer
61
views
What is the object translating part of a monadic endofunctor?
A monad is an endofunctor $T:C\rightarrow C$ with natural transformations $\eta:id_C\rightarrow T$ and $\mu:T^2\rightarrow T$.
Being natural transformations mean that $$T(f)\circ \eta_A = \eta_B\circ ...
CommunityBot
- 1
4
votes
3
answers
582
views
Functor composition rule necessary?
Sorry if this is a dumb question, but I don't quite understand the composition rule for functors.I see how the identity rule makes sense, as mapping the functor over the id function shouldn't change ...
- 2,757
3
votes
1
answer
251
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 ...
CommunityBot
- 1
0
votes
1
answer
59
views
Is Calling a Function a Side Effect
I've noticed a pattern in trying to make functional programming effective - there is still some kind of impure, effectful operation going on, but it gets holed up in a single, manageable imperative ...
CommunityBot
- 1
0
votes
1
answer
75
views
Is it possible for a language to have mixed evaluation strategies?
As far as I am aware, most functional programming languages today use a call-by-value eager evaluation strategy with some exceptions like Haskell. I am curious if it is possible for a language to have ...
CommunityBot
- 1
1
vote
2
answers
78
views
Is there a combinator that introduces brackets to a combinatory logic expression using just B?
Suppose I have the expression $abcdef$ and I want a combinator $X$ that does this:
$Xabcdef=a(bcd)(ef)$.
Is it possible to express $X$ using just the $B$ combinator, defined by
$Babc=a(bc)$?
Is ...
- 349
3
votes
2
answers
154
views
How, if possible, can we efficiently compute with lazy data structures in 𝜆-calculus?
In Haskell, we can use the following code to define fibonacci numbers,
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
And its time complexity is linear.
I cannot find ...
- 349
2
votes
1
answer
47
views
Is there any reference materials on complexity analysis for lazy languages?
Is there any books, papers or articles on how to analyze the time complexity of programs written in lazy languages such as Haskell?
I know how laziness is implemented and how it can be expanded and ...
- 23.1k
1
vote
1
answer
52
views
Understanding how lazy functional languages achieve IO (...sometimes?)
An Alternative view of I/O programs, popular in earlier lazy functional programming languages, was to see the input and output as Strings, that is as lists of characters. Under that model an I/O ...
- 685
12
votes
4
answers
3k
views
Does immutability in functional programming really exist?
Although I work as a programmer in my daily life and use all the trendy languages (Python, Java, C, etc) I still have no clear view of what functional programming is. From what I've read, one property ...
- 121
6
votes
0
answers
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 ...
0
votes
1
answer
87
views
Free variable in the programming language
From the wikipedia of Free variables and bound variables
In computer programming, the term free variable refers to variables used in a function that are neither local variables nor parameters of that ...
- 6,270
0
votes
1
answer
35
views
What are the non-overlapping properties of a function?
Specifically, properties that identify preconditions over which a function can be used without resulting in undefined behavior or data races.
For example, I am familiar with 3 important properties:
...
CommunityBot
- 1
6
votes
2
answers
273
views
Reference request: Monads, continuations, and other functional CS concepts
I've been using Clojure for about 18 months. Recently, I've come across terms such as Monads, Continuations, et al which I'd like to learn about.
I could visit Wikipedia and read about these two ...
- 299
1
vote
2
answers
67
views
(how) is assignment or binding possible in purely functional languages?
i can't seem to find much info on the following question:
how (if at all) is the fixing of names to values (by binding or assignment) possible in a purely functional system like the lambda calculus?
i'...
- 2,202
-1
votes
1
answer
185
views
Call by value is known as pure function how ?give reason
I think call by value may be pure function or impure function...
And pure function can be written through call by value or call by reference....
So according to the facts (c) should be correct ans......
CommunityBot
- 1
0
votes
0
answers
66
views
Representation of pairs in System F
System F defines the data type pair as:
$$X\times Y := \Pi Z. (X\to Y \to Z)\to Z$$
with:
$$\langle x,y \rangle := \Lambda Z. \lambda p^{X\to Y\to Z}.p \text{ }x\text{ } y$$
Projections are defined:
$$...
0
votes
1
answer
38
views
time complexity of loops
what is the time complexity of:
for (i = 1; i <= n; i = 2*i)
for (j = 0; j < i; j++)
sum++;
?
I thought it is O(nlogn) since the otter loop ...
- 390
2
votes
1
answer
65
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/...
- 659
3
votes
2
answers
153
views
Does this esoteric representation of integers have decidable equality?
Consider the following datatypes in Haskell:
data Foo = Halt | Iter Foo
newtype BigInt = BigInt {nthBit :: Foo -> Bool}
Foo ...
- 2,757
2
votes
2
answers
173
views
Translation between unit/bind and map/join in monads
Is there a translation between unit/bind and fmap/join in monads?
https://stackoverflow.com/questions/34398239/with-monads-can-join-be-defined-in-terms-of-bind
gives a partial one:
bind f m = join (...
- 575
2
votes
0
answers
104
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 ...
0
votes
1
answer
70
views
What is lambda caculus's "fix point combinators" corresponding to Turing Machine?
The lambda caculus equals to Turing Machine,so What is lambda caculus's "fix point combinators" corresponding to Turing Machine?
according to the paper <Primitive Rec, Ackerman's Function,...
- 31k
0
votes
1
answer
136
views
Compiler optimization pass joining identical function definitions together (or specializing them)
Consider this program transformation, in any direction, written in ANF:
...
- 23.1k
1
vote
1
answer
46
views
Literature on delta encoding serializeable ADTs
Suppose that I have some nested algebraic data type (ie. something one can construct via datas in Haskell) that is serializeable (so no functional fields ...
D.W.♦
- 164k
0
votes
0
answers
22
views
What are the similarities and differences between dependent function application and ML functor application?
Advanced Topics in Types and Programming Languages gives this rule section 2.2 gives this rule for dependent function application:
$$\frac{\Gamma \vdash t_1 : (\Pi x : S.T) \quad \Gamma \vdash t_2 : ...
- 358
8
votes
1
answer
705
views
Strictness in both arguments but not in each individually
I'm learning about strict functions in Haskell.
A function f is strict if f ⊥ = ⊥
Some functions are strict only in the first argument (for e.g. const), others are strict in the second (for e.g. map)....
7
votes
1
answer
1k
views
What exactly is the relation between Haskell and category theory?
In articles or Quora posts about category theory, I often find mentions of the programming language Haskell. I have little knowledge of category theory and even less of programming. Could someone ...
-1
votes
2
answers
137
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 ...
- 291
5
votes
2
answers
823
views
Functional Programming and Category Theory
I'm a math Ph.D. having done research in Algebraic Geometry and Algebraic Topology in grad school for my thesis and I've studied a fair amount of category theory in the process (e.g. having worked ...
- 291
138
votes
7
answers
41k
views
Is Category Theory useful for learning functional programming?
I'm learning Haskell and I'm fascinated by the language. However I have no serious math or CS background. But I am an experienced software programmer.
I want to learn category theory so I can become ...
- 291
4
votes
1
answer
102
views
Book references for combinatory logic as applied in Haskell?
I am looking for book references on combinatory logic. Is there a book focused on how combinatory logic is applied in the context of pure functional languages like Haskell?
I found "Combinators: ...
- 23.1k
2
votes
0
answers
58
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, ...
- 241
0
votes
0
answers
37
views
Ambiguous type of "triangle" operator for sum types
In Meijer, Fokkinga and Patersons "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" the ∇ operator for sum types is introduced which removes the tags from its ...
- 36
0
votes
0
answers
37
views
Programming language implementation challenge: is recursion harder than HOFs, or vice versa?
(Initially this question was on cstheory, but I was told cs would be a better fit, so posting it here.)
All other things being equal, which of the following languages would be more challenging to ...
- 179
1
vote
2
answers
898
views
Does it make sense to call GAP a "procedural" language?
GAP is a computer algebra system (CAS) that Wikipedia tells me is written in C, a procedural programming language. Does this mean we can say GAP's language is procedural? Or is this characterization a ...
- 39.1k
3
votes
2
answers
193
views
Curry–Howard correspondence and functional programming "reliability"
The first time I heard about functional programming, someone told me "it's more reliable to code in a functional style because your type system is like a proof of correctness".
I recently ...
- 291
8
votes
2
answers
618
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 ...
- 291
2
votes
3
answers
447
views
Proving monad laws for flatMap and unit, given laws for compose and unit
I'll use scala notation but hopefully things will make sense in general (I'm trying to prove that you can define a monad using either [flatMap (aka bind) and unit] or [compose and unit])
The book ...
- 291
9
votes
2
answers
2k
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 ...
- 101
0
votes
1
answer
83
views
Does category theory only deal with immutable objects? If so, why?
IIUC, category theory only applies to immutable objects, and mutability is modelled within that using e.g. functors, monads. Is that true? If so, why doesn't category theory include immutability? Has ...
- 31k
0
votes
1
answer
76
views
Are there any formal systems or programming languages in which its only possible to define functions that have inverses?
Consider an algorithm $f(x)$.
Are there formal systems or programming languages that only allow $f(x)$ to be defined if $f^-1(x)$ exists?
D.W.♦
- 164k
8
votes
2
answers
162
views
Does the concept of "side-effect" predate functional programming?
When I was reviewing a book, I saw that there's a sentence claiming "side effect is a term coming from the domain of functional programming". I would think that the concept existed before ...
- 129
0
votes
0
answers
59
views
Question about complexity of two topics in programming language theory
I am a student who is currently finishing second year of university mathematics. This summer I have to choose a topic for my diploma. Because I am particularly interested in computer science I am ...
- 203
-1
votes
2
answers
176
views
Are pure functions always computable functions?
Are pure functions always computable functions?
In computer programming, a Pure function is a function that has the following properties:
(1) the function return values are identical for identical ...
- 99
1
vote
2
answers
77
views
Can a strict right fold be implemented in a single loop?
A strict left fold is straightforward to implement as a loop, rather than with recursion:
...
- 413
3
votes
1
answer
160
views
Is possible to have a "pointer" to a tree node in a functional language?
Suppose I have the following structure definition in C:
struct node {
int value;
struct node *parent, *left, *right;
}
If I want to represent a specific ...
- 39.1k
0
votes
1
answer
28
views
How the indirect addressing works?
By other words, can anyone explain how indirect addressing works?
I red MARIE's LoadI X over and over and still didnt understand the logic behind it.
...
CommunityBot
- 1
1
vote
1
answer
154
views
Proving transitivity in an intuitionistic type theory without the K rule
In Agda, if I disable axiom $\mathbb{K}$ I'm not able to prove
$$
\forall\{A : \textbf{Set}\}\{a\ b : A\}\{p\ q : a \equiv b\} \to p \equiv q,
$$
which I guess is normal since the system does not ...
- 2,757
2
votes
2
answers
83
views
What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?
I know that retrieving an item in a collection can be done in $O(1)$ time(on average) using hash tables. I would like to know if there is an algorithm that could be as performance without using arrays....
- 235