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
-2
votes
1
answer
115
views
Lambda Expression Reduction
I am unable to solve the following lambda expression using both normal order (Call-by-name) and applicative order (Call-by-value) reduction. I keep getting different answers for both. This is the ...
- 3
0
votes
1
answer
151
views
generic way to convert imperative if-then-else statements into functional style?
In this question, I asked about a reference for translating imperative code to functional code. I want to ask a more specific question here.
How, in general, do we translate into functional style, a ...
- 3,752
1
vote
2
answers
174
views
resource on translating imperative programs to functional programs
I'm not asking this question for the purpose of any particular project. Rather, I'm trying to understand how to translate non-trivial programs in imperative style to functional style. By functional ...
- 3,752
0
votes
1
answer
57
views
Converting a function with single parameter to a function with multiple parameters
I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows:
Given a string or a list, do an aggregation operation on each of its elements. Here ...
- 3
3
votes
2
answers
310
views
When is cumulative type universes useful?
AFAIK, a hierarchy of type universe(Type^0: Type^1: Type^2: ...) was introduced to avoid inconsistency caused by Type: Type.
...
- 31
1
vote
0
answers
33
views
What is the maths name for a set which contains the Domain and Codomain of a function? [closed]
Im interested in this so that I can name a type parameter in a program I'm writing.
There is function that that has three parameters.
D, Domain
C, Codomain
X, where D is a subset of X and C is a ...
- 165
1
vote
0
answers
54
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 ...
king-side-slide
0
votes
2
answers
212
views
Does the callback concept of programming have any basis in computer science?
Although I seriously code with computer languages in general since 2010 and as an amateur programmer with programming languages in particular since 2015 (primarily Bash and JavaScript imperative ...
user109446
11
votes
1
answer
508
views
Semantics for de Bruijn levels
There is an exceptionally simple way to embed simply typed lambda calculus with de Bruijn indices in a functional host language (discussed by Carette, Kiselyov & Shan, and by Kiselyov). The ...
- 241
-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 ...
- 141
1
vote
2
answers
134
views
If declarative programming is possible at the instruction/action level?
I am considering what the possibilities are with declarative programming. I have a firm understanding of how to use declarative programming in practice, but, short of having examples, I don't know if ...
- 2,223
1
vote
0
answers
165
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 ...
- 239
2
votes
0
answers
98
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 ...
- 29.8k
5
votes
0
answers
61
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:
...
- 29.8k
6
votes
1
answer
398
views
Why does higher-order abstract syntax need an inverse to define catamorphisms?
In the introduction to the colorfully-named Boxes Go Bananas: Encoding Higher-Order Abstract Syntax with Parametric Polymorphism, Washburn and Weirich describe a problem in traditional formulations of ...
- 304
2
votes
1
answer
642
views
How does the function to curry and uncurrying another function work?
The following is the code to curry or uncurry a function in Haskell:
...
- 621
5
votes
1
answer
369
views
How to write a coterminating, effectful program?
[Using Idris for code examples and terminology, but the question is not about Idris per se]
In a post titled A Neighborhood of Infinity, @sigfpe argues that "the kind of open-ended loop we see in ...
- 253
2
votes
1
answer
52
views
Can most programs (except the IO part) be re-written as a sequence of matrix operations?
I got this idea recently. If we do not consider the data IO part of software, imagine the data is in the memory and we need to come out with some decision (which product to recommend to a user, how to ...
- 141
0
votes
0
answers
49
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 ...
- 621
2
votes
2
answers
70
views
Using function composition to turn a function into point free one
In Tacit Programming page on wikipedia, it is stated that the point free version of
p x y z = f (g x y) z is
p = ((.) f) . g
...
- 621
2
votes
0
answers
129
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 ...
- 121
0
votes
1
answer
51
views
What is the relation between the formal definition of strictness and its intuitive notion
I am currently reading Functional Programming in Scala and have encountered a statement in the book I cannot quite make sense of.
On page 67, we are told the formal definition of strictness:
"If the ...
- 103
2
votes
1
answer
168
views
Like transitive reduction, but removing vertices rather than edges?
Suppose I have a directed graph $G = (V, E)$ (or, which is the same, a relation on the set $V$ as defined by the adjacency matrix) that may contain three vertices $x, y, z$, such that $xy, xz, yz \in ...
- 229
1
vote
2
answers
117
views
Can we always transform a set of lines to a function?
If I have n lines in a programming language like Python (globally or inside a function):
...
- 135
-2
votes
1
answer
251
views
2
votes
1
answer
64
views
Are the definitions of constructs in terms of lambda terms issues in implementation/design or uses of functional languages?
In Lambda Calculus, natural numbers, boolean values, list processing functions, recursion, if function are defined in terms of lambda terms. For example, natural numbers are defined as Church numerals,...
- 4,895
6
votes
2
answers
135
views
Representing partialled/curried functions in postfix notation?
I'm working on a small query language in JSON. A query consists of a JSON array of JSON elements, such as strings, numbers, booleans, etc. Strings starting with a ...
- 173
0
votes
1
answer
305
views
Is "lazy evaluation" part of the compilation process or a run-time feature?
I'm studing the Clean functional programming language, and like other functional PL it uses Lazy Evaluation.
The thing that I can't get is when a PL that using ...
- 103
30
votes
2
answers
5k
views
Is Lambda Calculus purely syntactic?
I've been reading for a few weeks about the Lambda Calculus, but I have not yet seen anything that is materially distinct from existing mathematical functions, and I want to know whether it is just a ...
- 431
0
votes
0
answers
151
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 ...
- 129
0
votes
1
answer
118
views
Lazy streams and infinite series
I just started Unix System Programming with Standard ML and starting on page 22 Shipman begins to explain a pure functional way of avoiding the constant state changes of typing at a keyboard:
A ...
- 131
1
vote
0
answers
96
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,401
1
vote
0
answers
35
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 ...
- 171
0
votes
1
answer
28
views
Functional data structure fast to add and unorded deletion
I am looking for a functional data structure that would work in this role.
Adding items to the struct happens often. Removing items from the struct happens as often as adding them but I have no way ...
- 123
13
votes
1
answer
325
views
Is the IO monad technically incorrect?
On the haskell wiki there is the following example of conditional usage of the IO monad (see here).
...
- 233
3
votes
1
answer
3k
views
Why are both caller-save registers and callee save registers needed?
I am having a difficult time understanding callee and caller-save registers. I get that caller-save registers are those which are needed after function call and hence caller saves them in caller ...
- 163
2
votes
2
answers
240
views
Is purely functional programming in some situations less efficient than imperative programming?
I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that ...
- 283
1
vote
2
answers
297
views
lambda calculus with church numerals
today I found this term in our exercises: ((^fx.f(f(f x)) ^gy.g(g y )) ^z.z + 1) (0)
I am quit unaware how to solve this type of question.
I know this is the church numeral 3 , 2 , the identity ...
- 13
2
votes
1
answer
167
views
Which would be the most purely functional equivalent to generators?
Some programming languages, apart from functions, have generators (eg. Python's yield). Although generators are introduced in this Python's tutorial on functional programming, I don't think that they ...
- 175
0
votes
0
answers
35
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:
...
- 123
3
votes
2
answers
234
views
Can a language with some set of higher-order functions like map, fold and filter but without recursion or iteration be Turing complete?
I was reading this article and was wondering if there is any finite set of higher-order functions like map, fold or filter such that they could empower a language to be Turing complete even without ...
- 175
1
vote
1
answer
309
views
Avoiding "side effects" in recursive functions
I am writing a function to find the intersection between two sets.
The non-functional requirements of the assignment include avoiding "side effects".
...
- 113
3
votes
1
answer
44
views
"Immediate" method of translating arbitrary mutable program to equivalent unmutable program?
Consider the following program in "mutable style":
x=1
x=f(x);
x=f(x);
We can rewrite this in "immutable style" without changing the higher-level structure of ...
- 3,752
5
votes
3
answers
300
views
How exactly do we define parametric polymorphism?
My naive distinction between parametric polymorphism and ad-hoc polymorphism, is that:
In parametric polymorphism, the type is given as a variable: (pseudocode)
Function f: <.Type T> T $\to$ T {...
- 3,752
1
vote
1
answer
64
views
Generalization of Functors to other datatypes?
Functors in category theory, and also in its application to functional programming, can be seen as a kind of "structured" functions: Given two sets $A,B$, rather than just having a function $f:A\to B$,...
- 3,752
5
votes
0
answers
100
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 ...
- 3,752
2
votes
0
answers
46
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 ...
- 425
1
vote
0
answers
47
views
Reasons for why x - 1 and x -1 gives different result in some languages [closed]
I assume the reason space makes a difference in F# is due to reserving a certain function, when minus is in front of a number without space, however what are the reasons for this? I can't seem to find ...
- 11
20
votes
3
answers
3k
views
How would a CPU designed purely for functional programming be different?
CPU's are to an extent designed with in mind the software that people will write for it, implicitly or explicitly.
It seems to me that if you look at the design of instruction set architectures, ...
- 3,752
3
votes
1
answer
92
views
Intuition for “run” function of monads
I'm learning about monads, I understood why they are useful, I understood in general what bind, join, return do.
I also looked at basic usage examples for the basic reader / writer / state / list / ...
- 251