Applying a (possibly unary) function recursively on itself

Question

I am trying to express the L-system in Haskell https://en.m.wikipedia.org/wiki/L-system , in particular the original Lindenmayer L-system for modeling algae growth.

variables: AB
constants: no
axiom: A
rules: (A → AB), (B → A)

For me, the natural way to approach this problem is to apply rules to each element in the list, which (for me) means that I can model the solution using some type of string substitution.

Example:

In the list of “characters” [A, B, A, we apply the rules and get [A → AB, B → A, A → AB] = [A, B, A, A, B] (so that this model plays well with Haskell, you have to consider AB as a list of [A, B], which we will combine with any other results obtained using the above rules).

I have cited the code below that contains data constructors that should not process characters other than A or B,

data Letter = A | B deriving (Show, Eq) type Alphabet = [Letter] algae :: Alphabet -> Alphabet algae = concat . map (\c -> if | c == A -> A:[B] | c == B -> [A]) 

The above code is such that calling it with you as an argument gives the expected result, namely: that

 algae $ algae $algae [A] = [A, B, A, A, B] 

Duplicate applications work as expected.

What I want to do next is that the function will be recursively applied to itself, but not expressed. By this, I mean that I would like to be able to call the function either as algae [A] , or just algae (which requires changing the type signature to algae :: Alphabet ), which gives an infinite list that can be obtained using algae on itself infinitely many times.

Since I was defeated, I looked at http://hackage.haskell.org/package/lindenmayer-0.1.0.0/docs/Lindenmayer-D0L.html , but I can’t understand the code as it is (for now), and also found the others the same confusing implementations.

I tried my best to try to use the function with folds and fix , but could not do it. I also tried to borrow from other recursive definitions such as

 fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 

But this approach fails, since zipWith expects a binary operator. Is it possible to solve this problem without monads? If so, how?

Answer 1

You can use iterate . I would also suggest a slight modification to your algae function to use pattern matching:

 data Letter = A | B deriving (Show, Eq) type Alphabet = [Letter] algae :: Alphabet -> Alphabet algae = concatMap f where f A = [A, B] f B = [A] infAlgae :: [Alphabet] infAlgae = iterate algae [A] main :: IO () main = print $ infAlgae !! 3 

Answer 2

I thought you might also be wondering how to effectively create an actual infinite list, fibs style:

 import Data.List (stripPrefix) data Letter = A | B deriving (Show, Eq) type Alphabet = [Letter] algae :: Alphabet -> Alphabet algae = concatMap f where f A = [A, B] f B = [A] infFromPrefix :: Eq a => ([a] -> [a]) -> [a] -> [a] infFromPrefix rule prefix = inf where inf = prefix ++ case stripPrefix prefix (rule inf) of Just suffix -> suffix Nothing -> error "Substitution does not preserve prefix" infAlgae :: Alphabet infAlgae = infFromPrefix algae [A] main :: IO () main = print . take 100 $ infAlgae 

And in GHCi:

 *Main> :main [A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,B,A,A,B,A]