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
123
votes
7answers
30k 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 ...
60
votes
3answers
10k 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 ...
38
votes
3answers
4k 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 ...
32
votes
3answers
838 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 ...
30
votes
2answers
8k 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 ...
29
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 ...
25
votes
2answers
8k 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 ...
25
votes
3answers
3k 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 ...
22
votes
4answers
4k 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 ...
22
votes
2answers
2k 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 ...
22
votes
2answers
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, ...
22
votes
0answers
636 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 ...
21
votes
5answers
983 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 ...
21
votes
2answers
1k 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 ...
19
votes
4answers
962 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 ...
19
votes
3answers
1k 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
1answer
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 though. ...
19
votes
1answer
784 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 ...
16
votes
3answers
3k 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,...
16
votes
3answers
579 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, ...
15
votes
1answer
378 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 ...
14
votes
2answers
316 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 ...
14
votes
3answers
500 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, ...
13
votes
2answers
1k 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?
13
votes
2answers
635 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)$ ...
12
votes
3answers
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 ...
12
votes
1answer
188 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). ...
12
votes
2answers
276 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 ...
11
votes
2answers
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,...
11
votes
1answer
2k 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 ...
11
votes
1answer
646 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 ...
11
votes
1answer
145 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
1answer
458 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 ...
10
votes
3answers
578 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 ...
10
votes
4answers
542 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 ...
10
votes
2answers
163 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 -...
10
votes
1answer
469 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 ...
10
votes
1answer
347 views

Do Self Types make the Calculus of Inductive Constructions obsolete?

Self Types are an extension of the Calculus of Constructions [1] that allow the language to express algebraic datatypes encoded through the Scott Encoding. The Scott Encoding provides one the ability ...
9
votes
2answers
326 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 ...
9
votes
3answers
2k 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 ...
9
votes
2answers
739 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? ...
9
votes
1answer
945 views

λ -calculus : What is the most efficient in memory representation of functions?

I would like to compare performance of function encoded (Church's / Scott's) vs classically encoded (assembler / C) data structures. But before I do that I need to know how efficient is / can be ...
9
votes
1answer
279 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 ...
9
votes
1answer
49 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 ...
8
votes
4answers
23k 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 ...
8
votes
2answers
1k views

Isn't Functional Programming just Imperative Programming in disguise?

A YouTube video I was watching explained the differences between Imperative and Functional programming by demonstrating how the numbers from 1 to ...
8
votes
2answers
572 views

What is the Curry-Howard analogue for linear logics?

As defined by Wikipedia, (The Curry-Howard correspondence) is a generalization of a syntactic analogy between systems of formal logic and computational calculi that was first discovered by the ...
8
votes
1answer
14k 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: ...
8
votes
3answers
374 views

ML functions from polymorphic lists to polymorphic lists

I'm learning programming in ML (OCaml), and earlier I asked about ML functions of type 'a -> 'b. Now I've been experimenting a bit with functions of type ...
8
votes
1answer
472 views

Simply Typed Combinatory Logic?

As there is an untyped lambda calculus, and a simply-typed lambda calculus (as described, for example, in Benjamin Pierce's book Types and Programming Languages), is there a simply-typed combinatory ...

1 2 3 4 5 6