Functional programming is a programming paradigm which primarily uses functions as means for building abstractions and expressing computations that comprise a computer program.

learn more… | top users | synonyms

1
vote
0answers
11 views

How to reduce this with all 4 of normal applicative by-name by-value?

Given mult = \x -> \y -> x*y I am trying to reduce (mult (1+2)) (2+3) with each of the strategies: normal-order ...
1
vote
0answers
17 views

Algorithm for the function “drop” in a binary random-access list

In the book Purely Functional Data Structures by Okasaki, exercise 9.1 asks: Write a function drop of type ...
12
votes
2answers
286 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 ...
5
votes
0answers
35 views

Bounded existential polymorphism

In Pierce's "Types and Programing Languages" he, at the very end, presents the most powerful system in the book: $F^{\omega}_{<:}$. He, however, does not explain how bounded existential ...
1
vote
2answers
60 views

Call‑by‑name will succeeds where call‑by‑value may fails: some example cases?

I've landed to SML pages, comparing call‑by‑name and call‑by‑value, asserting the former always succeed while the latter may fails. As this seems counter intuitive to me, I feel at least an example ...
2
votes
1answer
55 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 ...
1
vote
1answer
47 views

Haskell monad bind operator type

In Haskell, the Monads type class has the bind operator, which is represented by the symbol >>= The type of such operator is: ...
3
votes
1answer
22 views

Lower complexity bounds without mutation

Lower complexity bounds tend to be a very hard problem in general. Despite this, I was wondering if there are any theoretical results that relate lower complexity bounds for some class of problems in ...
0
votes
0answers
9 views

How to apply the unification algorithm to a racket function

In my programming languages course we are reviewing unification algorithm by hand. The TA can't solve some examples of how to apply the unification algorithm to the ...
4
votes
1answer
283 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 ...
2
votes
0answers
36 views

Defunctionalization and known arity function calls by pointer

Defunctionalization is nice for higher order functions where it is completely necessary to avoid runtime support, but in some cases it's favourable to use function pointers instead (since they don't ...
3
votes
0answers
85 views

Is there any programming system that enables reversible computations?

Better explained with examples, I need a programming system with the following characteristics: ...
1
vote
0answers
16 views

How does supercompilers relate to macro tree transducers?

Supercompilers can be used as a generalisation of deforestation of a functional program. Macro Tree Transducers composition can be used to the same effect, using a completely different approach. What ...
3
votes
1answer
61 views

Why are dependently typed languages such as Agda used for proofs, if supercompilers for simpler typed languages can do the same?

Proof assistants such as Agda can be used to assert properties about programs, such as the double of a number is even. Interestingly, supercompilers can be used for ...
7
votes
2answers
132 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 ...
3
votes
0answers
24 views

Is dependency analysis required in order to type a program?

I have seen stated in various places that in order to allow an "increase in polimorphism" functional depency analysis should be performed, and type inference should be used for every declaration group ...
-1
votes
2answers
88 views

Mathematical function vs Computer program

In mathematics , an $n$-ary relation is subset of cross product on $n$ sets took under consideration. Let us take $A_1,A_2,A_3 \cdots A_n$ be the n sets. Then relation $R \subseteq A_1\times ...
5
votes
1answer
40 views

What progress has been made on persistent catenable deques in the last decade?

I'm interested in persistent catenable deques: deques that can be concatenated. Kaplan and Tarjan came up with the first such data structure in 1995; Okasaki came up with a simpler, amortized version ...
11
votes
4answers
245 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 ...
1
vote
1answer
38 views

What is the evidence that that types are more basic specifications, and specifications are more detailed types?

In the book Type Theory and Functional Programming [Thompson, S 1999] the author explains the relationship between specifications, types and proofs of functions: The equivalent specifications can ...
2
votes
0answers
68 views

von neumann architecture and functional programming languages

Why functional programming languages do not use Von-Neumann architecture?Please explain elaborately.It'll be more helpful if you explain it diagrammatically. Thanks in advance. :)
3
votes
2answers
140 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 ...
3
votes
1answer
44 views

Can indirect recursion also be tail recursive? [closed]

Consider the following function definitions: ...
0
votes
0answers
15 views

Is there a fusion law for the mapreduce operation used on conc-lists?

Conc lists are similar to cons lists. In contrast to folds, mapreduce is the main "iterating" operation used on it. Composed mapreduces produce intermediate lists. Is there a fusion law for them, ...
4
votes
0answers
29 views

What are the properties of the unsided fold?

Foldl and folr are 2 very important functions for FP and Haskell, but I have never heard much about the unsided fold: fold f [a,b,c,d] = (f (f a b) (f c d)) That ...
2
votes
1answer
61 views

Is Equational Reasoning an application of Referential Transparency?

In various discussions of the merits of functional programming, the phrase referential transparency or equational reasoning is often listed. My question is - are these roughly the same thing? (One ...
5
votes
1answer
40 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 ...
3
votes
1answer
83 views

Non-termination of types in Martin-Löf's Type:Type?

In the pre-history of dependent type theory, Per Martin Löf introduced a calculus that is in some sense the simplest dependent type theory and the most general form of impredicative polymorphism. It ...
2
votes
1answer
145 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?
3
votes
2answers
169 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 ...
9
votes
1answer
301 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. ...
3
votes
1answer
53 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? ...
1
vote
2answers
66 views

Give a recursive function $r$ on $A$ that reverses a string

I really need help with this task here. Im stuck at it and I really would appreciate your help Here is the task: Give a recursive function $r$ on $A$ that reverses a string. For instance, ...
1
vote
1answer
111 views

Pros and cons of representing strings as lists of characters

I am writing a compiler for my programming language (both almost complete), but they are stuck in the, I would call, "String vs List-of-Char dilemma". Maybe some more experienced compiler programmer ...
1
vote
2answers
109 views

Is changing or appending data an idempotent operation?

As far as I know idempotent operation is a operation that can be applied many times with the same effect. Also I learnt recently that updating a tuple in a database is also idempotent. I thought that ...
2
votes
1answer
128 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 ...
10
votes
2answers
473 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 ...
5
votes
2answers
126 views

Reference request: Monads, continuations, and other functional CS concepts

I've been using Clojure for about 18 months. Recently, I've come across terms such as Monads, Continuations, et al which I'd like to learn about. I could visit Wikipedia and read about these two ...
10
votes
2answers
212 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 ...
3
votes
2answers
236 views

What type of formal notation is being used here to represent functional algorithms?

Interested in learning more about algorithm design in functional programming, I picked up Andrew Bird's Pearls of Functional Algorithm Design. I have experience with a number of programming ...
8
votes
1answer
182 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 ...
3
votes
1answer
71 views

ML - Type Interface

From my recitation class - Can you please explain why does operator $"+"$ signature is $ int \rightarrow (int \rightarrow int)$ ? How does this graph is build ? And what is mean $t=u ...
5
votes
3answers
300 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
4answers
744 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 ...
2
votes
1answer
40 views

How is the following ML Curry expression evaluated

This question is not homework but it's related to material in a general course I take about programming languages, so I don't know whats the site policy about this In ML the following expression: ...
11
votes
2answers
417 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 ...
10
votes
3answers
602 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 ...
8
votes
3answers
287 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 ...
5
votes
3answers
298 views

How can SML infer types like this?

Wikipedia says: fun factorial n = if n = 0 then 1 else n * factorial (n-1) A Standard ML compiler is required to infer the static type int -> int of ...
1
vote
3answers
108 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 ...