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.

395 questions
13
votes
1 answer

The "CPS" approach has done great harm to performance in SML/NJ; reasoning desired

In a comment to Learning F#: What books using other programming languages can be translated to F# to learn functional concepts? Makarius stated: Note that the "CPS" approach has done great harm to performance in SML/NJ. Its physical evaluation model…
Guy Coder
  • 5,231
  • 3
  • 31
  • 67
13
votes
3 answers

How does 'deforestation' remove 'trees' from a program?

I think understand how deforestation consumes and produces a list at the same time (from a fold and an unfold function -- see this good answer on CodeReview here ), but when I compared that with the wikipedia entry on the technique it talked about…
Cris Stringfellow
  • 425
  • 2
  • 11
12
votes
4 answers

Does immutability in functional programming really exist?

Although I work as a programmer in my daily life and use all the trendy languages (Python, Java, C, etc) I still have no clear view of what functional programming is. From what I've read, one property of functionally languages is that data…
Pithikos
  • 393
  • 3
  • 13
11
votes
1 answer

Alternatives to Defunctionalization

Defunctionalization is a transformation first described 1972 by John C. Reynolds to eliminate higher-order functions. Are there alternative transformations (more efficient?) to eliminate higher-order functions?
Peter
  • 361
  • 1
  • 5
11
votes
1 answer

Can properties such as memory usage of a function be expressed in a dependently typed language?

Suppose one wants to reason about properties of code beyond things like totality and functional purity - one also cares about the memory consumption, or algorithmic complexity of a function. Can this be done through dependent typing and effects…
Dr. John A Zoidberg
  • 263
  • 1
  • 5
11
votes
3 answers

Are the words "expression" and "term" interchangeable in programming language theory?

When describing the syntax of a given programming language the words "expression" and "term" are often used to seemingly describe the same things. Are these words interchangeable in the context of programming languages?
tibbe
  • 245
  • 2
  • 5
11
votes
4 answers

What are common formal techniques for proving functional code correct?

I want to provide proofs for parts of a Haskell program I'm writing as part of my thesis. So far however, I failed to find a good reference work. Graham Hutton's introductory book Programming in Haskell ( Google Books )—which I read while learning…
FK82
  • 273
  • 2
  • 8
11
votes
2 answers

Is there a paradigm for composing "incremental update" functions in a pure dataflow style?

I don't know the correct terminology for asking this question, so I'll describe it with lots of words instead, bear with me. Background , just so we're on the same page: Programs often contain caches - a time/memory tradeoff. A common programmer's…
Hallting
  • 113
  • 7
11
votes
1 answer

What is the difference between the Mogensen-Scott and the Boehm-Berarducci encoding for ADTs on the Lambda Calculus?

On the Lambda Calculus, there are several different ways to represent a list. For example, one can encode it as its right fold: list = (λ (cons nil) (cons 1 (cons 2 (cons 3 nil)))) One can, instead, use pair , false , fst and snd as aliases to cons…
MaiaVictor
  • 4,287
  • 2
  • 22
  • 35
11
votes
4 answers

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 arguments passed as dummy and not passed as dummy?…
Kyss Tao
  • 213
  • 1
  • 2
  • 5
11
votes
2 answers

Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration

I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations. Clojure provides persistent Vector, but it's only for fast append. Scala's Vector…
Tvaroh
  • 255
  • 2
  • 6
11
votes
1 answer

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 construction here, expressed in Haskell, is from…
SEC
  • 241
  • 1
  • 7
11
votes
1 answer

Constraint-based Type Inference with Algebraic Data

I am working on an expression based language of ML genealogy, so it naturally needs type inference >:) Now, I am trying to extend a constraint-based solution to the problem of inferring types, based on a simple implementation in EOPL (Friedman and…
justkris
  • 211
  • 1
  • 3
10
votes
3 answers

anonymous lambda functions (functional programming)

What are anonymous (lambda) functions? What is the formal definition of an anonymous function in a functional programming language? In my simple terms, when I am programming in scheme/lisp I would say an anonymous (lambda) function is a function…
CodeKingPlusPlus
  • 517
  • 1
  • 6
  • 14
10
votes
2 answers

λ -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 function representation in memory. The function can be…
Ford O.
  • 253
  • 1
  • 7
1 2
3
…
26 27