CEng 242 Spring 2004-2005
Homework 1

(Due 20/3/2005)

Question 1

Write a Haskell function sublist which receives two list and return True if the first list is a sublist of the second, or False otherwise.

The all elements of the first list should be contained in the second list consequitively in the same order.

For example [2,4,5] is a sublist of [3,7,2,4,5,9] but not [3,7,4,2,5,9].

Function sublist should have the following type signature:
sublist:: [a] -> [a] -> Bool

Example:

sublist [1,2,3] [0,1,2,3,4,5,6]
True
sublist [5,4] [1,4,5,7,8,3,5,4]
True
sublist [2,8] [1,5,6,2,4,7,8,2]
False
sublist [1,2,4,3,4,5,7,8,9,5] [8,2,3,1,2,4,3,4,5,7,8,9,5,1,6,2]
True


Question 2

Write a function subtree which receives two binary trees and return True if the first tree is a subtree of the second, or False otherwise.

Assume a tree is a subtree of the other if all elements of the first tree is included in the second with the exact structure; all parent-child relations are preserved with their order.

You will use the following tree type definition:
data Tree = Empty | Leaf Int | Node (Int,Tree,Tree)
and you will have the following type signature for subtree:
subtree:: Tree -> Tree -> Bool

Example:

let tree1 = Node(3, Leaf(5), 
                    Node(6,Leaf(7),Leaf(4)))
    tree2 = Node(13,Node(3,Leaf(5),
                           Node(6,Node (7, Leaf (2), Empty),
                                  Node(4,Leaf(3),Leaf(4)))),
                    Node(12,Leaf(9),Node(6,Leaf(11),Leaf(7))))
in  subtree tree1 tree2
True
tree1 tree2
  3
 / \
5   6
   / \
  7   4
       13
     /    \
    3      12
   / \     / \ 
  5   6   9   6
     / \     / \
    7   4   11  7
   /   / \
  2   3   4