Pending homework questions
Questions 1–13 are now due.
(Find questions that are due here.)
-
Write a Haskell program to find all
of the k-element sublists of a given list. Assuming
that the original list is sorted, the sublists should be in
lexicographic order. For instance,
subList 3 [2,3,5,7,11] should be
[[2,3,5], [2,3,7], [2,3,11], [2,5,7],
[2,5,11], [2,7,11], [3,5,7], [3,5,11],
[3,7,11], [5,7,11]]
If possible, make your program incremental, so that a
computation like
3 `take` (100000 `drop` (subList 20 [1..40]))
is relatively fast.
-
Write a Scheme program to find all
of the k-element sublists of a given list, as in the
previous problem.
If possible, make your program tail recursive.
-
Write a Haskell program to find out
whether a given list is a sublist of a second list.
For instance,
[3,5,11] `isSubList` [2,3,5,7,11] should
be True; [3,5,2] `isSubList` [2,3,5,7,11] should
be False.
- Using your solutions to Questions 14 and 15 and code like the
Prolog code given in class, see how
Haskell,
Scheme, and
Prolog perform at the task of
finding the first sublist of size 10 of
[1 .. 40] of
the form [2,X,4,Y,Z, ...]
where X+Y+Z=16.
-
Write a Prolog} predicate
memberRem(X,Set,Setp) that holds when
X
is a member of the list Set, and SetP is what
results when X is deleted from Set.
For instance,
memberRem(3,[1,2,3,4],U) succeeds with U=[1,2,4].
-
Write merge sort in Prolog.
For bonus credit, write merge sort that takes a binary predicate
as an additional argument, and uses that to sort.
