Difference between revisions of "PFP Homework 1"
Jump to navigation
Jump to search
(Created page with "= PFP Homework 1 = == Automatons == * Create a function, that sorts an array using quicksort algorithm [https://en.wikipedia.org/wiki/Quicksort <code>quicksort</code>]. Ins...") |
|||
| Line 1: | Line 1: | ||
| − | = | + | = Automatons = |
| + | Let say, we have a finite automaton defined as: <math>(Q,I,F,q0,F )</math> | ||
| + | |||
| + | <syntaxhighlight lang="Haskell"> | ||
| + | type Transition = (Int, Char, Int) | ||
| + | type Automaton = (Int, String, [Int], Int, [Transition ]) | ||
| + | </syntaxhighlight> | ||
| + | |||
| + | where states are coded with numbers from 0 to n | ||
| + | |||
| + | <syntaxhighlight lang="Haskell"> | ||
| + | ex1 :: Automaton | ||
| + | ex1 = (3, [0], [2], "ab", [(0,'a',1), (0,'b',0), (1,'a',1), (1,'b',2), (2,'a',1), (2,'b',0)]) | ||
| + | |||
| + | ex2 :: Automaton | ||
| + | ex2 = (3, [0], [2], "ab", [(0,'a',1), (0,'a',0), (0,'b',0), (1,'b',2)]) | ||
| + | </syntaxhighlight> | ||
| − | |||
* Create a function, that sorts an array using quicksort algorithm [https://en.wikipedia.org/wiki/Quicksort <code>quicksort</code>]. Inside, you must use the mutable array [https://hackage.haskell.org/package/array-0.5.4.0/docs/Data-Array-ST.html#t:STArray <code>STArray</code>]. | * Create a function, that sorts an array using quicksort algorithm [https://en.wikipedia.org/wiki/Quicksort <code>quicksort</code>]. Inside, you must use the mutable array [https://hackage.haskell.org/package/array-0.5.4.0/docs/Data-Array-ST.html#t:STArray <code>STArray</code>]. | ||
<syntaxhighlight lang="Haskell">quickSort :: Array Int Int -> Array Int Int</syntaxhighlight> | <syntaxhighlight lang="Haskell">quickSort :: Array Int Int -> Array Int Int</syntaxhighlight> | ||
Revision as of 11:50, 10 October 2023
Automatons
Let say, we have a finite automaton defined as:
type Transition = (Int, Char, Int)
type Automaton = (Int, String, [Int], Int, [Transition ])
where states are coded with numbers from 0 to n
ex1 :: Automaton
ex1 = (3, [0], [2], "ab", [(0,'a',1), (0,'b',0), (1,'a',1), (1,'b',2), (2,'a',1), (2,'b',0)])
ex2 :: Automaton
ex2 = (3, [0], [2], "ab", [(0,'a',1), (0,'a',0), (0,'b',0), (1,'b',2)])
- Create a function, that sorts an array using quicksort algorithm
quicksort. Inside, you must use the mutable arraySTArray.
quickSort :: Array Int Int -> Array Int Int
ghci> elems $ quickSort $ listArray (0,5) [8,4,9,6,7,1]
[1,4,6,7,8,9]
