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
3 votes
1 answer
60 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 ...
user avatar
  • 131
0 votes
0 answers
20 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?
user avatar
7 votes
1 answer
611 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 ...
user avatar
0 votes
0 answers
17 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 ...
user avatar
  • 73
0 votes
1 answer
15 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. ...
user avatar
1 vote
1 answer
109 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 ...
user avatar
2 votes
2 answers
66 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....
user avatar
  • 235
2 votes
3 answers
54 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 ....
user avatar
  • 421
2 votes
1 answer
85 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 ...
user avatar
  • 21
0 votes
1 answer
39 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 ...
user avatar
  • 115
2 votes
1 answer
83 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 ...
user avatar
  • 55
0 votes
0 answers
17 views

Exemples of nested coinductive data types

Nested inductive data types have many exemples, for instance perfect trees, or lambda terms with variables ...
user avatar
  • 315
2 votes
1 answer
36 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 ...
user avatar
  • 121
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, ...
user avatar
  • 119
0 votes
0 answers
42 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 ...
user avatar
  • 1
0 votes
0 answers
30 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 ...
user avatar
0 votes
1 answer
33 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.
user avatar
2 votes
2 answers
89 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 ...
user avatar
0 votes
0 answers
34 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 ...
user avatar
  • 29
7 votes
1 answer
115 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 ...
user avatar
3 votes
1 answer
117 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 ...
user avatar
  • 63
5 votes
2 answers
70 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" ...
user avatar
19 votes
11 answers
6k 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. ...
user avatar
3 votes
0 answers
30 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, ...
user avatar
1 vote
1 answer
39 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 ...
user avatar
  • 262
0 votes
1 answer
43 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 ...
user avatar
  • 111
0 votes
1 answer
65 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, ...
user avatar
  • 143
1 vote
1 answer
329 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 ...
user avatar
  • 377
1 vote
0 answers
46 views

Delayed "let" in SICP

In section 3.5.4 , i saw this block: ...
user avatar
2 votes
3 answers
239 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 ...
user avatar
  • 121
0 votes
0 answers
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 ...
user avatar
  • 117
0 votes
1 answer
32 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 ...
user avatar
2 votes
0 answers
36 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 ...
user avatar
3 votes
1 answer
145 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 ...
user avatar
  • 133
3 votes
2 answers
113 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 ...
user avatar
0 votes
2 answers
48 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 ...
user avatar
5 votes
2 answers
252 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-...
user avatar
2 votes
1 answer
87 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 ...
user avatar
3 votes
1 answer
99 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 ...
user avatar
  • 131
10 votes
1 answer
1k views

What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?

On an imperative programming language, let us consider the following program: ...
user avatar
  • 123
1 vote
0 answers
36 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 ...
user avatar
1 vote
0 answers
38 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?
user avatar
2 votes
1 answer
71 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 ...
user avatar
2 votes
1 answer
130 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 ...
user avatar
1 vote
0 answers
110 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 ...
user avatar
2 votes
0 answers
68 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!
user avatar
2 votes
1 answer
113 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 ...
user avatar
  • 3,474
4 votes
1 answer
213 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 ...
user avatar
  • 143
3 votes
1 answer
153 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: ...
user avatar
5 votes
2 answers
286 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 ...
user avatar

1
2 3 4 5
8