CSE 130 
Sample Solutions for Group Project 1
NOTE: there are always different possible solutions 


-- ===================
-- PROBLEM 3: POWERSET
-- ===================
-- when called with [] you have to provide the type of the list!
-- Example: powerset ([]::[Int]) 
-- but otherwise you don't have to give the type!
-- reason: Hugs can infer the type, but not if the
-- input is the empty list! Empty list of what??

powerset		:: [a] -> [[a]]
powerset []		= [[]]
powerset (x:xs)		= [x:ys | ys <- powset] ++ powset
			  where 
				powset = powerset xs

-- alternative (very similar) solution

powerset1		:: [a] -> [[a]]
powerset1 []		= [[]]
powerset1 (x:xs)	= powerset1 xs ++ [x:ys | ys <- (powerset1 xs)]


-- ===========================
-- PROBLEM 4a: PERFECT NUMBERS
-- ===========================
-- ... the numerical types below are "Int". Alternatively, we could 
-- ... have used "Integer" or even omitted the type declarations 
-- ... to have the system infer the most general type.

-- factor n m 
-- ... tests whether n is a factor of m
factor			:: Int -> Int -> Bool
factor n m		=  m `mod` n == 0 

-- factors n
-- ... returns the list of all factors of n between 1..n-1
factors			:: Int -> [Int]
factors n		= [ i | i<-[1..n-1],  factor i n  ]

-- perfect n
-- ... tests whether n is a perfect number, i.e., 
-- ... the sum of factors equals the number
perfect			:: Int -> Bool
perfect n		= sum (factors n) == n

-- perfectnums 
-- ... generates the (infinite) list of perfect numbers. 
-- ... (strictly speaking we would have to use type "Integer" 
-- ... to really get a potentially infinite list)
perfectnums		:: [Int]
perfectnums		= [n | n <- [1..], perfect n]



-- ==============================
-- PROBLEM 4B: SQUAREFREE NUMBERS
-- ==============================
-- squarefactors n
-- ... returns the list of all factors (apart from 1) 
-- ... which are square numbers
squarefactors		:: Int -> [Int]
squarefactors n		= [ i | i <- [2..n], factor (i*i) n ]

-- squarefreenumbers
-- ... returns the list of all square free numbers 
squarefreenums		:: [Int]
squarefreenums		= [ n | n <- [1..], squarefactors n == [] ]




-- ====================
-- PROBLEM 5: XML trees
-- ====================

type Attribute		= (String, String)	-- Att-name/Att-value pair

data XML		= EmptyXML 
			| Leaf String 
			| Elem String [Attribute] [XML]

booksTree = 
	Elem "books" []
		[Elem "book" [("year","1995"), ("edition","1")]
			[Elem "title" [] [Leaf "Foundations of Databases"],
			Elem "author" [] [Leaf "Abiteboul"],
			Elem "author" [] [Leaf "Hull"],
			Elem "author" [] [Leaf "Vianu"]],
		 Elem "book" [("edition","1"), ("year","2000")]
			[Elem "title" [] [Leaf "Constraint Databases"],
			Elem "editor" [] [Leaf "Kuper"],
			Elem "editor" [] [Leaf "Libkin"],
			Elem "editor" [] [Leaf "Paredaens"]]]


-- ==============================
-- Returning the tags in PREORDER:
-- ...neat isn't it!?
-- ==============================
tags				:: XML -> [String]
tags EmptyXML			= []
tags (Leaf _)			= []
tags (Elem tag _ children)	= tag : concat' (map tags children)

-- here we've used the "concat" function which is nothing else
-- ... but folding a list (from the right) using "++": 
-- (since concat is predefined, we called it concat')
concat'           :: [[a]] -> [a]
concat'            = foldr (++) []


-- ====================
-- alternative solution
-- ====================
-- observe how we "programmed out"
-- ... the "concat (map ...)" construction using a 
-- ... tags1_list helper function
tags1				:: XML -> [String]
tags1 EmptyXML			= []
tags1 (Leaf _)			= []
tags1 (Elem tag _ children)	= tag : (tags1_list children)

tags1_list []			= []
tags1_list (x:xs)		= tags1 x ++ tags1_list xs


{------------------------ EXAMPLE OUTPUT ---------------------
Main> tags booksTree
["books","book","title","author","author","author","book","title","editor","editor","editor"] :: [String]
(1308 reductions, 1753 cells)
--------------------------------------------------------------}