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

Proving a function of asymptotic Notation

I need help with this question. If it’s possible to do this without limits, please show. Thanks. Q: If f(n) is Ω(n) and g(n) is O(n), then prove or disprove the following statement: f(n) is O(n)
anaya's user avatar
  • 1
1 vote
1 answer
46 views

Understanding how lazy functional languages achieve IO (...sometimes?)

An Alternative view of I/O programs, popular in earlier lazy functional programming languages, was to see the input and output as Strings, that is as lists of characters. Under that model an I/O ...
tryst with freedom's user avatar
0 votes
1 answer
51 views

Free variable in the programming language

From the wikipedia of Free variables and bound variables In computer programming, the term free variable refers to variables used in a function that are neither local variables nor parameters of that ...
tbhaxor's user avatar
  • 208
0 votes
1 answer
30 views

What are the non-overlapping properties of a function?

Specifically, properties that identify preconditions over which a function can be used without resulting in undefined behavior or data races. For example, I am familiar with 3 important properties: ...
Jorge Leitao's user avatar
2 votes
1 answer
42 views

Is there any reference materials on complexity analysis for lazy languages?

Is there any books, papers or articles on how to analyze the time complexity of programs written in lazy languages such as Haskell? I know how laziness is implemented and how it can be expanded and ...
Kagura Hitoha's user avatar
1 vote
2 answers
65 views

(how) is assignment or binding possible in purely functional languages?

i can't seem to find much info on the following question: how (if at all) is the fixing of names to values (by binding or assignment) possible in a purely functional system like the lambda calculus? i'...
elsewho's user avatar
  • 11
0 votes
0 answers
62 views

Representation of pairs in System F

System F defines the data type pair as: $$X\times Y := \Pi Z. (X\to Y \to Z)\to Z$$ with: $$\langle x,y \rangle := \Lambda Z. \lambda p^{X\to Y\to Z}.p \text{ }x\text{ } y$$ Projections are defined: $$...
Antonio Hernando's user avatar
0 votes
1 answer
34 views

time complexity of loops

what is the time complexity of: for (i = 1; i <= n; i = 2*i) for (j = 0; j < i; j++) sum++; ? I thought it is O(nlogn) since the otter loop ...
user163594's user avatar
-1 votes
1 answer
156 views

Call by value is known as pure function how ?give reason

I think call by value may be pure function or impure function... And pure function can be written through call by value or call by reference.... So according to the facts (c) should be correct ans......
Trivedi's user avatar
0 votes
0 answers
17 views

Would it be fair to describing a parser generator as a functional language?

I'm playing around with the implementation of PEGs and it struct me that the parser generator itself isn't any different than the language it's use to construct. If fact, it has all of the hallmarks ...
guidoism's user avatar
  • 131
0 votes
0 answers
25 views

Are these two implementations of Bag different monads?

I am not an expert with functional programming. What I know is that the bag data structure satisfies the definition of a monad. There are two different implementations of Bag: one with linked lists, ...
user442920's user avatar
3 votes
1 answer
49 views

What is the object translating part of a monadic endofunctor?

A monad is an endofunctor $T:C\rightarrow C$ with natural transformations $\eta:id_C\rightarrow T$ and $\mu:T^2\rightarrow T$. Being natural transformations mean that $$T(f)\circ \eta_A = \eta_B\circ ...
Gergely's user avatar
  • 379
3 votes
2 answers
148 views

Does this esoteric representation of integers have decidable equality?

Consider the following datatypes in Haskell: data Foo = Halt | Iter Foo newtype BigInt = BigInt {nthBit :: Foo -> Bool} Foo ...
Dannyu NDos's user avatar
2 votes
2 answers
108 views

Translation between unit/bind and map/join in monads

Is there a translation between unit/bind and fmap/join in monads? https://stackoverflow.com/questions/34398239/with-monads-can-join-be-defined-in-terms-of-bind gives a partial one: bind f m = join (...
Gergely's user avatar
  • 379
0 votes
1 answer
66 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 ...
wildcat's user avatar
0 votes
1 answer
68 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,...
wang kai's user avatar
  • 121
0 votes
1 answer
125 views

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

Consider this program transformation, in any direction, written in ANF: ...
paulotorrens's user avatar
1 vote
1 answer
45 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 ...
LeonidR's user avatar
  • 41
0 votes
0 answers
22 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 : ...
Max Heiber's user avatar
8 votes
1 answer
694 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)....
Marta's user avatar
  • 83
4 votes
1 answer
88 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: ...
tryst with freedom's user avatar
2 votes
0 answers
57 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, ...
SEC's user avatar
  • 241
2 votes
1 answer
63 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/...
Apoorv's user avatar
  • 659
0 votes
0 answers
37 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 ...
pgmcr's user avatar
  • 36
0 votes
0 answers
37 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 ...
Hank Igoe's user avatar
  • 179
1 vote
2 answers
897 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 ...
healynr's user avatar
  • 113
3 votes
1 answer
234 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 ...
tanjent's user avatar
  • 66
0 votes
1 answer
77 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 ...
joel's user avatar
  • 103
0 votes
1 answer
73 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?
newlogic's user avatar
  • 165
0 votes
0 answers
59 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 ...
Hinko Pih Pih's user avatar
-1 votes
2 answers
156 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 ...
polcott's user avatar
  • 87
1 vote
2 answers
68 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: ...
Xophmeister's user avatar
3 votes
1 answer
146 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 ...
matteo_c's user avatar
  • 133
7 votes
1 answer
1k 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 ...
tryst with freedom's user avatar
0 votes
1 answer
26 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. ...
damacaner's user avatar
1 vote
1 answer
151 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 ...
A confused dove's user avatar
2 votes
2 answers
80 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....
pedroth's user avatar
  • 235
2 votes
3 answers
90 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 ....
Dai's user avatar
  • 421
2 votes
1 answer
580 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 ...
SNEED's user avatar
  • 21
0 votes
1 answer
111 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 ...
Eric Auld's user avatar
  • 115
3 votes
1 answer
311 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 ...
Natrium's user avatar
  • 75
2 votes
1 answer
41 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 ...
mnj's 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, ...
swr52's user avatar
  • 119
1 vote
0 answers
81 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 ...
Alexander Pisanoff's user avatar
0 votes
1 answer
39 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.
thoughtpolice's user avatar
3 votes
2 answers
128 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 ...
thoughtpolice's user avatar
0 votes
0 answers
41 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 ...
hah's user avatar
  • 29
8 votes
2 answers
156 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 ...
kolistivra's user avatar
3 votes
2 answers
153 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 ...
Lin Jin's user avatar
  • 63
5 votes
2 answers
87 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" ...
Serge Hulne's user avatar

1
2 3 4 5
8