Talk:Purely functional

Name convention breaking

Since the title of this page is an adjective rather than a noun, it violates Wikipedia: Naming conventions. Of course, this may be justified in this case, but if it is I think we should be explicit about it here before someone decides to proactively move it. Deco 21:13, 15 July 2005 (UTC)

The article actually spends most of its time discussing purely functional data structures. I vote we rename the page accordingly. Neilc 09:05, 2 December 2005 (UTC)

I agree, if the unrelated material is moved out to somewhere suitable. Deco 23:20, 3 December 2005 (UTC)

Red Black Tree

Okasaki doesn't give the routine for deletion of Red-Black Trees. Since this encyclopedia article is basically a selection from his book and you mention that one specifically I think we should do the deletion case. Anyone else agree? — Preceding unsigned comment added by Jbolden1517 (talk • contribs) 2006-04-27T05:33:02 (UTC)

lazyness

I think lazyness and data structures deserves more explanation. Its one of the areas where functional languages differ and thus efficiency computations give different results. — Preceding unsigned comment added by Jbolden1517 (talk • contribs) 2006-04-27T05:33:02 (UTC)

Better example than thesaurus?

It's artificial, the simpler solution is to keep one common thesaurus and one private for each user and search in both than to impose additional requirements on the data structure.

--78.0.85.5 02:55, 12 September 2007 (UTC)

User:Brianski added XML comments to the article body. They should be discussed here on talk. LotLE×talk 23:36, 31 December 2007 (UTC)

(context) For example, a thesaurus service on a website uses a red-black tree to store its list of which words are synonyms for which other words; because the thesaurus is comprehensive, this tree has a large number of nodes. Consider adding a feature that allows each user to add their own custom words to their personal thesaurus. One way to do this is to make a copy of the tree for each user, and then add their custom words to it; however, this is wasteful duplication. Moreover, it would cause a significant processing delay to make the complete copy of the tree.

(Brianski) this is a bad example - the same problem could be solved by checking one thesaurus, then the other, and returning their union. no programmer, sane or not, would make a copy for each user presented this problem

The thesaurus/dictionary problem isn't very good. Some ideas for better examples: (1) A 3D game world where users can make their own private customisations. Because 3D scenes are very complex and large, and you can't solve this with the "two worlds" (private + shared) as you can in the dictionary case, a purely functional data structure would make more sense. (2) A filesystem like this: http://okmij.org/ftp/papers/zfs-talk.pdf (3) A way to implement an XML document editor where you allow infinite undo steps. Each undo step is essentially a shared copy of the document tree with private changes. Richard W.M. Jones (talk) 11:50, 1 January 2008 (UTC)

I've always assumed a standard pocket calculator (with the option of a battery of predefined expressions) is the way to think about this. You can do loops with recursion by way of decrementing an input parameter with each call, but in general the process is strained. This kind of programming is best limited to straightforward tasks such as calculation. No one ever said a programming "paradigm" must be all powerful or a thing unto itself. Not to mention that sometimes constraint can be a force for good. — Preceding unsigned comment added by 184.21.215.174 (talk) 12:22, 5 June 2013 (UTC)

SML program doesn't compile

Somebody please post the definition of "T" in the code snippet below:

fun insert (x, E) = T (E, x, E)
  | insert (x, s as T (a, y, b)) =
       if x < y then T (insert (x, a), y, b)
       else if x > y then T (a, y, insert (x, b))
       else s

—Preceding unsigned comment added by 71.72.235.91 (talk) 08:21, 24 December 2008 (UTC)

Not only that, but, I think that "else s" should be "else x". Shouldn't it? What language is this, anyway? Haskell?130.63.92.162 (talk) 17:49, 22 April 2010 (UTC)

Can't be Haskell; it doesn't require fun prefixes like that. --Gwern (contribs) 18:39 22 April 2010 (GMT)

Scope

This article should be deleted or heavily reworded based on the following premises: (1) Programmers create novel solutions to problems all the time; this does not make every workable idiosyncrasy eligible to be promoted as a new paradigm, unless it is extremely novel and widely applicable. (2) The actual use of a data structure that can only be modified by duplication and reference is 'extremely" limited in practice. Even in the thesaurus example, what happens if the website updates the master red-black tree? It potentially invalidates every functional reference of the master tree. Thus, all functional references would have to be rebuilt. You might try and argue that modifying the original tree also updates the user's trees, but this is not true, as the referenced trees duplicate some entries in order to maintain the structure of the new tree. There is no way around the fact that this paradigm requires the master tree to be immutable. (3) This example should be merged into a larger concept involving many themes related to the same concept; which is the trade off between memory and processing time--an age old problem. (4) Any programming system that takes input is inherently not a purely functional language. By taking input from the user over the internet, the programming system has read from I/O, which is a side effect; an imperative concept. The example fails to illustrate this point and inaccurately gives an impression of the validity and value of this immutable concept of a static data-structure. In other words, the thesaurus example is not a purely functional one, as the user generated versions of the master red-black tree are not immutable themselves. Which leads to the 5th point. (5) This is a process and not a data structure, yet it is presenting examples of data structures that are purely functional and also giving an example of a purely functional process. This article needs to decide which it is: a treatise on purely functional data structures (which is an misnomer, because data is not functional, logic is), or if it is a treatise on pure functions--which is already covered. --98.208.209.78 (talk) 20:57, 1 February 2009 (UTC)

Then how do you explain the purely functional concept of I/O monads? Diego (talk) 16:19, 4 February 2009 (UTC)

