Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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.

Filter by
Sorted by
Tagged with
137 votes
7 answers
41k views

Is Category Theory useful for learning functional programming?

I'm learning Haskell and I'm fascinated by the language. However I have no serious math or CS background. But I am an experienced software programmer. I want to learn category theory so I can become ...
user avatar
77 votes
4 answers
17k views

Dependent types vs refinement types

Could somebody explain the difference between dependent types and refinement types? As I understand it, a refinement type contains all values of a type fulfilling a predicate. Is there a feature of ...
Joey Eremondi's user avatar
38 votes
3 answers
5k views

How is algorithm complexity modeled for functional languages?

Algorithm complexity is designed to be independent of lower level details but it is based on an imperative model, e.g. array access and modifying a node in a tree take O(1) time. This is not the case ...
wsaleem's user avatar
  • 581
32 votes
2 answers
10k views

How do Functional Reactive Programming and the Actor model relate to each other?

FRP is about streaming events and behaviours through pure functions. The Actor model - at least, as implemented in Akka - is about streaming immutable messages (which can be considered to be discrete ...
Robin Green's user avatar
31 votes
3 answers
1k views

What is a brief but complete explanation of a pure/dependent type system?

If something is simple, then it should be completely explainable with a few words. This can be done for the λ-calculus: The λ-calculus is a syntactical grammar (basically, a structure) with a ...
MaiaVictor's user avatar
  • 4,137
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 ...
Neil's user avatar
  • 431
27 votes
2 answers
10k views

How to implement a Prolog interpreter in a purely functional language?

Is there a clear reference, with pseudo-code, on how to go about implementing a Prolog interpreter in a purely functional language? That which I have found so far seems to deal only with imperative ...
Jimster's user avatar
  • 373
27 votes
3 answers
4k views

What is the relation between functors in SML and Category theory?

Along the same thinking as this statement by Andrej Bauer in this answer The Haskell community has developed a number of techniques inspired by category theory, of which monads are best known but ...
Guy Coder's user avatar
  • 5,101
24 votes
2 answers
3k views

Is computation expression the same as monad?

I'm still learning functional programming (with f#) and I recently started reading about computation expressions. I still don't fully understand the concept and one thing that keeps me unsure when ...
Grzegorz Sławecki's user avatar
23 votes
4 answers
5k views

Why do we use persistent data structures in functional programming?

Functional programming employs persistent data structures and immutable objects. My question is why is it crucial to have such data structures here? I want to understand at a low level what would ...
gpuguy's user avatar
  • 1,799
23 votes
0 answers
1k 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 ...
MaiaVictor's user avatar
  • 4,137
22 votes
2 answers
1k views

What is meant by Category theory doesn't yet know how to deal with higher-order functions?

In reading Uday Reddy's answer to What is the relation between functors in SML and Category theory? Uday states Category theory doesn't yet know how to deal with higher-order functions. Some day, ...
Guy Coder's user avatar
  • 5,101
22 votes
2 answers
2k views

Category theory (not) for Programming?

After learning Haskell and other not so pure FP languages I decided to read about Category theory. After gaining good understanding of Category theory I started thinking about how the concepts of ...
Ankur's user avatar
  • 628
21 votes
5 answers
1k views

Lambda calculus outside functional programming?

I'm a university student, and we're currently studying Lambda Calculus. However, I still have a hard time understanding exactly why this is useful for me. I realize if you do loads of functional ...
Jacob's user avatar
  • 313
21 votes
1 answer
2k views

What classes of data structures can be made persistent?

Persistent data structures are immutable data structures. Operations on them return a new "copy" of the data structure, but altered by the operation; the old data structure remains unchanged ...
Realz Slaw's user avatar
  • 6,191
20 votes
4 answers
1k views

Why is it important for functions to be anonymous in lambda calculus?

I was watching the lecture by Jim Weirich, titled 'Adventures in Functional Programming'. In this lecture, he introduces the concept of Y-combinators, which essentially finds the fixed point for ...
Rohan Prabhu's user avatar
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, ...
user56834's user avatar
  • 3,892
19 votes
11 answers
7k 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. ...
BatWannaBe's user avatar
19 votes
3 answers
2k views

ML function of type 'a -> 'b

Our professor asked us to think of a function in OCaml that has the type 'a -> 'b i.e. a function of one argument that could be anything, and that can return ...
Gilles 'SO- stop being evil''s user avatar
19 votes
3 answers
4k views

How to make a language homoiconic

According to this article the following line of Lisp code prints "Hello world" to standard output. (format t "hello, world") Lisp, which is a homoiconic language,...
incud's user avatar
  • 551
19 votes
1 answer
1k views

Why hasn't functional programming researched dynamic trees?

Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging ...
user avatar
17 votes
1 answer
849 views

No Naive Set Theoretic Models of Polymorphic Lambda Calculus?

In Philip Wadler's paper on Theorems for Free he states in Section 2 on Parametricity that there are no naive set-theoretic models of polymorphic lambda calculus In the naive set-theoretic model ...
user avatar
17 votes
3 answers
832 views

Studying Programming Language Theory

I have recently become extremely interested in understanding and proving aspects of (functional) programming languages. However as I dive deeper in, things like $\lambda$ calculus, category theory, ...
daniel gratzer's user avatar
14 votes
1 answer
3k views

Concise example of exponential cost of ML type inference

It was brought to my attention that the cost of type inference in a functional language like OCaml can be very high. The claim is that there is a sequence of expressions such that for each expression ...
mrrusof's user avatar
  • 241
14 votes
2 answers
367 views

Are there peer-reviewed papers studying the pros and cons of functional programming?

Can somebody refer me to peer-reviewed papers studying the advantages or disadvantages of writing code in a functional style? Are there papers which discuss the applications of Lambda Calculus in ...
Dokkat's user avatar
  • 149
14 votes
2 answers
416 views

Are CPU architectures biased towards procedural runtimes?

Are there any changes that could be made to CPUs to make them perform better for concurrent runtimes like Rust? For instance, are there changes to branch prediction implementations or cache sizes ...
paIncrease's user avatar
13 votes
2 answers
2k views

Is there a theory/abstraction behind OOP?

Functional programming has the very elegant Lambda Calculus and its variants as a backup theory. Is there such a thing for OOP? What is an abstraction for the object oriented model?
Viclib's user avatar
  • 441
13 votes
1 answer
26k views

Difference between normal-order and applicative-order evaluation

The language I'm learning is Scheme and I'm working on an exercise that gives this: ...
user224530's user avatar
13 votes
3 answers
2k views

How does 'deforestation' remove 'trees' from a program?

I think understand how deforestation consumes and produces a list at the same time (from a fold and an unfold function -- see this good answer on CodeReview here), but when I compared that with the ...
Cris Stringfellow's user avatar
13 votes
2 answers
822 views

Do Higher Order Functions provide more power to Functional Programming?

I've asked a similar question on cstheory.SE. According to this answer on Stackoverflow there is an algorithm that on a non-lazy pure functional programming language has an $\Omega(n \log n)$ ...
vz0's user avatar
  • 233
13 votes
1 answer
327 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). ...
Lasse's user avatar
  • 233
