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
vote
2answers
70 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 ...
1
vote
0answers
54 views

Is there a known way to make an efficient, compact, and fully persistent stack or queue?

In the world of mutable/ephemeral data structures and imperative programming languages, one of the classic ways to implement a stack or queue is to use array doubling: use mutation to fill up or empty ...
1
vote
2answers
64 views

Uncurrying and Polymorphism

How do we uncurry functions when they are polymorphic? For example, is it possible to uncurry the following types? If so what is the uncurried type? $\forall X. X \rightarrow int \rightarrow X$ ? $...
65
votes
4answers
11k 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 ...
0
votes
1answer
97 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 ...
2
votes
1answer
146 views

Organizing a “speedback”

Speedback is the merging of speed-dating with feedback: a 2 min. 1-on-1 talk with all members of a group of people. I'm in a team and I want to plan the ideal speedback setup: all team members have ...
3
votes
1answer
22 views

Pattern matching on function application

Suppose we have a function f :: a -> b and a function g :: b -> a such that f . g = id....
8
votes
4answers
25k views

What does “dummy argument” mean?

What is does it mean when an argument to a function is called a dummy argument? I have not encountered this term outside Fortran, is it a general term in computer science? What would be examples of ...
0
votes
1answer
31 views

What kind of Grammar could this be

I am trying to sort Grammar into the Chomsky Hierarchy and I can do so for most of my examples but I am stumped by the following one: bX -> abY which Type of ...
4
votes
2answers
84 views

Why is the second operation of a Monad called bind?

I understand how monadic computation works, I am just wondering where does the name come from. I cannot relate the thing that the bind operator actually does (i.e. ...
2
votes
0answers
30 views

Compiling an impure language into a pure stack-based language

For a personal learning and fun project, I build an abstract virtual machine based on a stack. The instructions are simple and act on the top of the stack only. There are also stack operators such as <...
2
votes
0answers
15 views

Reducing Kleene's predecessor for Church numerals

I am trying to "reinvent" Kleene's predecessor myself. The following code snippet should be self-explanatory. The idea is to make a 2-tuple and count up from zero, i.e. ...
0
votes
1answer
58 views

generic way to convert imperative if-then-else statements into functional style?

In this question, I asked about a reference for translating imperative code to functional code. I want to ask a more specific question here. How, in general, do we translate into functional style, a ...
0
votes
1answer
52 views

lambda calculus beta reductions: ((((lambda f (lambda x ((f x) f))) (lambda y (lambda g (g (* y y))))) 2) (lambda a a))

My question is in continuation to lambda calculus reduction: (((lambda f (lambda x (f x))) (lambda y (* y y))) 12) given the input: ...
6
votes
2answers
223 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 ...
-2
votes
1answer
69 views

Lambda Expression Reduction

I am unable to solve the following lambda expression using both normal order (Call-by-name) and applicative order (Call-by-value) reduction. I keep getting different answers for both. This is the ...
0
votes
0answers
20 views

What does this semantic specification do about shuffling a single card of a Deck?

I have 2 constructor functions and 2 additional function: declare: d,d' = deck; c, c' = card Constructor 1) CreateDeck(); ...
1
vote
2answers
67 views

resource on translating imperative programs to functional programs

I'm not asking this question for the purpose of any particular project. Rather, I'm trying to understand how to translate non-trivial programs in imperative style to functional style. By functional ...
3
votes
2answers
116 views

When is cumulative type universes useful?

AFAIK, a hierarchy of type universe(Type^0: Type^1: Type^2: ...) was introduced to avoid inconsistency caused by Type: Type. ...
0
votes
1answer
22 views

Converting a function with single parameter to a function with multiple parameters

I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows: Given a string or a list, do an aggregation operation on each of its elements. Here ...
0
votes
2answers
168 views

Does the callback concept of programming have any basis in computer science?

