Faculty for Electrical Engineering and Informatics, BME
Engineering Programme in English
MSc Course in Software Engineering
Autumn semester 2007/08

Higher-order Functional Programming

Homework Overlappings

Version 1
Last modification: 26-10-2007

Task description

Given is the wordlist ts = [t0, t1, ..., tz-1] where 0 ≤ z. If z = 0 then ts = []. Collect those pairs of words (ti,tj) from ts for which, with 0 ≤ i < z, 0 ≤ j < z, i ≠ j and 0 ≤ k, it is true that the last k characters of ti are equal to the first k characters of tj. In the following, such pairs of words are called overlapping in k positions or shortly k-overlapping. If k = 0 then ti and tj do not overlap.

More precisely: let us denote the characters of ti by ci0 ci1 ... cim-1 and the characters of tj by cj0 cj1 ... cjn-1. Then, the task is to produce all those (ti,tj) pairs for which, with 0 ≤ k and i ≠ j, the conditions cim-k = cj0, cim-k+1 = cj1, ..., cim-1 = cjk-1 are all satisfied. If k = 0 then ti and tj do not overlap.

Naturally, words that contain less than k characters must not be enumerated.

SML-specification

Write an SML-function called overlappings to return the list of all those k-overlapping pairs of strings (in any order) that are produced by pairing the elements of a string list. 
(* overlappings : int -> string list -> (string * string) list
   overlappings k ts = the list of all k-overlapping pairs of elements from
                       ts
*)

Examples

overlappings 2 ["alma","omlik","mama","malom","ikra","atom","adat","ragad"] =
    [("alma", "malom"), ("alma", "mama"), ("atom", "omlik"), ("omlik", "ikra"),
     ("malom", "omlik"), ("mama", "malom"), ("ikra", "ragad"),
     ("adat", "atom"), ("ragad", "adat")]

overlappings 3 ["alma","omlik","mama","malom","ikra","atom","adat","ragad"] =
    []

overlappings 1 ["alma","omlik","mama","malom","ikra","atom","adat","ragad"] =
    [("alma", "adat"), ("alma", "atom"), ("ikra", "alma"), ("mama", "alma"),
     ("mama", "adat"), ("mama", "atom"), ("atom", "mama"), ("malom", "mama"),
     ("atom", "malom"), ("ikra", "adat"), ("ikra", "atom")]

overlappings 2 ["aa", "aa"] = [("aa", "aa"), ("aa", "aa")]

overlappings 3 ["aa", "aa"] = []

Possible subtasks and further task

Possible subtasks

  1. A predicate to check if two character lists are k-overlapping.
  2. A function to return all the k-overlapping pairs composed of a given word on the one hand, and the elements of a word list on the other.

Possible further task

  1. A function to produce all those pairs of words that overlap in at least 1 and at most k positions. Such pairs of words are called overlapping in maxk positions or shortly maxk-overlapping.