--
-- lab2.hs
--
-- Sum a list of integers recursively.
sumIntegers1 :: [Integer] -> Integer
-- TODO
-- Sum a list of integers in terms of foldl.
sumIntegers2 :: [Integer] -> Integer
-- TODO
-- Product of a list of integers in terms of foldr.
prodIntegers :: [Integer] -> Integer
-- TODO
-- List append in terms of foldr.
listAppend :: [a] -> [a] -> [a]
-- TODO
-- Insertion sort.
-- This sorts a list of values (which all have to be of type class Ord)
-- according to the following algorithm:
-- 1) Sort the sublist consisting of the tail of the list.
-- 2) Insert the first element (the head) into the sorted sublist at the
-- correct place.
-- Sort the list in ascending order.
insertionSort :: Ord a => [a] -> [a]
-- TODO
-- 'map' that works on two lists.
-- map f a b = [(f a1 b1), (f a2 b2), ...]
-- where a = [a1, a2, ...] and b = [b1, b2, ...]
map2 :: (a -> b -> c) -> [a] -> [b] -> [c]
-- TODO
-- Infinite list of factorials, starting from 0!, using map2.
factorials :: [Integer]
-- TODO
-- Infinite list of prime numbers using list comprehensions and a sieving
-- algorithm. The sieve works as follows: it's n followed by (the sieve of)
-- all numbers that aren't divisible by n.
primes :: [Integer]
-- TODO
-- Tree data structure. Note that this is different from the Tree
-- structure used in the lecture.
data Tree a = Leaf | Node a (Tree a) (Tree a)
deriving Show
-- Sample tree (for testing).
sampleTree :: Tree Integer
sampleTree = Node 1 (Node 2 (Node 3 Leaf Leaf) Leaf) (Node 4 Leaf Leaf)
-- Count the number of leaves in a Tree.
countLeaves :: Tree a -> Integer
-- TODO
-- Mapping over a tree.
mapTree :: (a -> b) -> Tree a -> Tree b
-- TODO
-- Some data/functions for testing:
-- Counting characters in a String.
countChars :: String -> Integer
countChars = toInteger . length
-- Sample tree of strings.
treeOfStrings :: Tree String
treeOfStrings = Node "foo"
(Node "bar" (Node "baz" Leaf Leaf) Leaf)
(Node "bam" Leaf Leaf)
treeOfNums :: Tree Integer
treeOfNums = mapTree countChars treeOfStrings
-- Fold on a tree.
foldTree :: (a -> a -> a) -> a -> Tree a -> a
-- TODO
-- Sample use of foldTree: count the characters in a tree of Strings.
charsInTree :: Integer
charsInTree = foldTree (+) 0 (mapTree countChars treeOfStrings)
--
-- end of lab2.hs
--