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**