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.
373
questions
7
votes
1
answer
654
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)....
- 73
2
votes
1
answer
27
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: ...
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, ...
- 221
1
vote
0
answers
39
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/...
- 639
0
votes
0
answers
28
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 ...
- 26
0
votes
0
answers
29
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 ...
- 159
1
vote
2
answers
884
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 ...
- 113
3
votes
1
answer
140
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 ...
- 66
0
votes
0
answers
37
views
How to represent iso-recursive type operators?
I've just read Chap20 of "Types and Programming Language" by Benjamin C. Pierce, which describes the formal theory of recursive types. But it doesn't include type operators. I would like to ...
- 13
0
votes
1
answer
61
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 ...
- 103
0
votes
1
answer
65
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?
- 155
0
votes
0
answers
57
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
129
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 ...
- 89
1
vote
2
answers
54
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
0
votes
0
answers
31
views
Exercise from Algebra of Programming on catamorphisms
This is an exercise from Algebra of Programming which I'm reading for self-study.
Below, $T$ is the initial algebra of $F$.
What I've tried:
I can construct $h \circ F (\pi_2) : F(A \times B) \...
- 263
3
votes
1
answer
105
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 ...
- 133
0
votes
0
answers
23
views
resources about programming language theory,topics: zipper and monads
I am in need of exercises and solutions about these topics in programming language theory with ocaml, zippers and monads, I can't find much on google, or I am missing something?
7
votes
1
answer
820
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 ...
0
votes
0
answers
18
views
Does the identity between functions and data (in languages with first-class functions) have a name in CS?
Section §2.1.3 at page 90 of Structure and Interpretation of Computer Programs explains, with a very clear example, that first class functions in a language make functions themselves and data be the ...
- 73
0
votes
1
answer
19
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.
...
- 15
1
vote
1
answer
133
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
votes
2
answers
74
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
2
votes
3
answers
63
views
To what extent is `this` state considered hidden-state - or its mutations a side-effect?
I was re-reviewing a somewhat upvoted answer of mine where I attempt to explain the differences between pure, impure, deterministic, non-deterministic, and idempotent functions.
In my answer I use ....
- 421
2
votes
1
answer
189
views
Addition in Lambda calculus
Found this term for a supposed 'adder' in lambda calculus.
λabcd.ac(bcd)
Although I know about alpha-conversion and beta-reduction and all that stuff, I don't know ...
- 21
0
votes
1
answer
52
views
Continuation passing transform
I'm stuck on something in in Shan's article Shift to Control, about CPS. On page three he writes the CPS transform
...
- 115
2
votes
1
answer
144
views
Why use the Y combinator for recursion?
The Y combinator is defined as $$Y=\lambda f.(\lambda x. f (x x))(\lambda x. f (x x))$$
It has the following useful property:
$$Y g = g (Y g)$$
for some expression $g$.
It can be easily used to ...
- 55
2
votes
1
answer
39
views
What is the meaning of "You describe the result you want rather than specifying the steps required to get there." in Functional Programming?
One of the characteristics of functional programming is as follows:
You’re describing the result you want rather than explicitly specifying the steps required to get there.
I found this quote at ...
- 121
10
votes
4
answers
4k
views
What are some interesting/important Programming Language Concepts I could teach myself in the coming semester?
I’m a CS senior with and Individual Study period this coming semester, and I’ve decided I’d like to learn more about Programming Language Concepts. More specifically, different programming paradigms, ...
- 119
1
vote
0
answers
51
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 ...
0
votes
1
answer
37
views
Pure Directed Graph
How can a directed graph be efficiently represented in a purely functional language like Haskell? Could someone suggest relevant materials on this topic? (functional pearls perhaps?) Thanks.
- 287
2
votes
2
answers
106
views
Semantics and implementation of side effects
From a practical point of view, how do functional languages with formally specified semantics (like ML) handle side effects like printing? I'm aware of things like the IO monad in Haskell but I'm ...
- 287
0
votes
0
answers
38
views
Question about machine learning
Hello everyone I am new to the site, I have a question that was in the test and did not understand the parts that are in the question. This question from a test I failed to pass, in a machine learning ...
- 29
8
votes
2
answers
143
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 ...
- 241
3
votes
1
answer
124
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 ...
- 63
5
votes
2
answers
74
views
Is there one (or a few) canonical/ specific use cases for "functions returning functions" (beyond "decorators")?
Is there one (or a few) canonical/ specific use cases for "functions returning functions" (beyond "decorators")?
What can you do with "functions returning functions" ...
- 165
19
votes
11
answers
6k
views
Why do functional languages disallow reassignment of local variables?
Fair warning: I don't actually know a functional language so I'm doing all the pseudocode in Python
I'm trying to understand why functional languages disallow variable reassignment, e.g. ...
- 347
3
votes
0
answers
38
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, ...
- 131
1
vote
1
answer
42
views
Is it possible to allow passing arguments as references without breaking referential transparency in functional languages?
Referential transparency is a relatively new concept to me, but I understood that it means that a function will always give the same answer given the same arguments.
Would passing arguments by ...
- 262
0
votes
1
answer
49
views
Which overhead is smaller - function call or passing variables between processes?
the question is related to networking frameworks; callback-based approach requires you to call a callback function every time you receive a new data packet; this is not a good approach for high-load ...
- 111
0
votes
1
answer
110
views
Is this way to combine two functions into a new function called a function product?
I have been looking for a maths operation that allows me to combine functions in a specific way. For example if we have functions f and g both with single mappings from o to e and v to c respectively, ...
- 155
3
votes
1
answer
930
views
Difference between function, method, routine, procedure, subprogram, subroutine, block, task
I don't know if I should have posted this on StackOverflow or here but what's the difference between these terms? Are the definitions of these dependent on the programming languages or they're things ...
- 411
1
vote
0
answers
48
views
2
votes
3
answers
265
views
Set theory pertaining to category theory and functional programming
I'm reading an unfinished Introduction to Category Theory/Products and Coproducts of Sets and have come across the following:
A power set of a set is the set of all its subsets. A script 'P' is used ...
- 121
0
votes
0
answers
27
views
What are advantages of "streaming" syntax in functional languages with for-yielding like Scala?
In Scala we can print list
val nums = (1 to 10).toList
with both
...
- 117
0
votes
1
answer
33
views
Example on Referential transparency (wikipedia)
I have a rather foolish question on an example
explaining the idea behind Referential transparency
Here is given an example i not understand:
Consider a function that returns the input from some ...
- 213
2
votes
0
answers
39
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 ...
- 388
3
votes
1
answer
172
views
Is mutual inductive type definition essential in coq core language?
I'm studying Coq's core language and I found that mutual inductive type definition is in it.
https://coq.inria.fr/refman/language/core/inductive.html#theory-of-inductive-definitions
Before I read the ...
- 133
3
votes
2
answers
123
views
Plain-language example of how a functional style makes parallel programming easier
I read a few "function >> imperative/OOP" articles because I heard there was a move in imperative OOP languages toward a functional style of coding, especially encouraging pure ...
- 347
0
votes
2
answers
49
views
What is name of type " Function->Value->Bool = if (Bool) Function (Value) " in Category theory?
I am very new to functional programming so sorry if the question is stupid.
Having this function
...
- 109
5
votes
2
answers
268
views
Regarding Backus' Commentary on von Neumann-style Programming
in John Backus' 1978 FP paper "Can Programming Be Liberated from the von Neumann Style" he says
To help assemble the overall result from single words [von Neumann ie.
conventional mutation-...
- 209