Safe Haskell	Safe

Lab3Help

Contents

Data types
Parsing of stop/line files
Tries

Description

Some data structures and functions related to stops and lines.

Synopsis

Data types

data Stop

Description of a (bus/tram/…) stop.

Constructors

Stop
Fields name ∷ String The stop's name. position ∷ (Integer, Integer) Coordinates (x, y). Invariant: The coordinates range from 0 to 1000.

Instances

Show Stop

data LineTable

Description of a line.

Constructors

LineTable
Fields lineNumber ∷ Integer The line number. stops ∷ [LineStop] Stops (in the order in which they are visited). Invariant: The list contains at least one element.

Instances

Show LineTable

data LineStop

Description of a stop, as part of a line.

Constructors

LineStop
Fields stopName ∷ String The stop's name. time ∷ Integer The travel time (in minutes) from the previous stop. Invariant: A non-negative number, 0 if this is the first stop.

Instances

Show LineStop

Parsing of stop/line files

readStops ∷ FilePath → IO (Either String ([Stop], Trie Char))

Tries to read a list of stops from the given file.

If the list is read successfully, then a trie with all the stop names is returned along with the list.

If an error is encountered, then an error message is returned (Left msg).

readLines

Arguments

∷ Trie Char	Known stop names. If an unknown stop is encountered, then an error message is returned.
→ FilePath
→ IO (Either String [LineTable])

Tries to read information about lines from the given file.

If an error is encountered, then an error message is returned (Left msg).

Tries

data Trie a

Tries.

member ∷ Ord a ⇒ [a] → Trie a → Bool

Is the list a member of the trie?

Time complexity: O(n c log v), where n is the length of the list, c is an upper bound on the time complexity of a comparison, and v is the number of distinct list elements in the trie. For Char this can be simplified to O(n).