# 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.

305 questions
Filter by
Sorted by
Tagged with
63 views

### A monad is just a monoid in the category of endofunctors, what's the enlightenment?

Pardon the word play. I'm a little confused about the implication of the claim and hence the question. Background: I ventured into Category Theory to understand the theoretical underpinnings of ...
91 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 ...
1k views

370 views

### Do functional algorithms require more memory than imperative algorithms? [closed]

Let's suppose we are counting words in string. We split it so what we have is an array of strings. I'll use Python as an example. The imperative approach would as follows: ...
588 views

In Haskell, the Monads type class has the bind operator, which is represented by the symbol >>= The type of such operator is: ...
592 views

### Expressing semantics of an array as a function

An assignment questions asks the following: Consider an array 'var a : array[1..10] of real'. Express the semantics of this array as a function, defining the domain and codomain (you might ...
174 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 ...
83 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 ...
107 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 ...
226 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 ...
97 views

### Functional programming with branches that have no order?

I was wondering if there is any programming style in which the outcome does not depend on the order of statements or groups of statements such as guards. Vaguely, I imagine this would leave room for ...
497 views

### Can we prove mathematical induction statements in Lisp?

My previous question Can we prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ using a computer program? has a problem that it tries to cover too much ground. Here is a related question motivated by ...
302 views

### Lazy lists with call-by-value reduction strategy

I am currently writing lists with lazy semantics in the pure lambda-calculus with call-by-value reduction strategy. I tried to construct pleasant to use and relatively efficient "lazy" functions on ...
147 views

### Organizing a “speedback”

Speedback is the merging of speed-dating with feedback: a 2 min. 1-on-1 talk with all members of a group of people. I'm in a team and I want to plan the ideal speedback setup: all team members have ...
144 views

### Why do we distinguish between term abstraction and type abstraction in System F?

In System F, we distinguish between types and terms. Types are defined by the following BNF: \begin{align} A, B ::=&~\alpha && \text{(type variable)} \\ &|~A \rightarrow B &...
1k views

### Call by need compared to pass by function

SML uses pass‑by‑value, Haskell uses call‑by‑need. Unless I'm wrong (the purpose of this question), one can do call‑by‑need with SML, passing a function instead of a value; a function to be later ...
116 views

### The meaning and relevance of the locution ''no terminating implementation'' in type theory

In the context of a discussion of Haskell https://stackoverflow.com/questions/62509788/the-intuition-behind-the-definition-of-the-co-reader-monad, I was told that There is no terminating ...
52 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 ...
62 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,...
103 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 ...
112 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?
1k views

### Lambda Calculus Type Inference

I'm currently trying to learn how to infer most general types on lambda calculus, and due to the lack of information on the subject I could find on Google I'm forced to attempt what I think is logical ...
92 views

### Occurrences notation in “Compiling Pattern Matching to Good Decision Trees”

From Compiling Pattern Matching to Good Decision Trees (Luc Maranget, Proceedings of ML '08, pp. 35–46. ACM, 2008.) We also consider the usual occurrences. Occurrences are sequences ...
301 views

### Second order function formalization

I need to work on a optimizer for a language whose operator are second order functions. They are the well known ones filter, map, reduce, fold, foreach etc. etc. I need to formalize as much as ...
340 views

### Functional Programming and Parallelism

I have an option to learn a new language for parallel computing. As a parallel programmer what are the reasons one might want to invest time to learn functional programming for parallel computing?
348 views

### What is the name of this combinator?

I've recently started casually reading into combinatorial logic, and I noticed that a higher-order function that I regularly use is a combinator. This combinator is actually pretty useful (you can use ...
47 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: ...
46 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 ...
99 views

74 views

423 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 ...
32 views

### numeric stability of map reduce operations

I am building a small library for computing information retrieval metrics for classifiers (precision, recall, f1, accuracy, whatever). Typically each metric is built by calculating a single value for ...