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
0 votes
1 answer
45 views

Is it possible for a language to have mixed evaluation strategies?

As far as I am aware, most functional programming languages today use a call-by-value eager evaluation strategy with some exceptions like Haskell. I am curious if it is possible for a language to have ...
2 votes
0 answers
98 views

What's the meaning of linguistics?

In the programming language theory world, there are two important terminologies, i.e syntax, and semantics. I can understand these two terminologies: syntax is about sentence's structure (e.g. a valid ...
0 votes
1 answer
46 views

What is lambda caculus's "fix point combinators" corresponding to Turing Machine?

The lambda caculus equals to Turing Machine,so What is lambda caculus's "fix point combinators" corresponding to Turing Machine? according to the paper <Primitive Rec, Ackerman's Function,...
0 votes
1 answer
113 views

Compiler optimization pass joining identical function definitions together (or specializing them)

Consider this program transformation, in any direction, written in ANF: ...
1 vote
1 answer
40 views

Literature on delta encoding serializeable ADTs

Suppose that I have some nested algebraic data type (ie. something one can construct via datas in Haskell) that is serializeable (so no functional fields ...
3 votes
1 answer
167 views

Is “x' = f(x)” a programming paradigm?

I'm the author of GateBoy (a gate-level simulation of the original Game Boy hardware) and Metron (a C++ to Verilog translation tool). One big issue I had to work around for both projects is the ...
0 votes
0 answers
19 views

What are the similarities and differences between dependent function application and ML functor application?

Advanced Topics in Types and Programming Languages gives this rule section 2.2 gives this rule for dependent function application: $$\frac{\Gamma \vdash t_1 : (\Pi x : S.T) \quad \Gamma \vdash t_2 : ...
7 votes
1 answer
669 views

Strictness in both arguments but not in each individually

I'm learning about strict functions in Haskell. A function f is strict if f ⊥ = ⊥ Some functions are strict only in the first argument (for e.g. const), others are strict in the second (for e.g. map)....
7 votes
1 answer
884 views

What exactly is the relation between Haskell and category theory?

In articles or Quora posts about category theory, I often find mentions of the programming language Haskell. I have little knowledge of category theory and even less of programming. Could someone ...
-1 votes
2 answers
132 views

Applying FP/Categorical terminology to non-FP languages

In my continuing effort to finally wrap my brain around advanced FP/categorical concepts, I've been reading dozens of articles and tutorials; what I have concluded is that: 1) Category Theory and ...
4 votes
2 answers
489 views

Functional Programming and Category Theory

I'm a math Ph.D. having done research in Algebraic Geometry and Algebraic Topology in grad school for my thesis and I've studied a fair amount of category theory in the process (e.g. having worked ...
137 votes
7 answers
39k 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 ...
4 votes
1 answer
60 views

Book references for combinatory logic as applied in Haskell?

I am looking for book references on combinatory logic. Is there a book focused on how combinatory logic is applied in the context of pure functional languages like Haskell? I found "Combinators: ...
1 vote
0 answers
46 views

Lambda calculus with unordered application

In lambda calculus, $\lambda xy.\phi$ isn't in general equivalent to $\lambda yx.\phi$. However, it seems possible to imagine a calculus which replaces application with something like specification, ...
1 vote
0 answers
45 views

Is there any formalization of GADTs implemented in OCaml?

There are papers that describe how generalized algebraic datatypes (GADTs) are encoded in core Haskell (System FC)[1][2], but I could not find any documentation on how OCaml formalizes/implements/...
0 votes
0 answers
31 views

Ambiguous type of "triangle" operator for sum types

In Meijer, Fokkinga and Patersons "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" the ∇ operator for sum types is introduced which removes the tags from its ...
0 votes
0 answers
33 views

Programming language implementation challenge: is recursion harder than HOFs, or vice versa?

(Initially this question was on cstheory, but I was told cs would be a better fit, so posting it here.) All other things being equal, which of the following languages would be more challenging to ...
1 vote
2 answers
890 views

Does it make sense to call GAP a "procedural" language?

GAP is a computer algebra system (CAS) that Wikipedia tells me is written in C, a procedural programming language. Does this mean we can say GAP's language is procedural? Or is this characterization a ...
3 votes
2 answers
123 views

Curry–Howard correspondence and functional programming "reliability"

The first time I heard about functional programming, someone told me "it's more reliable to code in a functional style because your type system is like a proof of correctness". I recently ...
7 votes
2 answers
485 views

Why are the laws of an applicative functor defined the way they are?

Let's recall the definition of an applicative functor. Throughout this question, I write $x: T$ to denote that the value $x$ has type $T$. Definition: An applicative functor consists of a type ...
2 votes
3 answers
386 views

Proving monad laws for flatMap and unit, given laws for compose and unit

I'll use scala notation but hopefully things will make sense in general (I'm trying to prove that you can define a monad using either [flatMap (aka bind) and unit] or [compose and unit]) The book ...
0 votes
0 answers
46 views

How to represent iso-recursive type operators?

I've just read Chap20 of "Types and Programming Language" by Benjamin C. Pierce, which describes the formal theory of recursive types. But it doesn't include type operators. I would like to ...
9 votes
2 answers
1k 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 ...
0 votes
1 answer
63 views

Does category theory only deal with immutable objects? If so, why?

IIUC, category theory only applies to immutable objects, and mutability is modelled within that using e.g. functors, monads. Is that true? If so, why doesn't category theory include immutability? Has ...
0 votes
1 answer
67 views

Are there any formal systems or programming languages in which its only possible to define functions that have inverses?

Consider an algorithm $f(x)$. Are there formal systems or programming languages that only allow $f(x)$ to be defined if $f^-1(x)$ exists?
8 votes
2 answers
144 views

Does the concept of "side-effect" predate functional programming?

When I was reviewing a book, I saw that there's a sentence claiming "side effect is a term coming from the domain of functional programming". I would think that the concept existed before ...
0 votes
0 answers
57 views

Question about complexity of two topics in programming language theory

I am a student who is currently finishing second year of university mathematics. This summer I have to choose a topic for my diploma. Because I am particularly interested in computer science I am ...
-1 votes
2 answers
131 views

Are pure functions always computable functions?

Are pure functions always computable functions? In computer programming, a Pure function is a function that has the following properties: (1) the function return values are identical for identical ...
1 vote
2 answers
55 views

Can a strict right fold be implemented in a single loop?

A strict left fold is straightforward to implement as a loop, rather than with recursion: ...
0 votes
0 answers
32 views

Exercise from Algebra of Programming on catamorphisms

This is an exercise from Algebra of Programming which I'm reading for self-study. Below, $T$ is the initial algebra of $F$. What I've tried: I can construct $h \circ F (\pi_2) : F(A \times B) \...
3 votes
1 answer
112 views

Is possible to have a "pointer" to a tree node in a functional language?

Suppose I have the following structure definition in C: struct node { int value; struct node *parent, *left, *right; } If I want to represent a specific ...
0 votes
0 answers
23 views

resources about programming language theory,topics: zipper and monads

I am in need of exercises and solutions about these topics in programming language theory with ocaml, zippers and monads, I can't find much on google, or I am missing something?
0 votes
0 answers
18 views

Does the identity between functions and data (in languages with first-class functions) have a name in CS?

Section §2.1.3 at page 90 of Structure and Interpretation of Computer Programs explains, with a very clear example, that first class functions in a language make functions themselves and data be the ...
0 votes
1 answer
19 views

How the indirect addressing works?

By other words, can anyone explain how indirect addressing works? I red MARIE's LoadI X over and over and still didnt understand the logic behind it. ...
1 vote
1 answer
137 views

Proving transitivity in an intuitionistic type theory without the K rule

In Agda, if I disable axiom $\mathbb{K}$ I'm not able to prove $$ \forall\{A : \textbf{Set}\}\{a\ b : A\}\{p\ q : a \equiv b\} \to p \equiv q, $$ which I guess is normal since the system does not ...
2 votes
2 answers
77 views

What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?

I know that retrieving an item in a collection can be done in $O(1)$ time(on average) using hash tables. I would like to know if there is an algorithm that could be as performance without using arrays....
2 votes
3 answers
68 views

To what extent is `this` state considered hidden-state - or its mutations a side-effect?

I was re-reviewing a somewhat upvoted answer of mine where I attempt to explain the differences between pure, impure, deterministic, non-deterministic, and idempotent functions. In my answer I use ....
2 votes
1 answer
263 views

Addition in Lambda calculus

Found this term for a supposed 'adder' in lambda calculus. λabcd.ac(bcd) Although I know about alpha-conversion and beta-reduction and all that stuff, I don't know ...
0 votes
1 answer
57 views

Continuation passing transform

I'm stuck on something in in Shan's article Shift to Control, about CPS. On page three he writes the CPS transform ...
2 votes
1 answer
183 views

Why use the Y combinator for recursion?

The Y combinator is defined as $$Y=\lambda f.(\lambda x. f (x x))(\lambda x. f (x x))$$ It has the following useful property: $$Y g = g (Y g)$$ for some expression $g$. It can be easily used to ...
2 votes
1 answer
40 views

What is the meaning of "You describe the result you want rather than specifying the steps required to get there." in Functional Programming?

One of the characteristics of functional programming is as follows: You’re describing the result you want rather than explicitly specifying the steps required to get there. I found this quote at ...
9 votes
1 answer
758 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 ...
6 votes
0 answers
105 views

Bounded existential polymorphism

In his "Types and Programming Languages", Pierce, at the very end, presents the most powerful system in the book: $F^{\omega}_{<:}$. He, however, does not explain how bounded existential ...
6 votes
1 answer
1k views

call by value: what is a value?

In the 'call by value' evaluation of lambda-calculus, I am bit confused with 'value'. On page 57 of the book Types and Programming languages, it is said: The definition of call by value, in which ...
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 ...
0 votes
2 answers
50 views

What is name of type " Function->Value->Bool = if (Bool) Function (Value) " in Category theory?

I am very new to functional programming so sorry if the question is stupid. Having this function ...
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, ...
1 vote
0 answers
62 views

Shallow Binding with static scope, is it possible?

I'm new in programming, I'm currently studying programming languages. I'm trying to implement Shallow Binding with static scope, starting from an abstract syntax (producing a programming language ...
0 votes
1 answer
37 views

Pure Directed Graph

How can a directed graph be efficiently represented in a purely functional language like Haskell? Could someone suggest relevant materials on this topic? (functional pearls perhaps?) Thanks.
2 votes
2 answers
111 views

Semantics and implementation of side effects

From a practical point of view, how do functional languages with formally specified semantics (like ML) handle side effects like printing? I'm aware of things like the IO monad in Haskell but I'm ...

1
2 3 4 5
8