Discrete Dynamic Systems in Haskell

0. We will be consider discrete dynamical systems. "Discrete" meaning we're using integers to keep track of time. "Dynamical Systems" keep track of state evolving in time. So in Haskell

type Time = Int
data State = {
    --- implementation left to the user
    } deriving (Eq, Show)

Remark. For continuous systems, we have the subtle problems of quadrature to deal with, because we'll be solving differential equations. Maybe this is something to think about. (End of Remark)

1. A "Flow" is a family of maps of a set X, Flow :: Time -> (State -> State) such that (i) Flow 0 == id and (ii) Flow t . Flow s == Flow (t + s).

--- Warning: I have no clue if this will work as intended
class Flow f where
  flow :: Time -> State -> State
  flow 0 = id

Remark. If we restricted time to non-negative integers, then we have a "semiflow". (End of Remark)

2. Given some initial state x0 :: State, we usually study processes x :: Time -> State such that x t = (Flow t) x0.

3. A "Trajectory" is a map Trajectory :: State -> (Time -> State) taking Trajectory x0 = (\t -> (Flow t) x0).

Trajectory :: State -> (Time -> State)
Trajectory x0 = (\t -> (Flow t) x0)

Remark. If I knew how to implement a process better, a trajectory would be a more natural thing. But it shouldn't be Trajectory x0 = Process x0. (End of Remark)

4. The "Orbit" of some state x is a set Orbit :: State -> [State] defined by Orbit x = [(Flow t) x | t <- [0..]].

Orbit :: State -> [State]
Orbit x = [(Flow t) x | t <- [0..]]

Remark. Really, this should be over all time. So if we have positive and negative integers for time, we should have something like Orbit x = [(Flow t) x | t <- [-Infinity .. +Infinity]]...but I don't know how to meaningfully implement this in Haskell. (End of Remark)

5. A "fixed point" is a state which does not change in time under our equations of motion. So, we can implement a predicate testing for this:

isFixedPoint :: State -> Bool
isFixedPoint x = x == (Flow 1) x

Can you see why this works for a discrete system? Property (ii) of the flow tells us the "sucessor function" applied over and over again will give us (Flow t) x0 (if we iterate (Flow 1) exactly t times). So if x is a fixed state, then (Flow 1) x should be x by definition ("any successor must be the same state").

Exercise for the Author. Demonstrate this framework can describe cellular automata. Hopefully it is elegant...

References

1. Jürgen Jost, Dynamical Systems: Examples of Complex Behaviour. Springer-Verlag, 2005.