-- | Assignment 1 template.
-- Instructions. 
--      1. You are to write your solutions to the assignment in this file. You
--      may add extra functions in this file to implement your solution.
--
--      2. When testing your code locally, make sure that you have the
--      'Assignment1Types.hs' file in the same directory as this file, so
--      Haskell can load up that file as well.
--
--      3. Do NOT change the type or name of any of the template functions. 
--
--      4. Do NOT change the name of this file. 
--
--      5. Do NOT change the module name of this file.
--
--      6. To submit this to GradeScope, submit ONLY this file.
--
--      7. Have lots of fun :)
module Assignment1 where

-- This imports some required types for the assignment such as the 'Rose' data
-- type for question 19.
import Assignment1Types

-- | 1
-- Write your own function for appending two lists and for reversing a list:
-- @app:: ([a],[a]) -> [a]@, @rev:: [a] -> [a]@.  Now define your own datatype
-- for lists and write the append function for this datatype.

app :: ([a], [a]) -> [a]
app = undefined

rev :: [a] -> [a]
rev = undefined

-- | 4
-- Write a function to determine whether its first argument, a list of
-- integers, is lexicographically larger than its second argument:
-- @lexInt::[Int] -> [Int] -> Bool@.   Now modify it to work on any type in
-- class Ord. Finally can you modify the Ord class to include lexicographical
-- orderings of lists.

lexInt :: [Int] -> [Int] -> Bool
lexInt = undefined

lexOrd :: Ord a => [a] -> [a] -> Bool
lexOrd = undefined

-- Don't forget to add it into the class system!  Since Ord [] already exists,
-- you will need to make a @newtype MyList a = MyList [a]@ and put that in the
-- class system instead.

-- | 5
-- Develop a merge sort in Haskell: 
--      - Write a function which splits a list into two lists, the first
--      containing the odd indexed elements and the second containing the even
--      indexed elements: @msplit:: [a] -> ([a],[a])@. 
--
--      - Write a function to merge two lists of integers, taking the least
--      first element at each step: @mergeInt :: ([Integer],[Integer]) ->
--      [Integer]@. 
--
--      - Write a mergesort for integers:  @mergesortInt :: [Integer] ->
--      [Integer]@. 
--
-- Generalize the mergesort to arbitrary ordered type (using the class system).

msplit :: [a] -> ([a], [a])
msplit = undefined

mergeInt :: ([Integer],[Integer]) -> [Integer]
mergeInt = undefined

mergesortInt :: [Integer] -> [Integer]
mergesortInt = undefined

merge :: Ord a => ([a],[a]) -> [a]
merge = undefined

mergesort :: Ord a => [a] -> [a]
mergesort = undefined

-- | 6 
-- Write a quicksort for an arbitrary ordered type.
quicksort :: Ord a => [a] -> [a]
quicksort = undefined

-- | 7
-- Write a function which determines whether an element (of equality type) is in a list.
member :: Eq a => a -> [a] -> Bool
member = undefined

-- | 9
-- Program the "group" function: given a predicate pred:: a -> a -> Bool and a
-- list the group function breaks the list into a series of (maximal) sublists
-- such that any two consecutive elements satisfy the predicate pred.   The
-- type of the function group is @group:: (a -> a -> Bool) -> [a] -> [[a]]@.  An
-- example of its use is as follows: suppose that the predicate nbr determines
-- whether the absolute difference of two integers is at most 1 (i.e. they are
-- equal or they differ by one) then @group nbr [2,1,3,4,5,5,4,7,4,3,3] =
-- [[2,1],[3,4,5,5,4],[7],[4,3,3]]@: program up this example to make sure your
-- group works.  What is @group nbr []@?

group :: (a -> a -> Bool) -> [a] -> [[a]]
group = undefined


-- | 11
-- Write a function which given a list returns the list of all permutations of that list: @perm:: [a] -> [[a]]@. 
perm :: [a] -> [[a]]
perm = undefined

-- | 12
-- Given a permutation it is possible to give its cyclic decomposition. For
-- example the permutation [2,4,5,1,3] of [1,2,3,4,5] can be represented as
-- [[1,2,4],[3,5]] where this indicates that each element becomes its righthand
-- neighbor unless it is at the end of a sublist in which case it goes to the
-- first in the sublist. Give the list of all permutations represented by their
-- cyclic decompositions.

cyclicDecomp ::
    Eq a => 
    -- | original list
    [a] -> 
    -- | a permutation of the original list
    [a] -> 
    -- | return the cyclic decomposition
    [[a]]
cyclicDecomp = undefined

-- | 15
-- Write a function for normalizing, adding, and multiplying multivariable
-- polynomials.  You may represent the polynomials as lists of real numbers
-- paired with a list of powers, [(Float,[Int])], for each variable so
-- [(1.5,[0,0,0]),(3.2,[0,1,1]),(4.7,[2,2])] = 1.5 + 3.2yz +4.7x^2y^2. To
-- normalize a polynomial one places entries so the power lists are in
-- lexicographical order and one amalgamates any repeated terms: @normpoly::
-- [(Float,[Int])] -> [(Float,[Int])]@. To add polynomials we have @addpoly::
-- [(Float,[Int])]  -> [(Float,[Int])] -> [(Float,[Int])]@ and to multiply
-- polynomials @multpoly:: [(Float,[Int])]  -> [(Float,[Int])] ->
-- [(Float,[Int])]@.

normpoly :: [(Float,[Int])] -> [(Float,[Int])]
normpoly =  undefined

addpoly :: [(Float,[Int])] -> [(Float,[Int])] -> [(Float,[Int])]
addpoly = undefined

multpoly :: [(Float,[Int])]  -> [(Float,[Int])] -> [(Float,[Int])]
multpoly = undefined

-- | 18
-- Calculate the factorial of 1,891 or explain six different ways of programming factorial.

computeFactorial1891 :: Integer
computeFactorial1891 = undefined

-- | 19 
-- Given a Rose tree with values at the arguments of the nodes ( data Rose a =
-- RS [(a,Rose a)] ) use a fold to calculate the width of a Rose Int tree (that
-- is in the undirected graph of the tree with weighted edges, the width is the
-- length of the longest path),  @width:: Rose Int -> Int@.
--
-- Note: You must use the 'Rose' tree data type as defined in the module
-- Assignment1Types. 
-- Note: You may assume that Int is non-negative
width :: Rose Int -> Int
width = undefined