12 votes
4 answers
3k views

Does immutability in functional programming really exist?

Although I work as a programmer in my daily life and use all the trendy languages (Python, Java, C, etc) I still have no clear view of what functional programming is. From what I've read, one property ...
Pithikos's user avatar
  • 393
12 votes
1 answer
855 views

The "CPS" approach has done great harm to performance in SML/NJ; reasoning desired

In a comment to Learning F#: What books using other programming languages can be translated to F# to learn functional concepts? Makarius stated: Note that the "CPS" approach has done great harm to ...
Guy Coder's user avatar
  • 5,101
11 votes
4 answers
31k views

What does "dummy argument" mean?

What is does it mean when an argument to a function is called a dummy argument? I have not encountered this term outside Fortran, is it a general term in computer science? What would be examples of ...
Kyss Tao's user avatar
  • 213
11 votes
4 answers
1k views

What are common formal techniques for proving functional code correct?

I want to provide proofs for parts of a Haskell program I'm writing as part of my thesis. So far however, I failed to find a good reference work. Graham Hutton's introductory book Programming in ...
FK82's user avatar
  • 273
11 votes
2 answers
3k views

Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration

I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations. Clojure provides persistent Vector,...
Tvaroh's user avatar
  • 255
11 votes
2 answers
218 views

