SuperPAL

Welcome to SuperPAL questions. This worksheet is divided into 4 topics: Recursion, Higher Order Functions and Trees. At the end, there are also a few questions on Lambda Calculus and Proving Programs for COMP1130 students.

Recursion

Question 1

Write a function that compresses a list by making it a list of list, where each inner list is a list of adjacent duplicates. For example:

pack [1,1,2,4,42,1,1,6,6,6,6,7,1]
    = [[1,1],[2],[4],[42],[1,1],[6,6,6,6],[7],[1]]

Question 2

Write a function that checks whether a given list of elements is increasing or not. For example:

isSorted [1,2,3,2,4,5] = False
isSorted [1,1,4,7] = True
isSorted [] = True

Question 3

Write a function that takes an integer and a list and drops every n’th element of that list. For example:

dropEvery [1..10] 2 = [1,3,5,7,9]

Question 4

A “scan” is like a cross between a map and a fold. Folding a list accumulates a single return value, whereas mapping puts each item through a function returning a separate result for each item. A scan does both: it accumulates a value like a fold, but instead of returning only a final value it returns a list of all the intermediate values. There are four different types of scans defined in the prelude namely scanl, scanr,scanl1 and scanr1.

We are going to write out own scanl. It’s type signature is:

scanl :: (a -> b -> a) -> a -> [b] -> [a]

At each step, it adds the second input to the intermediate values list, and then uses the inputted function on the second input and the first element of the list, setting the second input to the result and removing the first element from the list. At the end, it returns the list of the intermediate values. For example:

scanl (+) 2 [1..5]  = 2 : (scanl (+) 3 [2..5])
                    = 2 : (3 : (scanl (+) 5 [3..5]))
                    = 2 : (3 : (5 : (scanl (+) 8 [4,5])))
                    = 2 : (3 : (5 : (8 : (scanl (+) 12 [5]))))
                    = 2 : (3 : (5 : (8 : (12 : (scanl (+) 17 [])))))
                    = 2 : (3 : (5 : (8 : (12 : (17 : [])))))
                    = [2,3,5,8,12,17]

Higher Order Functions

Question 1

Write a function that takes multiple sentences and removes all non-letters and capitalises all letters. For example:

onlyBigLetters "This is a short sentence. This, on the other hand, is a very very very long and drawn out sentence!"
    = "THISISASHORTSENTENCETHISONTHEOTHERHANDISAVERYVERYVERYLONGANDDRAWNOUTSENTENCE"

Question 2

Write a function that takes in two integers and produces a list of list that is the timetables. For example:

timetables 3 4 = [[1,2,3,4],[2,4,6,8],[3,6,9,12]]

Question 3

Consider the following function:

function = 0 : 1 : (zipWith (+) function (tail function))

What does this function do? What quality of haskell allows this to work?

Question 4

Give an example using booleans that shows that difference between foldl and foldr. Write out a trace for each that shows tha difference.

Question 5

Write the reverse function using foldl.

Trees

Question 1

What is the difference between a binary tree, a balanced binary tree and a binary search tree? Is it possible to always have a balanced binary search tree?

Question 2

Write a function that finds the average depth of a binary tree. For example the following tree

Binary Tree

would output the following:

example_binarytree_0 = example_binarytree_0 = Node (Node (Node (Node Null 8 Null) 6 (Node Null 3 Null)) 3 (Node Null 1 Null)) 2 (Node (Node (Node Null 4 (Node Null 6 Null)) 7 Null) 4 (Node (Node Null 3 Null) 9 (Node Null 2 Null)))

averageDepth example_binarytree_0 = 4.0

Question 3

Write a zipWith function for binary trees. For example if the zip function is +, then:

Zipping two trees with addition

So if one tree doesn’t have the node, then the zip returns no node. In haskell, the example:

example_binarytree_1 = Node (Node (Node Null 6 Null) 3 (Node Null 1 Null)) 2 (Node Null 4 Null)

example_binarytree_2 = Node (Node (Node Null 1 Null) 3 Null) 4 (Node (Node Null 2 Null) 4 (Node Null 8 Null))

treeZipWith example_binarytree_1 example_binarytree_2 (+) = Node (Node (Node Null 7 Null) 6 Null) 6 (Node Null 8 Null)

Question 4

Write a filter function for rose trees. For example, if we filtered by x `mod` 2 == 0 then:

Filtering a rose tree

So all nodes that don’t satisfy x `mod` 2 == 0 are deleted and their children nodes moved up.

Note that if the root node doesn’t pass through the filter, than return a list of rose trees must be returned. So the type is:

treeFilter :: RoseTree a -> (a -> Bool) -> [RoseTree a]
treeFilter tree f = undefined

And the example in Haskell is:

example_rosetree = Rose 10 [Rose 2 [Rose 3 [Rose 6 [], Rose 1 []], Rose 4 []], Rose 1 [Rose 7 [ Rose 8[]], Rose 5 []], Rose 4 [Rose 3 [Rose 1 []], Rose 5 [], Rose 4 [Rose 2 [], Rose 8[]]]]

function x = (x `mod` 2) == 0

treeFilter example_rosetree function = [Rose 10 [Rose 2 [Rose 6 [],Rose 4 []],Rose 8 [],Rose 4 [Rose 4 [Rose 2 [],Rose 8 []]]]]

Hint: Write a helper function that deals with the subtrees first, i.e treeFilterHelper :: [RoseTree a] -> (a -> Bool) -> [RoseTree a].

COMP1130: Lambda and Proving Programs

Question 1

Which variables are bound and which variables are free in the following lambda expression?

(λz.(λy.xyw(λx.zyx)y))

Question 2

Beta reduce the following lambda expression with both eager and lazy evaluation methods until it is in normal form.

(λz.λy.xyz) x ((λx.xx) w)

Question 3

Consider the following Haskell functions:

reverse :: [a] -> [a]
reverse []     = []                     --(reverse.1)
reverse (z:zs) = (reverse zs) ++ [z]    --(reverse.2)

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys                     --(++.1)
(++) (x:xs) ys = x : (xs ++ ys)         --(++.2)

sum :: [a] -> [a]
sum [] = 0                              --(sum.1)
sum x:xs = x + (sum xs)                 --(sum.2)

Prove that sum (reverse ls) = sum ls

Hint: You may want to first prove the Lemma: sum (xs ++ ys) = (sum xs) + (sum ys).