Lindenmayer.D0L

A D0L is a deterministic, context-free L-system.

An L-system is a tuple L = (V, ω, P) where

• V is the alphabet
• ω is the axiom (starting state)
• P is the set of rules

A deterministic L-system is one where there is only one production rule for each letter in the alphabet. A context-free L-system is one where the production rule looks only at the given letter, not at any of its neighbors.

Here, V is given by the inhabitants of a, ω by an m-container of a, and P by a Kleisli arrow a -> m a. When m is [], this is the usual notion of an L-system.

The original L-system used to model the growth of algae can be given by

data Algae = A | B deriving Show

algae :: D0L [] Algae
algae = D0L rules [B]
  where rules A = [A,B]
        rules B = [A]

We can demonstrate that the lengths of the generated strings give the fibonacci sequence:

>>> print . map (length . axiom) . take 7 . generate $ algae
[1,1,2,3,5,8,13]

Documentation

data D0L m a

Constructors

D0L

Fields

rules :: a -> m a

axiom :: m a

Instances

Show (m a) => Show (D0L m a)

generate :: Monad m => D0L m a -> [D0L m a]

Generate a list of D0L steps starting from an initial system.

step :: Monad m => D0L m a -> D0L m a

Apply the rules to each letter of the axiom (in parallel). The resulting string becomes the axiom of a new D0L with the same rules.