Although I seriously code with computer languages in general since 2010 and as an amateur programmer with programming languages in particular since 2015 (primarily Bash and JavaScript imperative ...
1
vote
0answers
39 views

Relationship between left identity and associativity

In an effort to better-grok monads I have reviewed many "Everything you need to know about Monads" tutorials out in the wild, but I feel like my understanding is still coming up a bit short. While ...
0
votes
2answers
32 views

If declarative programming is possible at the instruction/action level?

I am considering what the possibilities are with declarative programming. I have a firm understanding of how to use declarative programming in practice, but, short of having examples, I don't know if ...
1
vote
0answers
26 views

What is the maths name for a set which contains the Domain and Codomain of a function? [closed]

Im interested in this so that I can name a type parameter in a program I'm writing. There is function that that has three parameters. D, Domain C, Codomain X, where D is a subset of X and C is a ...
9
votes
1answer
114 views

Semantics for de Bruijn levels

There is an exceptionally simple way to embed simply typed lambda calculus with de Bruijn indices in a functional host language (discussed by Carette, Kiselyov & Shan, and by Kiselyov). The ...
1
vote
0answers
51 views

Predecessor function with recursive types

I am defining the type Nat of natural numbers a recursive sum type: $$ Nat = \mu X. Unit \oplus X$$ Now, I have defined zero ...
124
votes
7answers
31k 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 ...
3
votes
1answer
197 views

What type of function is main()?

As the functions are of 2 type:1.Pre-defined/library functions,2.User defined functions. What type of function is main() function? This doubt comes in my mind while writing a program we define the ...
2
votes
0answers
50 views

Simulating extensible sums with dependent types?

ML-style languages have a concept of "extensible" or "open" sum types, where variants can be declared at any point, and there's not a fixed number of constructors for the type. They're usually used to ...
5
votes
0answers
47 views

Rules for consistency with mutual inductive families?

I'm trying to use a proof assistant to define a type and a relation that are mutually dependent on each other: ...
0
votes
0answers
64 views

Is this proof of the map fusion law correct?

I am reading Functional Programming in Scala, where I have been asked to prove the map fusion law. Since Scala is what I am familiar with, I am using as my notation a kind of pseudo-Scala. Here is ...
2
votes
1answer
43 views

How does the function to curry and uncurrying another function work?

The following is the code to curry or uncurry a function in Haskell: ...
4
votes
1answer
326 views

Why does higher-order abstract syntax need an inverse to define catamorphisms?

In the introduction to the colorfully-named Boxes Go Bananas: Encoding Higher-Order Abstract Syntax with Parametric Polymorphism, Washburn and Weirich describe a problem in traditional formulations of ...
5
votes
1answer
292 views

How to write a coterminating, effectful program?

[Using Idris for code examples and terminology, but the question is not about Idris per se] In a post titled A Neighborhood of Infinity, @sigfpe argues that "the kind of open-ended loop we see in ...
0
votes
0answers
42 views

Evaluation of function

Is this the right approach to the question or am I off-track? Function: let rec collect f = function | [] -> [] | x::xs -> f x @ collect f xs;; Question: ...
2
votes
1answer
46 views

Can most programs (except the IO part) be re-written as a sequence of matrix operations?

I got this idea recently. If we do not consider the data IO part of software, imagine the data is in the memory and we need to come out with some decision (which product to recommend to a user, how to ...
0
votes
0answers
39 views

What is the point-free version of f(x,y)?

What is the point-free version of f(x, y) ? Is it just f or some kind of function composition, since when curried there is an implicit function which is made ...
2
votes
2answers
50 views

Using function composition to turn a function into point free one

In Tacit Programming page on wikipedia, it is stated that the point free version of p x y z = f (g x y) z is p = ((.) f) . g ...
2
votes
0answers
56 views

Integer-array indexing (e.g. numpy.take) as function composition: where can I find more resources?

For context, one of Numpy's features is that an an array of integers can be passed as an index to an array, and this selects values at all of the specified positions, in any order with possible ...
19
votes
1answer
819 views

Why hasn't functional programming researched dynamic trees?

Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging ...
0
votes
1answer
30 views

What is the relation between the formal definition of strictness and its intuitive notion

I am currently reading Functional Programming in Scala and have encountered a statement in the book I cannot quite make sense of. On page 67, we are told the formal definition of strictness: "If the ...
2
votes
1answer
70 views

Like transitive reduction, but removing vertices rather than edges?

Suppose I have a directed graph $G = (V, E)$ (or, which is the same, a relation on the set $V$ as defined by the adjacency matrix) that may contain three vertices $x, y, z$, such that $xy, xz, yz \in ...
1
vote
2answers
97 views

Can we always transform a set of lines to a function?

If I have n lines in a programming language like Python (globally or inside a function): ...
0
votes
1answer
88 views

Composition of compostion as a functor

"Composition of Composition" (i.e., (.) . (.)) in Haskell), has type ...
7
votes
2answers
644 views

In the Curry-Howard isomorphism as applied to Hindley-Milner types, what proposition corresponds to a -> [a]?

(Using Haskell syntax, since the question is inspired by Haskell, but it applies to general Hindley-Milner polymorphic type systems, such as SML or Elm). If I have a type signature ...
4
votes
4answers
11k views

What are differences between Static Scope and Dynamic Scope?

My teacher has provided the following pseudo-code, and says that the output using static scope is 1 2 3, but the output using dynamic scope is ...
8
votes
1answer
507 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 ...
2
votes
1answer
57 views

Formally proving properties of fold function

Recall the fold function for lists: $fold(f,z,[x,xs]) = fold(f,f(z,x),xs)$ $fold(f,z,[]) = z$ I want to formally proof that if $f$ is associative, commutative and idempotent (meaning $f(x,y) = f(x,...
4
votes
1answer
444 views

Prove foldl fusion law

I have proven the foldr Fusion Law as follows: Given f is strict, f a = b and ...

1
2 3 4 5
7