module LAG

where 
import List
import Char

listsOfLength :: Int -> [a] -> [[a]]
listsOfLength 0 alphabet = [[]]
listsOfLength n alphabet = 
  [ x:xs | x <-  alphabet,
           xs <- listsOfLength (n-1) alphabet ]

star  :: [a] -> [[a]]
star alphabet = 
  concat [ listsOfLength n alphabet | n <- [0..] ]

copies ::  a -> Int -> [a]
copies x 0 = []
copies x n = x : copies x (n-1)

reversal :: [a] -> [a]
reversal [] = []
reversal (x:xs) = reversal xs ++ [x]

binaryWhole :: [Char] -> Bool
binaryWhole ['0'] = True
binaryWhole ('1':xs) = binaryWholeA xs 
binaryWhole ('-':'1':xs) = binaryWholeA xs 
binaryWhole _ = False

binaryWholeA :: [Char] -> Bool
binaryWholeA [] = True
binaryWholeA ('0':xs) = binaryWholeA xs
binaryWholeA ('1':xs) = binaryWholeA xs
binaryWholeA _ = False

genWholes :: [String]
genWholes = filter binaryWhole (star "-01")

split2 :: [a] -> [([a],[a])]
split2 [] = [([],[])]
split2 (x:xs) = ([],(x:xs)):
   (map ( \ (ys,zs) -> ((x:ys),zs)) (split2 xs))

split3 :: [a] -> [([a],[a],[a])]
split3 xs = [(ys,zs,us) | (ys,ws) <- split2 xs, 
                          (zs,us) <- split2 ws ]

split4 :: [a] -> [([a],[a],[a],[a])]
split4 xs = 
  [(ys,zs,us,vs) | (ys,ws)    <- split2  xs, 
                   (zs,us,vs) <- split3 ws ]

recognizeA :: [Char] -> Bool
recognizeA [] = True
recognizeA ('a':xs) = 
  or [ recognizeA ys | (ys,zs) <- split2 xs, 
                        zs == ['b'] ]
recognizeA _ = False

genA :: [String]
genA = filter recognizeA (star "ab")

recliteral :: Eq a => a -> [a] -> Bool
recliteral x xs = xs == [x]

recS :: [Char] -> Bool
recS xs = or [ recA ys && recC zs | 
                 (ys,zs) <- split2 xs ]
recA [] = True
recA xs = or [ recliteral 'a' ys
               && recA zs
               && recliteral 'b' ws | 
                 (ys,zs,ws) <- split3 xs ]
recC [] = True
recC xs = or [ recliteral 'c' ys
               && recC zs | (ys,zs) <- split2 xs ]

genS :: [String]
genS = filter recS (star "abc")