EoPL - Ch 1 - Ex 16

Exercise 16 in Chapter 1 of Essentials of Programming Languages builds on the progress of Exercise 15. It further explores programming with lists by delving into deeply-nested list structures (pun intended). Note that the up function in Part 1 plays counterpart to the down function from Exercise 15, Part 9.

Ex. 16, Pt. 1
Define a function up : (lst : [_]) -> [_] that returns a list like lst but with each list-element (element of type list) replaced by the elements that that list-element contains. Solution.

Ex. 16, Pt. 2
Define a function swapper : (s1 : 'a) * (s2 : 'a) * (lst : [_]) -> [_] that returns a list like lst but with all instances of s1 replaced by s2, and all instances of s2 replaced by s1. Solution.

Ex. 16, Pt. 3
Define a function count-occurrences : (s : 'a) * (slist : [_]) -> int that returns the number of times s occurs in slist, including occurrences nested arbitrarily deep in list-elements of slist. Solution.

Ex. 16, Pt. 4
Define a function flatten : (slist : [_]) -> [_] that returns a list of all non-list-elements in slist (including non-list-elements nested arbitrarily deep within list-elements) in depth-first-traversal order. Solution.

Ex. 16, Pt. 5
Define a function merge : (lon1 : [int]) * (lon2 : [int]) -> [int] that returns a list, in ascending order, of the elements in lon1 and in lon2, where lon1 and lon2 are each already sorted in ascending order themselves. Solution.