Managing invariants in Clojure / Haskell

Question

I have been comparing OOP and FP methodologies and I could not put my head around one thing in functional programming - keeping invariants in the data structure.

For example imagine the following requirements.

We have a list of projects and every project a has list of tasks and a list of assigned members. Every task can have a worker assigned to it but only from the list of project assigned members.

I can imagine how I can solve this problem in a OOP language, for example in Java, by adding required checks and exceptions, and this would lead in my opinion to more robust code.

But as the data is separated from the behaviour in FP, how should I solve the same problem in FP, say in Clojure or Haskell?

Answer 1

In Clojure it is possible to specify arbitrary :pre and :post conditions on any function. Here's an example from the documentation:

(defn constrained-sqr [x]
    {:pre  [(pos? x)]
     :post [(> % 16), (< % 225)]}
    (* x x))

There's also a very interesting library core.contracts that implements contracts in Clojure.

Answer 2

Your question is very general, a lot of strategies could be used to solve related problems but, essentially, checking invariants (at runtime) is "equal" than in OOP

assign :: Task -> Worker -> Either String Task
assign task worker =
    if not (taskProject task) `containsWorker` worker
        then Left "You can't assign..."
        else Right $ task { taskWorkers = worker : taskWorkers task }

One common behavior is hide data constructor (as Task, Worker and Project), the OOP counterpart is write private constructors.

module Scheduler (
  Task   -- instead `Task (..)`
, Worker -- instead `Worker (..)`
...
, assign
, createTask
, createWorker
...
) where

(I unkown the current Haskell support to friend, protected, ... counterpart probably not exists and you can find a lot of Haskell modules with Some.Module.Internals.Something with private objects)

The main question is about how to structure the whole program to achieve the required behavior.

Real World Haskell is a good starting point to learn about that or as suggested on related question Large-scale design in Haskell?

On the other hand, about pre/post condition in Haskell you can read What are the options for precondition checking in Haskell.

Answer 3

You say data is "separated" from behavior in an FP language, but in Haskell (I don't know Clojure) you can quite easily define a data structure in a module, make its definition private, and only export functions to manipulate the data.

In other words, Haskell doesn't have (OO-style) classes, but it still has encapsulation.

Answer 4

JoseJuan and MathematicalOrchid covered key points about hiding constructors while exposing types and interfaces, but there is another technique for managing certain kinds of invariants in Haskell: encode them in the type system. Algebraic data types do this to a certain degree on their own:

data Tree a = Tri (Tree a) a (Tree a) a (Tree a)
            | Bin (Tree a) a (Tree a)
            | Tip

is much more constrained than

newtype Tree a = Tree [a] [Tree a]

But you can go much further using nested types, phantom types, and GADTs. For example, Data.Sequence defines

newtype Elem a = Elem a
data Node a = Node2 !Int a a | Node3 !Int a a a
data Digit a = One a | Two a a | Three a a a | Four a a a a
data FingerTree a = Empty
                  | Single a
                  | Deep !Int (Digit a)
                    (FingerTree (Node a))
                    (Digit a)
newtype Seq a = Seq (FingerTree (Elem a))

Note that a deep FingerTree a contains a FingerTree (Node a). This is called a "nested" or "non-regular" type; it ensures that the 2-3 trees at each level are exactly one deeper than the ones at the previous level.

The same shape invariant could be maintained differently (but less efficiently, as it turns out) using phantom types and GADTs:

{-# LANGUAGE GADTs, DataKinds, KindSignatures #-}
data Nat = Z | S Nat

-- This is a GADT; n is a phantom type
data Tree23 (n::Nat) a where
  Elem :: a -> Tree23 Z a
  Node2 :: !Int -> Tree23 n a -> 
             Tree23 n a -> Tree23 (S n) a
  Node3 :: !Int -> Tree23 n a -> Tree23 n a ->
             Tree23 n a -> Tree23 (S n) a

-- n is again a phantom type
data Digit (n::Nat) a
  = One (Tree23 n a)
  | Two (Tree23 n a) (Tree23 n a)
  | Three (Tree23 n a) (Tree23 n a) (Tree23 n a)
  | Four (Tree23 n a) (Tree23 n a) (Tree23 n a) (Tree23 n a)

-- n is still a phantom type
data FingerTree (n::Nat) a
     = Empty
     | Single a
     | Deep !Int (Digit n a) (FingerTree (S n) a) (Digit n a)

In this version, the level of the finger tree is "tracked" using a phantom type, and then the heights of the 2-3 trees are forced to match it using a GADT.