import Plural

data Nat = Z | S Nat

data List a = Nil | Cons a (List a)

add Z x = x
add (S x) y = S (add x y)

mult Z _ = Z
mult (S x) y = add y (mult x y)

two = S (S Z)
four = add two two
eight = add four four
n16 = add eight eight
n20 = add n16 four 
n32 = add n16 n16 
n256 = mult n16 n16 
n1024 = mult four n256

-----------------------------------------------------------------

ifThen :: Bool -> a -> a
ifThen True x = x

-- An alternative definition of the palindrome property without
-- higher-order functions, logic variables etc:
pali :: Plural a -> List a -> Bool
pali _ Nil = True
pali t (Cons x Nil) = ifThen (t==x) True
--pali t (x : xs) | t==x && x==y = pali t ys  where (ys,y) = last xs
pali t (Cons x xs) = ifThen (t==x) (paliAux t x (last xs))

paliAux :: Plural a -> a -> (List a,a) -> Bool
paliAux t x (ys,y) = ifThen (x==y) (pali t ys)

last (Cons x Nil) = (Nil,x)
--last (x:xs) = let (ys,y) = last xs in (x:ys,y)
last (Cons x xs) = lastAux x (last xs)
lastAux x (ys,y) = (Cons x ys,y)

abPali s = pali (A ? B) s

main1 = abPali (Cons A (Cons B (Cons A Nil)))
main2 = abPali (Cons A (Cons C (Cons A Nil)))

-- Palindromes over digits:
numPali s = pali (0?1?2?3?4?5?6?7?8?9) s

--main3 = numPali [0,1,2,3,4,5,4,3,2,1,0]

len Nil = 0
len (Cons _ xs) = 1 + len xs

-----------------------------------------------------------------
-- Generate test data:
data Letter = A | B | C

aaList Z = Nil
aaList (S n) = Cons A (aaList n)

aabbaaList Z l = Cons B (Cons B (aaList l))
aabbaaList (S n) l = Cons A (aabbaaList n l)

genList n = aabbaaList n n

main3 = abPali (genList (S Z))
main4 = abPali (genList two)  --> Length: 6    Time: 0ms
main5 = abPali (genList four) --> Length: 10   Time: 0ms
main6 = abPali (genList eight)--> Length: 18   Time: 0ms
main7 = abPali (genList n16)  --> Length: 34   Time: 0ms
main8 = abPali (genList n32)  --> Length: 66   Time: 0ms
main9 = abPali (genList n256) --> Length: 514  Time: 100ms