关于算法:COMP5450-检索算法分析

53次阅读

共计 2961 个字符,预计需要花费 8 分钟才能阅读完成。

COMP5450 Retrieval Coursework – Scrolling Animation
The goal of this assignment is to create a simple animation system in Haskell based on printing
out successive lines of characters after a small delay.
Submission
• Please submit a single Haskell file named by your login ID, e.g. dao7.hs.
• Please put comments in your code to show which question you are answering with each
piece of code. This will help the markers.
• You may create auxiliary functions if you like. You may use library functions from Haskell’s
standard library apart from where explicitly stated in Q1.
• Please limit your line lengths to 100 characters max.
Questions We will create simple animations on the command line based on printing a single
line at a time, where that line consists of hyphens – apart from a single character which will
be the‘cursor’which we can‘move’around. Each line of the animation will be described by
a State which is a data type combining an Int describing the position of the cursor, an Int
describing the length of the line, and a character which is used to print the cursor.
data State = MkState Int Int Char
deriving Show
example = MkState 0 5’a’

  1. To generate strings from State values, we first need a function blanks :: Int -> String (5 marks)
    which given an integer input produces a string of hyphen characters whose length is that of
    the input.
    For example, blanks 3 = “—“
    You must write this function from scratch rather than using library functions. Recall, strings
    are just lists of Char.
  2. Based on the description above, and using your answer question 1, write a function of type (10 marks)
    generateLine :: State -> String that converts a state into its string representation for
    the line.
    Here are a few examples that can be used as tests:
    • generateLine (MkState 0 10’a’) = “a———“
    • generateLine (MkState 2 5’.’) = “–.–“
    • generateLine (MkState 3 4’0’) = “—0”
    Note, we can assume that the cursor position is ≥ 0 and less than the line length.
  3. Define a pair of functions goLeft :: State -> State and goRight :: State -> State (10 marks)
    which from a state computes a new state where the position of the cursor is decremented
    or incremented respectively. Ensure the position of the cursor does not become negative nor
    goes beyond the end of the line.
    Here are a few examples that can be used as tests:
    • goRight (MkState 0 5’a’) = MkState 1 5’a’
    • goLeft (MkState 0 5’a’) = MkState 0 5’a’
    1
    • goRight (MkState 4 5’a’) = MkState 4 5’a’
  4. Using your generateLine function, define a function animate :: [State] -> IO () which (10 marks)
    outputs the line of animation for each state every 50 milliseconds.
    Use the threadDelay :: Int -> IO () function which can be imported from the Control.Concurrent
    module, where threadDelay n delays execution as an IO computation for n microseconds.
    For example, animate [example, goRight example, goRight (goRight example)] should
    produce:
    *Main> animate [example, goRight example, goRight (goRight example)]
    a—-
    -a—
    –a–
  5. Define a function pingPong :: State -> [State], which given a state, produces an infinite (15 marks)
    list of states where the position of the cursor is moved backwards and forwards from the lowerlimit
    to the upper-limit, with each state in the list having the position either incremented or
    decremented from the previous.
    For example, take 7 (pingPong (MkState 0 3’a’)) = [MkState 0 3’a’,MkState 1 3
    ’a’,MkState 2 3’a’,MkState 1 3’a’,MkState 0 3’a’,MkState 1 3’a’,MkState 2 3
    ’a’].
    You should then be able to see the following behaviour in ghci:
    *Main> animate (take 20 (pingPong example))
正文完
 0