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
10
votes
4answers
3k 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, ...
0
votes
0answers
37 views

Is there a static type system (implemented or not) that can detect ignored parameters and re-type them to increase generality?

I came across this question while playing with the SKI combinators. (Skip to the bottom for the question, if you don't care about the motivation.) You can implement the combinators in Haskell as ...
0
votes
0answers
21 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
1answer
30 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
2answers
80 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 ...
0
votes
0answers
28 views

Question about machine learning

Hello everyone I am new to the site, I have a question that was in the test and did not understand the parts that are in the question. This question from a test I failed to pass, in a machine learning ...
7
votes
1answer
109 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 ...
2
votes
1answer
107 views

How, if possible, can we efficiently compute with lazy data structures in 𝜆-calculus?

In Haskell, we can use the following code to define fibonacci numbers, fibs = 1 : 1 : zipWith (+) fibs (tail fibs) And its time complexity is linear. I cannot find ...
5
votes
2answers
67 views

Is there one (or a few) canonical/ specific use cases for "functions returning functions" (beyond "decorators")?

Is there one (or a few) canonical/ specific use cases for "functions returning functions" (beyond "decorators")? What can you do with "functions returning functions" ...
19
votes
11answers
5k 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. ...
3
votes
0answers
27 views

Monad with a partial inverse, but not a comonad

I have encountered a structure that looks like a monad with a one-sided inverse and some additional properties. I am not sure which properties of this structure are essential and which are accidental, ...
1
vote
1answer
38 views

Is it possible to allow passing arguments as references without breaking referential transparency in functional languages?

Referential transparency is a relatively new concept to me, but I understood that it means that a function will always give the same answer given the same arguments. Would passing arguments by ...
0
votes
1answer
41 views

Which overhead is smaller - function call or passing variables between processes?

the question is related to networking frameworks; callback-based approach requires you to call a callback function every time you receive a new data packet; this is not a good approach for high-load ...
0
votes
1answer
51 views

Is this way to combine two functions into a new function called a function product?

I have been looking for a maths operation that allows me to combine functions in a specific way. For example if we have functions f and g both with single mappings from o to e and v to c respectively, ...
1
vote
1answer
130 views

Difference between function, method, routine, procedure, subprogram, subroutine, block, task

I don't know if I should have posted this on StackOverflow or here but what's the difference between these terms? Are the definitions of these dependent on the programming languages or they're things ...
1
vote
0answers
42 views

Delayed "let" in SICP

In section 3.5.4 , i saw this block: ...
2
votes
3answers
224 views

Set theory pertaining to category theory and functional programming

I'm reading an unfinished Introduction to Category Theory/Products and Coproducts of Sets and have come across the following: A power set of a set is the set of all its subsets. A script 'P' is used ...
0
votes
0answers
26 views

What are advantages of "streaming" syntax in functional languages with for-yielding like Scala?

In Scala we can print list val nums = (1 to 10).toList with both ...
0
votes
1answer
31 views

Example on Referential transparency (wikipedia)

I have a rather foolish question on an example explaining the idea behind Referential transparency Here is given an example i not understand: Consider a function that returns the input from some ...
2
votes
0answers
33 views

Is there a functional programming language with inherent change propagation?

Change propagation in programming environments is an add-on at the framework level such as React. There was a lot of work on dataflow virtual machines in the wake of Backus's Turing Award Lecture on ...
3
votes
1answer
128 views

Is mutual inductive type definition essential in coq core language?

I'm studying Coq's core language and I found that mutual inductive type definition is in it. https://coq.inria.fr/refman/language/core/inductive.html#theory-of-inductive-definitions Before I read the ...
3
votes
2answers
102 views

Plain-language example of how a functional style makes parallel programming easier

I read a few "function >> imperative/OOP" articles because I heard there was a move in imperative OOP languages toward a functional style of coding, especially encouraging pure ...
0
votes
2answers
45 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 ...
0
votes
0answers
25 views

Is there a uniform way of giving for any mathematical formula a hypercomputer that computes it?

Some mathematical formulas directly suggest an algorithm for computing it (even if sometimes an inefficient one). For example, if we recursively define $\sum_{i=1}^nx_i=x_n+\sum_{i=1}^{n-1}x_i$, then ...
5
votes
2answers
232 views

Regarding Backus' Commentary on von Neumann-style Programming

in John Backus' 1978 FP paper "Can Programming Be Liberated from the von Neumann Style" he says To help assemble the overall result from single words [von Neumann ie. conventional mutation-...
2
votes
1answer
85 views

Meaning of Free (Arbitrary Abstract Algebra Term)

I'm currently learning abstract algebra and the word free appears (free monoid, free vector space) throughout different literatures. Is there a general (and simple) definition of the word (and ...
2
votes
1answer
86 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 ...
10
votes
1answer
1k views
1
vote
0answers
31 views

Should I use Dr. Racket for learning Scheme?

I've been fiddling with software development for a couple of years and in trying to get into the gist of things I came across SICP, which uses Scheme. Basically what I want to do at this stage is to ...
1
vote
0answers
37 views

Can a lambda expression be beta-equal to beta-normal forms?

Given a Lambda Expression Term T can it be beta-equal to two different Lambda Terms T1 and T2, both T1 and T2 are in beta-normal form?
2
votes
1answer
66 views

Computation equivalence of functional and procedural programming

I'm really interested in the idea of functional programming, it seems like a very modular way of doings things. I've seen some suggestion that functional programming is just as powerful as procedural ...
2
votes
1answer
99 views

Show that term cons works by showing all beta reductions

I'm new to functional programming. So the terms cons appends an element to the front of the list. Where cons ≜ λx:λl:λc:λn: c x (l c n). How should I go about proving that cons works correctly using ...
1
vote
0answers
108 views

Constraint based analysis: understanding the program $[[ \text{fn} \ x => [x]^1]^2 [ \text{fn} \ y => [y]^3]^4]^5$

I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter 1.4 Constraint Based Analysis says the following: 1.4 Constraint ...
2
votes
0answers
65 views

The word "algebra" in category theory

I am currently learning category theory and a saying that I see a lot is that X is the algebra of something (e.g. Monoid is an algebra of something). Can someone explain to me what that means? Thanks!
2
votes
1answer
85 views

Is well-founded recursion enough for practical total functional programming?

Total functional programming is a paradigm of non-Turing-complete programming languages where any program that type checks is proven to halt. Well-founded recursion is a recursive definition of a ...
3
votes
1answer
156 views

How to prove that the Church encoding, forall r. (F r -> r) -> r, gives an initial algebra of the functor F?

The well-known Church encoding of natural numbers can be generalized to use an arbitrary (covariant) functor F. The result is the type, call it ...
3
votes
1answer
138 views

Loop optimization of non-tail recursion

When researching how to optimize recursion into loops, I came upon (on Wikipedia) a general rule about this: Whenever a function is in form: ...
5
votes
2answers
223 views

What are the implications of Homotopy Type Theory?

I've recently come across the topic of homotopy type theory and I'm interested to learn more. I have a very limited background in type theory. Can anyone tell me, in functional programming terms or ...
6
votes
4answers
210 views

Is there difference between a function in mathematics to a function in computer science?

I never learned a lot of mathematics (generally only arithmetic) and never learned computer science in a formal frame. I emphasize that I don't mean to ask about a "function" in programming (...
5
votes
0answers
190 views

Normalization-by-evaluation for untyped lambda calculus which results in 𝛽𝜂-normal form

Usual NbE algorithms for untyped lambda calculus, which use (P)HOAS to embed terms to a host language constructs, results in a beta-normal form of a terms. Is there algorithms to (efficiently) exploit ...
0
votes
0answers
92 views

Can we think of a non-symmetric product type in Haskell?

Meta note: I asked this question here a while ago. It got an answer: type a /\!! b = (a, ((b -> Void) -> Void)) Unfortunately, I do not reckon it to be ...
1
vote
1answer
115 views

For every imperative function, is there a functional counterpart with identical performance or even instructions?

Currently, I haven't learned about a functional language that can achieve the same performance as C/C++. And I have learned that some languages that favor functional programming to imperative ...
1
vote
0answers
66 views

What is the category theory interpretation of higher order abstract syntax?

Suppose you have a simple sort of lambda calculus abstract syntax tree. The fine details don't really matter. ...
-1
votes
1answer
117 views

Repeating functions in functional programming?

Functional programming is said to be superior in many ways to imperitive programming. But I am struggling to find a simple functional way of writing: ...
1
vote
0answers
19 views

N-dimensional generalization of map and reduce?

Is there any conceptual generalization of higher-order functions like map and reduce but for N-dimensional objects (e.g. arrays or tensors)? For mapping, I guess it would be a point-wise ...
4
votes
3answers
153 views

Can lists be defined in a special way so that they contain things of different type?

In https://www.seas.harvard.edu/courses/cs152/2019sp/lectures/lec18-monads.pdf it is written that A type $\tau$ list is the type of lists with elements of type $\tau$ Why must a list contain ...
2
votes
1answer
159 views

Creating a large tuple from smaller tuples via a monad or applicative

Suppose I have a term $a :\alpha$ of the Simply-Typed Lambda Calculus (in the following, $\alpha, \beta, \gamma$ stand for arbitrary types) and I want to lift it to a term $\lambda x_{\beta}. \;(x, \, ...
3
votes
1answer
260 views

The meaning and relevance of the locution ''no terminating implementation'' in type theory

In the context of a discussion of Haskell https://stackoverflow.com/questions/62509788/the-intuition-behind-the-definition-of-the-co-reader-monad, I was told that There is no terminating ...
2
votes
2answers
110 views

Lambda Calculus Conversion

How can I take a Haskell data type or function (eg fold, list, String, zip) and convert or translate it to a lambda calculus abstraction? Example: If sum computes a sum of all elements in a list, and :...
2
votes
1answer
393 views

A monad is just a monoid in the category of endofunctors, what's the enlightenment?

Pardon the word play. I'm a little confused about the implication of the claim and hence the question. Background: I ventured into Category Theory to understand the theoretical underpinnings of ...

1
2 3 4 5
7