=================================================

||
||	Jonathan Shade
||
||	CSE 505 Autumn 94	
||	Assignment #1 
||	7 october 1994
||


||
||	#4
||
||	Do something interesting with infinite data structures.
||
||	L-systems
||
||		L-systems are named after Aristid Lindenmayer. They
||		were introduced in 1968 as a theoretical framework for
||		studying the development of simple multicelular
||		organisms, and subsequently applied to investigate
||		higher plants and plant organisms.
||
||		To find out more, check out the book:
||
||		"The Algorithmic Beauty of Plants" by
||		  Przemyslaw Prusinkiewicz & Aristid Lindenmayer.
||
||
||	The basic idea is that a L-system is a string rewriting system
||	in which a set of rules are given that show how to rewrite a string.
||
||	Given:
||		a -> ab
||		b -> a
||	
||		initial string: b
||
||	1st rewrite: a
||	2nd rewrite: ab
||	3rd rewrite: aba
||	4th rewrite: abaab
||	5th rewrite: abaababa
||	and so on ...
||
||	Things get more interesting when we interpret the symbols that
||	make up the strings as directives to a turtle graphics type
||	drawing system.
||
||	In the two examples below, symbols stand for the following:
||
||	L : left edge
||	R : right edge
||	+ : turn left by some angle delta
||	- : turn right by some angle delta		
||
||	Left edges and right edges are drawn the same way, just as
||	a line of some predetermined length. It just make things
||	more interesting to have two different kinds of edges.
||
||	This has been a rather terse intro, so refer to the book for
||	more details. The upshot is that things like Koch curves, and
||	snowflakes, and pine trees can be described by these systems.
||	I have implemented two systems, one for a dragon curve, and
||	one for the Sierpinski Gasket. Both work the same way:
||
||	1. There is a function (*_rs) that rewrites a string.
||	2. There is a function (*_rl) that takes a list of strings, plucks
||	   of the first string, has it rewritten, adds it to the list,
||	   then has the result of the above rewriting rewritten and
||	   added to the list, etc on out to infinity. We get an infinte
||	   list of strings (rewrites).
||	3. There is a function ( dragon, sierpinski_gasket ) that "takes"
||	   the first n elements of the infinite list generated by 2. This
||	   gives us the first n rewritings of the L-system.
||
||	dragon 0 will return a list with 1 string:  L
||	dragon 1 will return a list with 2 strings: L, L+R+
||	dragon 2 will return a list with 3 strings: L, L+R+, L+R++-L-R+
||
||	To see the infinite list of rewrites type: dragon_rl ["L"]
||
||	You cant do this on the Sierpinski Gasket because the
||	list rewrite function is in a where clause of the top
||	level function. I did this just to show that the L-system
||	could be implemented that way.
||

||
||	The Dragon Curve.
||
||		Initial String:		L
||
||		Rewrite Rules:		L -> L+R+
||					R -> -L-R
||

|| rewrite a string
||
dragon_rs []    = []
dragon_rs (a:x) = replace a ++ dragon_rs x
			where	replace 'L' = ['L','+','R','+']
				replace 'R' = ['-','L','-','R']
				replace '+' = ['+']
				replace '-' = ['-']	
|| rewrite a list
||
dragon_rl :: [[char]] -> [[char]]
dragon_rl (a:x) = [a] ++ dragon_rl [ (dragon_rs a) ]

|| take first n element of the infinite list of strings
|| created by dragon_rl.
||
dragon :: num -> [[char]]
dragon n = take (n+1) (dragon_rl ["L"])



||
||	Sierpinski Gasket
||
||		Initial String:		R
||
||		Rewrite Rules:		L -> R+L+R
||					R -> L-R-L
||
sg_rs [] = []
sg_rs (a:x) = replace a ++ sg_rs x
		where	replace 'L' = ['R','+','L','+','R']
			replace 'R' = ['L','-','R','-','L']
			replace '+' = ['+']
			replace '-' = ['-']

sierpinski_gasket n = take (n+1) ( sg_rl ["R"] )
		      where sg_rl (a:x) = [a] ++ sg_rl [ (sg_rs a) ]