Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know what an "applicative Functor" is, but I've been reading papers recently that refer to other "applicative" things, particularly "purely applicative data structures".

The trouble is, I'm not sure precisely what "applicative" means in this context, and Google has so far failed me. I can get a general English (ie useless) definition of "applicative", but as soon as I add "computer science" to the search all I get is definitions of computer science.

I have a vague sense that this relates to keeping them pesky effects in their place, but I could use a precise definition.

I found this - - but I'm not sure "applicative language == functional language" really helps.

share|improve this question
There's a little more here: Haskell uses the word "applicative" in a specific way: – Robert Harvey Feb 16 '12 at 0:59
-1: What problem are you trying to solve? – Jim G. Feb 16 '12 at 10:19
@JimG. clearly he is trying to understand papers that use this term, it says that in the first sentence. – jk. Feb 16 '12 at 12:32
@Jim - One paper where I found this is (A Persistent Union-Find Data Structure - Conchon, Filliatre). Although the use of the word didn't seem to be a barrier to understanding this or other papers, it was bugging me a little. – Steve314 Feb 16 '12 at 13:05
up vote 3 down vote accepted

The best general definition I can think of is "respects the principle of extensionality".

An applicative functor given equal structures produces equal structures. Contrast with a generative functor, which produces a "fresh" structure each time---that is, the equality of structures depends on "where" and/or "when" they were produced.

An applicative data structure is one where the information is represented by "how the data structure is put together", rather than external things like memory locations. This sense of "applicative" requires a certain perspective, common in programming language semantics, that separates "values" from "the store" (an abstraction of mutable memory). For algebraic data types, extensionality equates two values of the same type iff they were produced by the same constructor applied to the same arguments. The upshot is that mutation and "object identity" are forbidden.

There's also another usage: "applicative order of evaluation". I'm not sure that use is related to the others.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.