Structure of the Final:

• 7 problems, 1 more than the midterm. 

• Outside of using a higher-order function you wrote earlier, you will NOT have to solve a problem specifically using HOFs, list comprehensions, or recursion.

 1 Describe A Function, 1-2 Write A Function:

• Write a function given a description, or describe a function given an implementation.

  • A good description focuses on what the function computes, not how it computes it.

• Function(s) over lists

• Function(s) over already defined algebraic data types (as input, output, or both.)

• An IO action: (i.e. like prompt :: String -> IO String)

prompt str = 

do putStr (str ++ “: ”)

     answer <- getLine

     return answer

2-3 Define and/or Use an Abstraction:

• Define an algebraic data-type and use it

• Define a higher order function and use it (Like "iters" on midterm)

• Define or use a type class, like "Boolish." Some (but not all) of: 

  • Define a typeclass given examples

  • Make instances of a given typeclass (i.e. String and Int)

  • Write a function that uses a given typeclass.

1 Algorithmic Problem

• A hard problem to solve, I want to see how far you get. Outline any limitations of your solution if you are aware of them.

• I.E. largestSequence from midterm.

1 Decomposition Problem

• You will be given a problem that would take too much code to fit on an exam.

  • Similar to the final problem on any project: kMeans is a good example

  • Break the problem apart into logical helper functions.

    • moveCenters, assignPoints, startClusters

    • You should decompose into 3-5 helper functions.

  • Write a solution, in code, that uses helper functions to solve the larger problem.

  • Then describe, but do not write the helper functions

    • Give a type signature and a 1-2 sentence description of what the function does. Do not describe how the function works.

    • Think of the comments above each function on the projects.

    • An example is excellent!

  • A helper function not used in the main solution, but in another helper function, is acceptable but not ideal. Be sure to mention where it is used.

Content Covered on the Final:

Topics that were on midterm, will be on the final

• Recursion

• Higher-order functions (Defining and using a new one)

• Lists, Tuples

New topics since the midterm

• Data type declarations/Algebraic Data Types

  • Defining, including constructors with values

  • Using with pattern matching

  • Polymorphic types

  • Recursive types (i.e. trees)

    • Write a function given a definition (abstract syntax tree, decision tree)

    • Define a recursive type which is a kind of tree.

• IO Monad

  • Building actions

  • Composing IO actions/do blocks 

    • “Unwrap” things, only when they will be “re-wrapped”.

  • Building more complex IO actions

  • Recursive actions

  • You will be given the signatures of basic IO actions

  • Not File IO, arguments, or GetOpt.

• Typeclasses

  • Class declarations

  • Instance declarations

  • Functions that take typeclasses as  inputs (like Eq a => or Boolish a =>)

• Solving games  - i.e. project 2 (bestPlay) and group project (milestone 2)

Topics You Can Avoid:

These topics  may show up in given code on the final, or be helpful for solving problems, but you do not have to use them to solve a problem

• List comprehensions - can always replace with recursion

• Built-in higher-order functions

• Lambdas  - can always replace with a "let....in"

• The Maybe monad/do blocks with Maybes - can always replace with
  case expr of
  Nothing -> Nothing
  Just x -> ....