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.
385
questions
137
votes
7
answers
40k
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 ...
dan
76
votes
4
answers
16k
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 ...
- 29.7k
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 ...
- 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 ...
- 673
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 ...
- 4,117
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
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 ...
- 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 ...
- 5,091
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 ...
- 1,799
23
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 ...
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 ...
- 4,117
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, ...
- 5,091
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 ...
- 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 ...
- 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 ...
- 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 ...
- 303
20
votes
3
answers
2k
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,642
19
votes
11
answers
6k
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. ...
- 357
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 ...
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,...
- 459
19
votes
1
answer
987
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 ...
JC Saenz
17
votes
1
answer
787
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 ...
user30564
17
votes
3
answers
800
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, ...
- 1,480
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 ...
- 241
14
votes
2
answers
365
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 ...
- 149
14
votes
2
answers
407
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 ...
- 279
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?
- 441
13
votes
3
answers
1k
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 ...
13
votes
2
answers
807
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)$ ...
- 233
13
votes
1
answer
316
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
12
votes
1
answer
25k
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:
...
- 121
12
votes
1
answer
839
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 ...
- 5,091
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 ...
- 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 ...
- 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,...
- 255
11
votes
3
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 ...
- 373
11
votes
2
answers
217
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 -...
- 113
11
votes
1
answer
184
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 ...
11
votes
1
answer
679
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 ...
- 361
11
votes
1
answer
550
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 ...
- 211
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, ...
- 119
10
votes
3
answers
717
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 ...
- 517
10
votes
2
answers
493
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 ...
- 293
10
votes
3
answers
3k
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 ...
- 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:
...
- 123
10
votes
2
answers
945
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? ...
- 409
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:
...
- 4,117
10
votes
1
answer
364
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 ...
- 3,790
10
votes
2
answers
508
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 ...
- 203
10
votes
1
answer
492
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 ...
- 231