Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
1answer
24 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
19 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
60 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
25 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 ...
2
votes
2answers
32 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
24 views

Composition of compostion as a functor

"Composition of Composition" (i.e., (.) . (.)) in Haskell), has type ...
0
votes
1answer
58 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
53 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
158 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
70 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 ...
0
votes
0answers
50 views

Monads not with “flatMap” but “flatUnit”?

Monads in category theory is defined by triples T, unit, flat⟩. ...
2
votes
2answers
54 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 ...
0
votes
0answers
22 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
200 views
2
votes
4answers
84 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: $$ ...
1
vote
0answers
29 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
259 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
66 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
18 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
44 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
16 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
53 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
54 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
199 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.\...
2
votes
2answers
80 views

Proving parametricity for Gallina functions

I have the following definitions Definition nat'' {X : Type} := (X -> X) -> X -> X. Definition nat' := forall (X : Type), @nat'' X. And when I wanted to ...
19
votes
0answers
427 views

Can a calculus have incremental copying and closed scopes?

A few days ago, I proposed the Abstract Calculus, a minimal untyped language that is very similar to the Lambda Calculus, except for the main difference that substitutions are ...
5
votes
1answer
109 views

Best way to translate while loops to functions for software verification

I have a verification engine where while loops are translated into functional code, like this: ...
2
votes
2answers
90 views

Inference of a measure for a decreasing chain

Given integers $v_0,\dots,v_{n-1} \in \mathbb{N}$, I want to find an integer $t>0$, a map $f:\mathbb{N} \times \{0,1,\dots,n-1\} \to \mathbb{N}^t$, and a well-founded order $>_t$ on $\mathbb{N}^...
1
vote
1answer
72 views

pure function in C

There does not seem to be a canonical definition of "pure function", but the widespread language-agnostic understanding seems to be a function that has no side effects produces a value that is ...
-1
votes
2answers
48 views

Defining an HTML Template as an Algebraic Type

Wondering if/how you could define a highly nested structure as a Dependent Type (or an Algebraic or Parameterized type). Specifically, an HTML template. Not that they work like this (HTML templates ...
1
vote
2answers
122 views

functional vs state-based

As mentioned in Lambda Calculus - Computerphile, Alonzo Church's method is functional where a function as a blackbox, takes an input, processes, and produces an output, and Turing machines ...
4
votes
0answers
106 views

Why most purely functional red-black trees are left-leaning?

Is there any particular reason for picking a left-leaning red-black tree over a regular red-black tree when trying to do a purely functional implementation? I've not researched very deeply into this ...
0
votes
1answer
79 views

Are there any known implementations of a functional Heap's Algorithm?

TL;DR: Is an implementation of the Heap's Algorithm adhering to the principals of functional programming possible, and are any implementations of it known? And by "adhering to the principals of ...
2
votes
0answers
52 views

Term for weak head normal forms that cannot be reduced in any environment

In my understanding, a lambda expression is a normal form (NF) when it has no redexes. For instance, $\lambda x.x$ is a NF, but $(\lambda x.x)y$ is not. A lambda expression is a weak head normal form (...
-2
votes
1answer
37 views

Erlang- Creating a function which only adds/subtracts positive integers

I want to create a function which allows me to input a list, and then add all of the positive numbers from the list together, leaving any that are negative. ([3,1,-1]) For example only 3 and 1 would ...
2
votes
0answers
154 views

How would a priority queue be implemented in a functional programming language?

How would a priority queue be coded efficiently in a functional programming language? I'm new to functional programming, but I'm having difficulty understanding how a data structure that seems to ...
-2
votes
2answers
95 views

Are mathematical functions used in computer science? [closed]

Well, I know the difference between functions used in math and C language. But what are those specific areas where mathematical functions are used?
1
vote
1answer
48 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 ...
0
votes
1answer
74 views

Can we define the Functor Category in Haskell (or any other language with a more expressive type system)?

Here I am talking about the Functor category, which is defined as a category whose objects are functors and morphisms are natural transformations. For reference: https://ncatlab.org/nlab/show/functor+...
3
votes
2answers
68 views

Can we define a program by means of a walk of a graph induced by the category of types?

After reading about Category Theory at https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ I was wondering whether we can represent any program by means of a walk of a ...
3
votes
3answers
155 views

Is it possible to make a language that can build upon itself perfectly?

First of all, note that I'll have to explain my thoughts in a layman's terms. There are so many high-level programming languages out there that compete with each other. This means we have to build ...
1
vote
2answers
63 views

What mathematical terminology exists for “embellished trees”?

I'm looking for some pointers on proper mathematical (FP?, category-theory?) terminology. My apologies if the below is somewhat imprecise; I suppose the precision is precisely what I'm looking for in ...
2
votes
1answer
57 views

How is this lamda function beeing executed in an example for the Y combinator

I have spent a few hours now trying to understand how the Y Combinator is working and how it allows us to construct recursive functions with higher order functions. I have been going through this ...
3
votes
1answer
61 views

Can we implement every algorithm using only immutable variables?

Can we implement every algorithm using only immutable variables such that their space and time complexity is the same as using mutable variables?
1
vote
0answers
26 views

What extent of difference is considered significant in runtime?

I have a task to test the time required to evaluate a specialised function and a generalized function that aims to get the same output, and conclude whether there is a speed advantage of using one ...
3
votes
1answer
131 views

explaining $\lambda$-calculus/functional programming to someone used to Turing machines/procedural programming?

I have the following background: I have experience with object-oriented programming languages I find Turing machines and the concept of a "procedure" very intuitive. Yet I'm interested to ...
1
vote
1answer
60 views

Why does functional map() operation not permit operating on two elements of a list at a time?

Mathematically it seems so easy to use two elements of a vector as two arguments to a function. $$f(\boldsymbol{x_{i+1}},\boldsymbol{x_{i}})$$ In functional programming however a map (function) allows ...
2
votes
2answers
81 views

General term for map/fmap

The general term for folds is a catamorphism. The general term for unfold is an Anamorphism. Is there an equivalent term for map? I know that a map is a type of fold however restriction is ...
7
votes
1answer
105 views

Y combinator, function composition

I am trying to understand Y combinators. Could you please explain why the following are equivalent (Y (f ∘ g)) (f (Y (g ∘ f))) (Y is a fixed point combination)...
4
votes
1answer
50 views

How to explain/understand brackets of applicative functor [[f u1… un]]?

I am reading article about Applicative Abstract Categorial Grammars http://okmij.org/ftp/gengo/applicative-symantics/AACG.pdf and this article uses brackets [[...]] for action on terms inside ...