(data Tuple (a b) (
	(Tuple a b)))
(data List (a) (
	Nil
	(Cons a (List a))))
(type String (List Char))

(fun length ((xs : List a)) : Int
	(length_acc 0 xs))
(fun length_acc ((n : Int) (xs : List a)) : Int
	(case xs (
		(Nil -> n)
		(Cons _ xs -> length_acc (+ n 1) xs))))

(data TypeIdent ((TI String)))
(data TypeVarIdent ((TVI String)))
(data ConstructorIdent ((CI String)))
(data SymbolIdent ((SI String)))

(data Type (
	(Type TypeIdent)
	(TypeVar TypeVarIdent)
	(TypeApp Type Type)))

(data ConstructorDef (
	(ConstructorDef ConstructorIdent (List Type))))

(data BasicValue (
	(BVInt Int)
	(BVChar Char)))

(data Pattern (
	Wildcard
	(BasicValuePattern BasicValue)
	(IdentPattern SymbolIdent)
	(ConstructorPattern ConstructorIdent (List Pattern))))

(data CaseAlternative (
	(CaseAlternative Pattern Expression)))

(data Expression (
	(Ident SymbolIdent)
	(Case Expression (List CaseAlternative))
	(ExpApp Expression Expression)))

(data Definition (
	(DataDef TypeIdent (List TypeVarIdent) (List ConstructorDef))
	(FunDef SymbolIdent (List (Tuple SymbolIdent Type)) Type Expression)))

(fun list_ast () : Definition
	(DataDef
		(Cons 'L' (Cons 'i' (Cons 's' (Cons 't' Nil))))
		(Cons (Cons 'a' Nil) Nil)
		(Cons (ConstructorDef (Cons 'N' (Cons 'i' (Cons 'l' Nil))) Nil)
			(Cons (ConstructorDef (Cons 'C' (Cons 'o' (Cons 'n' (Cons 's' Nil)))) (Cons (TypeVar (Cons 'a' Nil)) (Cons (TypeApp (Type (Cons 'L' (Cons 'i' (Cons 's' (Cons 't' Nil))))) (TypeVar (Cons 'a' Nil))) Nil)))
			Nil))))
(fun length_acc_ast () : Definition
	(FunDef
		(Cons 'l' (Cons 'e' (Cons 'n' (Cons 'g' (Cons 't' (Cons 'h' (Cons '_' (Cons 'a' (Cons 'c' (Cons 'c' Nil))))))))))
		(Cons (Tuple (Cons 'n' Nil) (Type (Cons 'I' (Cons 'n' (Cons 't' Nil)))))
			(Cons (Tuple (Cons 'x' (Cons 's' Nil)) (TypeApp (Type (Cons 'L' (Cons 'i' (Cons 's' (Cons 't' Nil))))) (TypeVar (Cons 'a' Nil))))
			Nil))
		(Case (Ident (Cons 'x' (Cons 's' Nil)))
			(Cons (CaseAlternative (ConstructorPattern (Cons 'N' (Cons 'i' (Cons 'l' Nil))) Nil) (Ident (Cons 'n' Nil)))
				(Cons (CaseAlternative (ConstructorPattern (Cons 'C' (Cons 'o' (Cons 'n' (Cons 's' Nil)))) (Cons Wildcard (Cons (IdentPattern (Cons 'x' (Cons 's' Nil))) Nil))))
				Nil)))))