I/O is not purely functional that's why it is in a monad and not the main language. jbolden1517^Talk 12:29, 6 June 2009 (UTC)

Monads are a part of the main language in Haskell, they are purely functional, and they handle input/output thanks to the pure concept of a State. So no, I don't think I/O is an inherently imperative concept. You say "By taking input from the user over the internet, the programming system has read from I/O, which is a side effect", but in Haskell it is not a side effect, it's a function evaluation. Diego (talk) 15:30, 6 June 2009 (UTC)

The idea of the I/O monad came from Imperative Functional Programming by Wadler. Yes they are imperative and no they are not purely functional. For a more modern treatment, specific to Haskell Handling the awkward squad , "We begin with an apparently fundamental conflict. A purely functional program implements a function; it has no side effect.... Well, if the side effect can’t be in the functional program, it will have to be outside it." jbolden1517^Talk 15:43, 6 June 2009 (UTC)

This is partially a confusion of concepts. Monads are not "imperative"; they are purely functional constructs, which you can easily see by desugaring them to regular, run-of-the-mill Haskell functions. The implementation of the IO monad by Haskell, when being evaluated, does perform I/O, which is of course a side-effect. This is completely unrelated to its being a monad (which, again, is a purely functional concept), but is instead related to the implementation of this particular monad, the IO monad. 200.0.230.235 (talk) 17:49, 30 September 2014 (UTC)

I totally agree. The Red-Black tree example is bad for a number of reasons, another of which is that Red-Black Trees are defined as such because of the algorithm they use to remain balanced through changes, but the tree is defined as immutable, so it cannot change. The proper term should be 'balanced binary tree', and it should be explicitly explained what the purely functional approach does that is different, its too vague. —Preceding unsigned comment added by 70.57.74.3 (talk) 02:14, 11 June 2009 (UTC)

Deletion of this article

I strongly suggest that this article is removed. "Purely functional" is not a term of computer science as this article says, it doesn't mean anything indeed. I think the authors of this article are confused with the common term "Purely functional programming language" and the not so common or accepted "Purely functional data structures". Making an article called "purely functional" puts the two terms at the same level when the first one is really much more important. I'm not familiar with wikipedia so maybe someone who knows how this works and agrees with me can make the formal request for deletion. —Preceding unsigned comment added by 190.139.62.23 (talk) 07:03, 5 June 2009 (UTC)
I'll further discourage simply changing the name of this article to "Purely functional data structures", as this is the name of a book, and not the name of a class of structures as this article suggest. You can search the data structures named in the article as "examples" and you'll see that none of them are listed as a "functional data structure", the only thing that relates them to functional languages is that the later use them, but the same can be said about imperative (ie. not functional) languages. I really don't see any part worth saving of this article. — Preceding unsigned comment added by 190.139.62.23 (talk) 2009-06-05T07:27:50‎

Not knowing this subject that well, I am still inclined to agree with deletion if such is the case. What I do know, however, is that the introduction fails to explain what the subject is all about in simple terms any reader can understand. It is no good to include an encyclopedic article if it cannot satisfy the needs of anyone who uses an encyclopedia to gather knowledge on unfamiliar subjects. - KitchM (talk) 22:52, 3 March 2010 (UTC)

'Purely functional' is in widespread usage among the Haskellers, whom one would think would know what the term means. --Gwern (contribs) 23:56 3 March 2010 (GMT)

I am also no expert, just a programmer with an interest in functional programming. I agree that the article should be deleted since there is no such thing as "purely functional". The content is ostensibly about "purely functional data structures" but very little information is given about these. Bcaulf (talk) 01:12, 15 July 2013 (UTC)

tree diagram

Just as a point, the tree diagram is wrong the f in blue should be an f' not f. jbolden1517^Talk 12:21, 6 Jun

It is. The prime symbol is just difficult to see in the font that Wikipedia uses to rasterize the SVG. — Xaonon (Talk) 20:17, 10 August 2009 (UTC)

Move data structures part of page to Persistent data structure

I propose moving the discussion of purely functional data structures to Persistent data structure, since purely functional data structures are persistent data structures. The current data structure explanation is confusingly fragmented between the two pages, and I think it would be much clearer in one place. The Purely functional page would remain, but without over-weighting the data structure content. This structure would avoid the previous objections to entirely merging Purely Functional into Persistent Data Structures. Thoughts? Billgordon1099 (talk) 02:17, 5 April 2011 (UTC)

Core definition is wrong

The article starts with the sentence that Purely Functional is a term in computing used to describe algorithms, data structures, or programming languages that exclude destructive modifications (updates) of entities in the program's running environment. It then justifies this claim by referencing the Haskell language. However, Haskell *can* do 'destructive' updates. It simply guarantees that all functions will be referentially transparent (and therefore side effect free), not that they won't perform destructive updates. An example of this is the ST Monad which can (among many things) be used to operate on a mutable array. Therefore, I suggest the definition of "Purely Functional" be changed to "Purely Functional is a term in computing used to describe algorithms, data structures, or programming languages that guarantee referential transparency, often by excluding destructive modifications (updates) of entities in the program's running environment". — Preceding unsigned comment added by 98.189.26.19 (talk) 02:40, 15 October 2013 (UTC)

PRESERVE

An old version of the article was deleted and substituted by a Disambiguation page with this edit. Diego (talk) 11:42, 2 August 2016 (UTC)

A longer version can be found here, including examples that have been since moved to Persistent data structure. Diego (talk) 11:50, 2 August 2016 (UTC)