What to Hand In (see also: example project solution)

• A listing of the Haskell script you write for your project, following the required standards.
• A session transcript in which you show that your function operates correctly on arguments chosen to demonstrate the function's capabilities.
• Explain (handwritten on the transcript) what aspects of the function's behavior are illustrated by each of your choices of demonstration examples.
• A logical argument showing that your function satisfies the property specified in the problem statement. If your definition uses functions from software supplied on the class web site, your argument may assume the truth of any properties of those functions stated in the commentary associated with their definitions.

Four projects are described below. Different team members do different projects. Team members listed first or fifth on their team's roster must do Project 3A; those listed second or sixth, Project 3B; third, Project 3C; fourth, Project 3D.

Project 3A - packaging lines
Define a function called linePackets that splits a sequence of strings (words) supplied in the second argument into a sequence of sequences of strings (line packets) that fit within a length limit supplied in the first argument, but would not fit if they contained any additional strings.

The delivered sequence of packets must satisfy the following properties:

• Each line packet p in the sequence delivered by linePackets must have the property that (length . unwords) p <= lengthLimit Exception: If any word in the argument containing the words is longer than the limit, then that word, by itself, forms an outsized line packet.
• If p is a packet in the delivered sequence and w is the first word in the next packet in the sequence, then (length . unwords) (p ++ [w]) > lengthLimit
• For any non-empty ws::[String] and n::Int with n > 0, concat(linePackets n ws) = ws

Examples

  linePackets 12 ["The", "purpose", "of", "computing"]
    = [["The", "purpose"], ["of computing"]]
  linePackets 6 ["is", "insight,", "not", "numbers."]
    = [["is"], ["insight,"], ["not"], ["numbers."]]
  linePackets 14 (repeat "blah") = repeat["blah", "blah", "blah"]

If k::Int and ws::[String] and

(1) ps = linePackets k ws and

(2) p is an element of ps and

(3) sum[length w | w <- p] + length(p) - 1 > k,

then length(p) = 1.

Examples:

  justify 12 ["The", "purpose"] = "The  purpose"
  justify 12 ["of", "computing"] = "of computing"
  justify 6 ["is"] = "is    "
  justify 6 ["insight,"] = "insight,"
  justify 52 ["The", "purpose", "of", "computing",
              "is", "insight,", "not", "numbers."] =
           "The  purpose  of  computing is insight, not numbers."

If ws::[String] and length(ws) > 1 and length(unwords ws) <= n,

then length(justify n ws) = n

Project 3C - arranging words in columns
Define a function called columns that, given a number indicating how many columns are desired and a sequence of strings (words), delivers a sequence of sequences (columns) of words such that the first column contains the initial segment of the given sequence of words, the second column contains the next segment, and so on. All columns must have exactly the same length; if the number of words is not a multiple of the number of columns, then pad the bottom of some of the columns with an empty string.

Note: Each column must consist entirely of words from the argument, except that the last element of the column may be a pad; the number of padded columns must be less than the number of columns.

Examples

   columns 3 ["Bool", "Char", "Int", "Float",
              "Double", "Integer", "String"] =
                                [["Bool", "Char", "Int"],
                                 ["Float", "Double", ""],
                                 ["Integer", "String", ""]]
   columns 3 ["Bool", "Char", "Int", "Float", "Double", "Integer"] =
                                [["Bool", "Char"],
                                 ["Int", "Float"],
                                 ["Double", "Integer"]]
   columns 3 ["Bool", "Char", "Int", "Float", "Double"] =
                                [["Bool", "Char"],
                                 ["Int", "Float"],
                                 ["Double", ""]]

If n::Int, n >= 1, and ws::[String],

then ws is a subsequence of concat(columns n ws)

Project 3D - making a table
Define a function called table that, given a number (the first argument) indicating how many spaces to put between columns and a sequence of sequences of strings (columns of words), all columns having exactly the same length, delivers a sequence of strings (rows) such that each row is formed by concatenating one word from each column in such a way that the words from the first column occur at the beginnings of the rows, the words from the second column follow the words from the first column in their respective rows, then the words from the third column and so on.

The rows must be arranged so that the columns "line up" and so that the minimum gap between each adjacent pair of columns is the number supplied as the first argument. That is, if the second word in the first row begins at the k-th character in the string representing that row, then the second word in all the other rows must begin at the k-th character of the row. Furthermore, number of spaces between the end of the first and second words on the row must be exactly equal to the second argument in the invocation of the table function. Other words in the rows must line up in an analogous way and follow the same constraint on the number of spaces between words in one column and words in the next column. All of the rows must contain exactly the same number of characters. Use spaces to separate the words of a row and to pad out the rows to make them all the same length.

Examples

  table 3 [["Char", "String", "Bool"],
           ["Int", "Integer", "Rational"],
           ["Float", "Complex Float", "Double"]] =
      ["Char     Int        Float        ",
       "String   Integer    Complex Float",
       "Bool     Rational   Double       "]
  table 1 [["Char", "String", "Bool"],
           ["Int", "Integer", "Rational"],
           ["Float", "Complex Float", "Double"]] =
      ["Char   Int      Float        ",
       "String Integer  Complex Float",
       "Bool   Rational Double       "]
  table 0 [["Char", "String", "Bool"],
           ["Int", "Integer", "Rational"],
           ["Float", "Complex Float", "Double"]] =
      ["Char  Int     Float        ",
       "StringInteger Complex Float",
       "Bool  RationalDouble       "]

All the rows of a table are exactly the same length. That is,

If n::Int, n >= 0, cs::[[String]],

and r::String and s::String are any two elements of table n cs

(that is, [..., r, ..., s, ...] = table n cs)

then length(r) = length(s)

Ground Rules

• You may use any aspects of Haskell covered in Lessons 1-14 of the Haskell textbook, plus any operator or function covered in class. In particular, you may find the following functions useful: length, concat, null, fst, snd, max, maximum, sum, signum.
• You may also use any of the functions in the modules SequenceUtilities and IOutilities, supplied on the class web site.
  Download these modules anew. They have been augmented for this project.
• Functions from these modules that you may find especially helpful include: takeUntil, prefixes, multiplex, reps, spaces, blocks, leftJustify, transpose, and concatWithSpacer.
• The Project Style Guide contains one new requirement for this project and subsequent ones. You must write type specifications to accompany each definition.
• You may assume the correctness of the following theorems, which may be of some assistance in proving the properties specified in some of the projects.

  Theorem D-concat

  if xss::[[a]] and yss::[[a]] for some type a, then

  concat(xss ++ yss) = concat xss ++ concat yss

  Theorem D-length

  if xs::[a] and ys::[a] for some type a, then

  length(xs ++ ys) = length xs + length ys

  Theorem C

  if xss::[[a]] for some type a, then

  length(concat xss) = sum[length xs | xs <- xss]

  Theorem U

  if ws::[String], then

  (length . unwords) ws = sum[length w | w <- ws] + max 0 (length ws - 1)

  Theorem M

  if xss::[[a]] for some type a, then multiplex(xss) and concat(xss) contain the same elements, possibly arranged in a different order. That is, there is some rearrangement of the order of the elements in the sequence concat(xss), call the rearranged sequence ys, such that ys = multiplex(xss)

  Theorem S

  if n::Int with n >= 0 and xs::[a] for some type a and (prefix, suffix) = splitAt n xs, then

  xs = prefix ++ suffix