Tagged Questions

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

-2
votes
0answers
11 views

Is this a well-known Haskell idiom [migrated]

Is this a well-known idiom? applyTwice :: (a -> b -> c) -> (d -> a) -> (d -> b) -> (d -> c) applyTwice g f1 f2 p = g (f1 p) (f2 p) Here's a typical use: applyTwice someFunction head tail ...
1
vote
2answers
48 views

Is it possible to write an HTML compiler with no mutable state?

That's probably a vague question but allow me to try and give an example: My compiler does transformations on HTML (from HTML to HTML). It scans a flattened DOM tree, and relies on lookbehinds (on ...
0
votes
0answers
49 views

Logic and Functional programming

I have a subject Introduction to logic and functional programming but the course is not provided in detail. This is the provided course. Introduction to declarative programming paradigms. The ...
1
vote
0answers
19 views

How to get from factorial to a y-combinator?

In one of his conference talks Jim Weirich derives the applicative form of the y-combinator by refactoring a partial definition of factorial. The starting point in his talk is different than what ...
0
votes
0answers
28 views

Are if statements avoidable is we define a program according to explicit state transitions? [duplicate]

This question occurred to me some time ago when I was thinking about whether or not if statements are fundamental in computation. Consider a program that manages a ...
3
votes
1answer
76 views

How is IO a monad?

I am learning the Haskell programming language. From what I am reading, Input/Ouput (IO) raises challenges for Haskell's purity, since by definition we are interacting with the outside world. From ...
5
votes
2answers
64 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? ...
1
vote
0answers
16 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
20 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 ...
13
votes
2answers
304 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
40 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
70 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
68 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
2answers
69 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
15 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 ...
6
votes
2answers
484 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
92 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
75 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
136 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 ...
4
votes
1answer
32 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 polymorphism," functional dependency analysis should be performed, and type inference should be used for every declaration ...
-1
votes
2answers
105 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
44 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 ...
12
votes
4answers
260 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
84 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. :)
4
votes
2answers
194 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
50 views

Can indirect recursion also be tail recursive? [closed]

Consider the following function definitions: ...
0
votes
0answers
16 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
34 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
79 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
46 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
98 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
147 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?
4
votes
2answers
180 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
336 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
64 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
68 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
112 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
114 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
133 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
517 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
127 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
215 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
280 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
198 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
73 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 ...
7
votes
3answers
334 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 ...