Is there a paradigm for composing "incremental update" functions in a pure dataflow style?

I don't know the correct terminology for asking this question, so I'll describe it with lots of words instead, bear with me. Background, just so we're on the same page: Programs often contain caches -...
Hallting's user avatar
  • 113
11 votes
1 answer
188 views

Can properties such as memory usage of a function be expressed in a dependently typed language?

Suppose one wants to reason about properties of code beyond things like totality and functional purity - one also cares about the memory consumption, or algorithmic complexity of a function. Can this ...
Dr. John A Zoidberg's user avatar
11 votes
1 answer
695 views

Alternatives to Defunctionalization

Defunctionalization is a transformation first described 1972 by John C. Reynolds to eliminate higher-order functions. Are there alternative transformations (more efficient?) to eliminate higher-order ...
Peter's user avatar
  • 361
11 votes
1 answer
559 views

Constraint-based Type Inference with Algebraic Data

I am working on an expression based language of ML genealogy, so it naturally needs type inference >:) Now, I am trying to extend a constraint-based solution to the problem of inferring types, based ...
justkris's user avatar
  • 211
11 votes
1 answer
509 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 ...
SEC's user avatar
  • 241
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, ...
swr52's user avatar
  • 119
10 votes
3 answers
723 views

anonymous lambda functions (functional programming)

What are anonymous (lambda) functions? What is the formal definition of an anonymous function in a functional programming language? In my simple terms, when I am programming in scheme/lisp I would ...
CodeKingPlusPlus's user avatar
10 votes
2 answers
511 views

Proving a sorting operation in type system

I want to know how far a type system in a programming language can be beneficial. For example, I know that in a dependently typed programming language, we can create a ...
meguli's user avatar
  • 293
10 votes
3 answers
4k views

Are the words "expression" and "term" interchangeable in programming language theory?

When describing the syntax of a given programming language the words "expression" and "term" are often used to seemingly describe the same things. Are these words interchangeable in the context of ...
tibbe's user avatar
  • 223
10 votes
1 answer
1k views

What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?

On an imperative programming language, let us consider the following program: ...
yuezato's user avatar
  • 123
10 votes
2 answers
950 views

Which fixpoint is Haskell list type?

Let's say that lists are defined as List a = Nil | Cons a (List a) Then, in Haskell is List x the greatest or least fixpoint? ...
miniBill's user avatar
  • 419
10 votes
1 answer
2k views

What is the difference between the Mogensen-Scott and the Boehm-Berarducci encoding for ADTs on the Lambda Calculus?

On the Lambda Calculus, there are several different ways to represent a list. For example, one can encode it as its right fold: ...
MaiaVictor's user avatar
  • 4,137
10 votes
1 answer
367 views

Are combinatory logic terms always larger?

So there is an algorithm to convert lambda calculus terms to combinatory logic using SK combinators. It produces things that explode in size. I would like to know more about this explosion in size. I ...
Jake's user avatar
  • 3,810
10 votes
2 answers
521 views

Is there a canonical definition of “pure” function?

StackOverflow pointed me here, so the question might be a bit in a layman's terms. Wikipedia defines pure functions as In computer programming, a function may be described as a pure function if ...
Andrey Shchekin's user avatar

1
2 3 4 5
8