Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In an answer to this question (written by Pete) there are some considerations about OOP versus FP. In particular, it is suggested that FP languages are not very suitable for modelling (persistent) objects that have an identity and a mutable state.

I was wondering if this is true or, in other words, how one would model objects in a functional programming language. From my basic knowledge of Haskell I thought that one could use monads in some way, but I really do not know enough on this topic to come up with a clear answer.

So, how are entities with an identity and a mutable persistent state normally modelled in a functional language?

EDIT

Here are some further details to clarify what I have in mind. Take a typical Java application in which I can (1) read a record from a database table into a Java object, (2) modify the object in different ways, (3) save the modified object to the database.

How would this be implemented e.g. in Haskell? I would initially read the record into a record value (defined by a data definition), perform different transformations by applying functions to this initial value (each intermediate value is a new, modified copy of the original record) and then write the final record value to the database.

Is this all there is to it? How can I ensure that at each moment in time only one copy of the record is valid / accessible? One does not want to have different immutable values representing different snapshots of the same object to be accessible at the same time.

share|improve this question
    
Depends on a language. Rich Hickey, the author of Clojure recommends that you use data structures (lists, dictionaries, sets, etc.) to represent your data. I am not completely sold on the idea; I like to de-reference fields by their name rather than index or mnemonic and have the compiler check that I did not screw up. F# has structures, which are like classes. msdn.microsoft.com/en-us/library/dd233233.aspx Even using Java or C#, you can have immutable objects that can "change" by creating a whole new object. –  Job Aug 13 '12 at 17:37
add comment

4 Answers 4

up vote 6 down vote accepted

The usual way to go about state changes in a pure language like Haskell is to model them as functions that take the old state and return a modified version. Even for complex objects, this is efficient because of Haskell's lazy evaluation strategy - even though you are syntactically creating a new object, it is not copied in its entirety; each field is evaluated only when it is needed.

If you have more than a few local state changes, things can become clumsy, which is where monads come in. The monad paradigm can be used to encapsulate a state and its changes; the textbook example is the State monad that comes with a standard Haskell install. Note, however, that a monad is nothing special: it's just a data type that exposes two methods (>>= and return), and meets a few expectations (the 'monad laws'). Under the hood, the State monad does exactly the same: take the old state and return a modified state; only the syntax is nicer.

share|improve this answer
    
I think laziness is the wrong word, It's efficient because Haskell can share unmodified subcomponents of the state. This can happen in any language which puts mutability at the type level. –  jozefg Nov 29 '13 at 8:01
add comment

I'll take that you are talking about the stateless characteristic of pure functional language.

You take the initial state as an input, you return the final state as an output. Nothing fundamentally different from what you do in a language with a notion of state, excepted that you are more explicit about it and that can be tedious and less efficient(*).

Note that you don't necessarily have to modify all places which reference your object: they may hold a token and then you just have to modify the data structure which map the tokens to their current state. By then you are implementing a state-full system using a stateless language and you get back the issues of state-full languages.


(*) For instance I've looked for -- and not found -- the data structure which allow me to return in O(1) a modified copy of a data structure indexable by consecutive integers in O(1) as well.

share|improve this answer
    
+1. Yes I was referring to modelling a stateful entity like an object (which has an identity and a history of subsequent states) in a stateless language. What would be the counterpart of your example (marked with (*)) in a language like Java? An array? An array of objects? –  Giorgio Aug 14 '12 at 11:57
    
@Giorgio, yes. I know how to do this in O(log n), but not O(1) -- and then the constant factor is also an hit. Note that I've used data structures designed for pure functional language as a way to implement undo in state-full languages. –  AProgrammer Aug 14 '12 at 12:05
    
Incidentally, a trie is technically O(1) under the same simplifying assumptions often used when discussing such things, being a variable-size collection with insert/delete operations whose time complexity does not depend on the number of elements present. They're not really comparable to a mutable array, though. –  C. A. McCann Sep 6 '12 at 20:57
    
A normal association list [(Int, v)] will let you replace the value at any index in constant time by simply consing the new value. Downsides: the old value is still taking RAM and search is linear. –  singpolyma Nov 25 '12 at 2:44
add comment

In short, each state of an entity is its own entity. So in your classic "ordering" business logic, there's an Order entity, and an OrderVersion entity. Both are immutable. Logic that adds a line item takes the old version and a new OrderLineItemVersion as an input and returns a new OrderVersion entity.

It makes some things easier (particularly "undo" functionality), but some stuff is more difficult.

share|improve this answer
add comment

I'm not a functional language developer, so please shoot me down in flames if I have this wrong, but if right, it might be an interesting analogy.

I was once told that Excel is essentially a functional language. I'm not talking about VBA and so on, I'm talking about what happens on sheet.

So you have inputs, which may be tabular, individual cells or named ranges, and so on, and through a chain of operations you end up with a result, or many results. Change one input and it immediately flows through.

Does that analogy hold water?

share|improve this answer
1  
By argument from authority, you are correct ;) –  phant0m Aug 13 '12 at 21:16
    
I believe using Excel like that is more akin to dataflow programming, but there's some leeway in where Excel might fit. Personally, I'm not sure I'd call it a language in the first place... –  Izkata Aug 13 '12 at 21:33
1  
You have a point there. But still, Excel is functional in that regard. P.S: I recommend you take a look at the presentation, I think it's quite interesting. –  phant0m Aug 13 '12 at 21:40
add comment

Your Answer

 
discard

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.