Complete the following Haskell function denitions. Unless stated otherwise
do not use library functions that are not in the Haskell standard
prelude. This constraint is so that you gain practice in simple Haskell
recursive programming. The Haskell 2010 standard prelude denition is
available at
https://www.haskell.org/onlinereport/haskell2010/haskellch9.html
Place all denitions in a single le. Submit just this text le
electronically as directed on the course Study Desk page. Use the
specied function name as your code will be tested by a Haskell function
expecting that function name.
The testing program may use many more test cases than the ones shown in
the specication. So, please test your functions extensively to ensure that
you maximise your marks.
1. [2 marks]
Write the function insertAt :: Int -> a -> [a] -> [a].
insertAt n x xs will insert the element x into the list xs at position
n items from the beginning of xs. In other words, skip n items in xs,
then insert the new element.
You can assume that n will be a non-negative number. If n is greater
than the length of the list xs then add it to the end of the list.
For example
insertAt 3 ‘-‘ “abcde” ) “abc-de”
insertAt 2 100 [1..5] ) [1,2,100,3,4,5]
Hint: Use standard prelude functions ++ and splitAt.
2. [2 marks] Write a function uniq :: Eq a => [a] -> [a] that re-
moves duplicate entries from a sorted (in ascending order) list. The
1
Sem 1, 2018
CSC3403 Comparative Programming Languages
11:55pm AEST (13:55 UTC/GMT) 8th May 2018
12%
12
resulting list should be sorted, and no value in it can appear elsewhere
in the list.
For example:
uniq [1,2,2] ) [1,2]
uniq [1,2,3] ) [1,2,3]
3. [1 mark] Write a function
join :: Eq a => [(a,b)] -> [(a,c)] -> [(a,b,c)].
join takes two lists of pairs, and returns a single list of triples. A triple
is generated only when there exists a member of both argument lists
that have the same rst element. The list elements are not sorted. This
is the same semantics as the relational algebra natural join operation.
For example:
join [(2,”S”),(1,”J”)] [(2,True),(3,False)]
) [(2,”S”,True)]
join [(2,”S”),(1,”J”)] [(2,1),(2,2),(3,4)]
) [(2,”S”,1),(2,”S”,2)]
Hint: use list a comprehension.
4. [1 mark] This question extends the join function from question 3.
Write the function
ljoin :: Eq a => [(a,b)] -> [(a,c)] -> [(a,b,Maybe c)].
This is the left outer join from relational algebra. If a tuple (database
row) from the rst (left) argument does not have a matching tuple
from the second argument, include that tuple in the resulting tuple,
but place a \null” value in place of the un-matched value. For this
implementation we use a Maybe data type, and use the Nothing value
to denote Null.
For example
ljoin [(2,”S”),(1,”J”)] [(2,1),(2,2),(3,4)]
) [(2,”S”,Just 1),(2,”S”,Just 2),(1,”J”,Nothing)]
5. [2 marks] Consider the following denition for a binary tree.
data Tree a = Leaf a | Node (Tree a) (Tree a)
A binary tree is balanced if, at every node, the dierence
between the number of leaves appearing in the left and right
subtree is at most one. (A tree which contains just one leaf
is considered balanced.)
Write the function isBalanced :: Tree a -> Bool that decides if
the tree is balanced. Hint: rst write a function size::Tree a ->
Int that counts leaves in a tree.
2
isBalanced (Node (Node (Leaf 1)(Leaf 3)) (Leaf 2)) ) True
isBalanced (Node (Node (Leaf 1)(Node (Leaf 1)(Leaf 3))) (Leaf
2))
) False
6. [2 marks] Write a function isNumber :: String -> Bool that tests
if a string contains a valid number. A valid number is dened in EBNF
as:
number ! :digit+ j digit+ [ :digit]
For example, .5, 1.5, 1, 1. are all valid numbers. As usual, +
signies one or more occurrences, and * denotes zero or more.
You may use the isDigit function from the Data.Char module.
Hint: you may wish to write functions someDigits, manyDigits ::
String -> Bool to test for :digit+ and digit.
7. [2 marks] Write a function getElems :: [Int] -> [a] -> [Maybe
a] which takes a list of integers signifying the position of an element
in a list, and a list. It returns those elements that correspond to the
positions specied. Because a position may be greater than the list size
the returned element is a Maybe data type. If the position specied is
greater the the maximum list position then Nothing is returned, else
Just value.
For example
getElems [2,4] [1..10] ) [Just 3,Just 5]
getElems [2,4] [1..4] ) [Just 3,Nothing]
3
TO GET THIS OR ANY OTHER ASSIGNMENT DONE FOR YOU FROM SCRATCH, PLACE A NEW ORDER HERE
