Purely functional data structure: Difference between revisions

Revision as of 20:33, 29 August 2019

Revision as of 14:15, 26 February 2020

Line 13:

==Ensuring that a data structure is purely functional==

A data structure is never inherently functional. For example, a stack can be implemented as a [[singly-linked list]]. This implementation is purely functional as long as the only operations on the stack return a new stack without altering the old stack. However, if the language is not purely functional, the run-time system may be unable to guarantee immutability. This is illustrated by Okasaki,{{r|Okasaki-book|pp=9-11}} where he shows the catenationconcatenation of two singly-linked list can still be done using an imperative setting.{{cn|date=December 2018}}

In order to ensure that a data structure is used in a purely functional way in an impure functional language, [[modular programming|modules]] or [[class (computer programming)|classes]] can be used to ensure manipulation via authorized functions only.{{cn|date=December 2018}}