Versions Compared

Old Version 5

changes.mady.by.user Robert Cartwright

Saved on

compared with

New Version 6

changes.mady.by.user Robert Cartwright

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

  • Write the most general (parametric) contract for the following function:
    Code Block
    ; compose : ?
; Purpose: (compose f g) returns the result of composing functions f and g: x |-> f(g(x))
  (define (compose f g)
    (lambda (x) (f (g x))))
  • Write the same merge-sort mergesort function as described in exercise 26.1.2, except decompose the problem "top-down" rather than "bottom-up". You will need to define a function split: (listOf list-of number) -> (listOf listof (listOf number)) that partitions its input into two lists of approximately (+/- 1) the same length in O(thumbs down) time where n is the length of the input list. (split l) returns a list containing two lists of numbers. After splitting the list in half, mergesort recursively sorts each half and then merges them together.