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.
264
questions
2
votes
1answer
51 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,...
6
votes
2answers
77 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 ...
0
votes
1answer
35 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 ...
28
votes
2answers
4k 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 ...
0
votes
0answers
45 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
1answer
44 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 ...
1
vote
0answers
27 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
23 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 ...
0
votes
1answer
23 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 ...
12
votes
1answer
160 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).
...
2
votes
1answer
56 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 ...
2
votes
2answers
58 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 ...
1
vote
2answers
51 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 ...
2
votes
1answer
43 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 ...
0
votes
0answers
32 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
2answers
56 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 ...
0
votes
0answers
17 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:
...
1
vote
1answer
71 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".
...
3
votes
1answer
37 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 ...
5
votes
3answers
82 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$...
1
vote
1answer
44 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$,...
5
votes
0answers
58 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 ...
2
votes
0answers
35 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 ...
1
vote
0answers
44 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 ...
14
votes
3answers
345 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
votes
1answer
47 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 / ...
3
votes
1answer
49 views
What are different ways to provide a semantics to a language?
Suppose you have 1. a grammar for terms of a language; 2. type-assignment rules, 3. a set of reduction rules. You want to prove that your language is adequate for mathematical reasoning. If I ...
1
vote
1answer
35 views
Tailrecursive definition for a function
In an exam I took we were asked to provide a tailrecursive definition of a recursive function. I failed miserably and the provided solution makes absolutely no sense to me. If anyone could explain ...
0
votes
2answers
113 views
Beta reduction order in Lambda calulus
Will it be wrong to use g for reducing (λx.λy.x) first in step (2) instead of using to reduce λg?
Is there a rule against it?
4
votes
1answer
75 views
Why are there two not operators in lambda calculus?
From Wikipedia:
$\mathrm{true} = \lambda a. \lambda b. a$
$\mathrm{false} = \lambda a. \lambda b. b$
Because true and false choose the first or second parameter they may
be combined to ...
1
vote
0answers
35 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 ...
3
votes
2answers
55 views
When are you supposed to eta-reduce?
Wikipedia lists the following algorithm for normalizing a lambda calculus term $t$:
If $t$ is not in head normal form, beta reduce the beta redex in the head position to get $t'$. Then normalize $t'$ ...
0
votes
0answers
40 views
Composition of compostion as a functor
"Composition of Composition" (i.e., (.) . (.)) in Haskell), has type ...
0
votes
1answer
233 views
First-order vs Higher-order Programs
Can someone explain the difference between first-order programs and higher-order programs in the context of programming languages?
My understanding so far is that Functional Languages (most) use ...
0
votes
2answers
101 views
Multiple inputs in lambda calculus (Confusing example)
In a programming class I take, we briefly (very briefly) touched lambda calculus. I think I have a pretty good grasp of the basics now, but one example given I just don't understand. Am I missing ...
1
vote
1answer
502 views
Is Pattern Matching as expressive as Case Expression in Haskell?
Nomenclature
The term expressive in the question shall bear the same meaning as in the following sentence:
A Turing Machine is as expressive as Lambda Calculus.
Introduction
While learning ...
0
votes
1answer
83 views
join is the heart of the monad because it encompasses everything a monad can do that a functor cannot. Is this true? [closed]
There is a controversy about Monad implementation in S.O .
The original question is,
What's so special about Monads in Kleisli category?
Is there any counterexample that Functors cannot do what ...
2
votes
2answers
84 views
How does one show $(\lambda x . (\lambda y.x))yx \equiv_{\beta} y$ in lambda calculus?
I wanted to show:
$$ (\lambda x . (\lambda y.x))yx \equiv_{\beta} y $$
the definition of beta equivalence is on page 17 of these notes.
I did a few attempts but got different things like $x$. I ...
2
votes
1answer
55 views
How do we show $\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x . x)$ in lambda calculus?
How do we show $$\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x . x)$$?
I was going through the slides here and it asked to do the above but by page 16 of the slides we have not ...
-1
votes
1answer
341 views
2
votes
4answers
111 views
How does one formally show that two lambda functions are $\alpha$ equivalent?
I was going through the following slides and I wanted to show the following:
$$ \lambda x. x \equiv_{\alpha} \lambda y . y$$
formally. They define a an $\alpha$-conversion on page 15 as follows:
$$ ...
2
votes
0answers
34 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, ...
5
votes
1answer
269 views
About the relationship between non-termination and inconsistency?
I've been trying to get into Agda and I noticed that it doesn't have recursion, which implies that it isn't Turing-Complete.
From what I could understand, if Agda had recursion, it would make itself ...
0
votes
1answer
69 views
Solving equations without side effects
Consider the example of solving for $x$ where $Ax=b$. This is not in general function, there can be more than one solution. So if you make such a solver in a functional style...does this count as a ...
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 ...
4
votes
0answers
46 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 ...
1
vote
0answers
22 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
1answer
63 views
how to deduce a function subtype rule from a given function type definition
This question relates to liskov substitution principle seems to have two conventional meanings but is really a different question, so I'm posing it as a new question.
I'm doing a bit of research into ...
1
vote
1answer
57 views
Stablishing termination of the construction of infinite stream with ranking functions
I'm working with Turing's paradigm to prove termination of programs by annotating functions with ranking functions and I encounter the following example:
...
2
votes
1answer
671 views
Reducing lambda expression to normal form
Can someone explain the steps to reduce
$$ (\lambda n. \lambda m. \lambda f. \lambda x.\ n\ (m\ f)\ x)\ (\lambda f. \lambda x.\ f\ (f\ x))\ (\lambda f. \lambda x.\ f\ x) $$
to $\lambda y. \lambda z.\...
