6

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 - http://foldoc.org/applicative - but I'm not sure "applicative language == functional language" really helps.

Improve this question
4
  • 1
    There's a little more here: en.wikipedia.org/wiki/Applicative_programming_language. Haskell uses the word "applicative" in a specific way: en.wikibooks.org/wiki/Haskell/Applicative_Functors
    – Robert Harvey
    Feb 16, 2012 at 0:59
  • -1: What problem are you trying to solve?
    – Jim G.
    Feb 16, 2012 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, 2012 at 12:32
  • @Jim - One paper where I found this is www.lri.fr/~filliatr/ftp/publis/puf-wml07.ps (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.
    – user8709
    Feb 16, 2012 at 13:05

1 Answer 1

Reset to default
3

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.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.