#step function

Introduction to AWS Step Function

Step Function is state-machine based workflow coordination as a service provided by AWS. AWS provides a straightforward way for application developers to create an execution workflow to coordinate the use of multiple AWS Lambda or Amazon Elastic Compute Cloud (EC2) components in distributed applications running on the cloud.

Before digging into AWS Step function, let’s take an example.

You want…

This is the last post about StepFunction module.

Not all programs can be written in the best form the first time around. The API design for StepFunction in the third post seems like someone thought of it in 5 minutes(indeed it was...).

Are there better representation of step function? We don't really need a pair of numbers to specify the interval, we just need to know one end point, and the next end point is implicit.

Why is Monoid required to create a StepFunction?

Why do we require Eq b? It allows one to merge intervals together, and make sure the representation is unique. However, there is no way to express StepFunction a as an instance Applicative if we enforce this requirement.

Let's change the representation for StepFunction. Create a toStepFunction :: (Ord a) => ([a],[b]) -> StepFunction a b, and we should build a inverse fromStepFunction. The first list is a strictly increasing list of end points, and second list is a list of values associated with the first list of points. The second list have one more element to account for all the values before the first end point. Consider the following step function

\[ f(x) = \begin{cases} 0 &\text{if } x < 1 \newline 1 & \text{if } x \in [1,2) \newline 2 & \text{if } x \in [2,3) \newline 3 & \text{if } x > 3 \end{cases} \]

It is constructed by

ghci> toStepFunction ([1,2,3],[0,1,2,3]) Step [(Minimum,0),(Value 1,1),(Value 2,2),(Value 3,3)] ghci> fromStepFunction $ toStepFunction ([1,2,3],[0,1,2,3]) ([1,2,3],[0,1,2,3])

Eq b is no longer a requirement, and the following very redundant StepFunction can be created.

ghci> toStepFunction ([1,2,3],[0,0,0,0]) Step [(Minimum,0),(Value 1,0),(Value 2,0),(Value 3,0)]

To solve this problem, introduce compress:: (Eq b, Ord a) => StepFunction a b -> StepFunction a b.

ghci> compress $ toStepFunction ([1,2,3],[0,0,0,0]) Step [(Minimum,0)]

The module will be more useful if we can make it instances of some popular type classes. Note that $f \circ g$ is a step function if $g$ is a step function. Since $f\circ g$ is just a map over the range, this is a hints that StepFunction a can be implemented as a Functor. Indeed it can be.

Can we make StepFunction a an Applicative? The type of <*> would be StepFunction a (b -> c) -> StepFunction a b -> StepFunction a c. How to make sense of this? We can define it naturally as apply a different function at different intervals.

A concrete example: \[ f(x) = \begin{cases} (\lambda b\to b) &\text{if } x < 0 \newline (\lambda b \to b+1) & \text{otherwise} \end{cases} \] and \[ g(x) = \begin{cases} 0 &\text{if } x < 1 \newline 1 & \text{otherwise} \end{cases} \] \[ (f <*> g)(x) = \begin{cases} 0 &\text{if } x < 0 \newline 1 &\text{if } x < 1 \newline 2 & \text{otherwise} \end{cases} \]

mappend defined on StepFunction a b become a special case of <*>, and the code become much more powerful.

Problem

Rewrite the module, implement fromStepFunction, toStepFunction, compress, eval and make StepFunction a a instance of Applicative.

Future possibilities

Algorithmically, the list based implementation uses $O(n)$ time to transverse the list to find the points of interest. We can use finger trees to improve eval and <*> to $O(\log n)$ and $O(n\log \frac{m}{n})$ time respectively, where $n$ and $m$ are the number of steps in each step function and $n\leq m$.

How can we solve this problem other than call compress manually? I don't have an answer yet.

One could polish this up and upload it to hackage.

Solution

From now on the first solution posted here will be written by me(Chao Xu) unless otherwise specified...

Problem

We will use the StepFunction module to solve Serial Numbers, a problem form ACM-ICPC Mid-Central Regional in 2008. Note this problem took the contestants a while to solve. Let's do this in Haskell.

Solution

Chao Xu's solution. It requires the StepFunction module from the previous exercise and the split package.

The idea is to create a monoid that replace the value each time, and the remaining is just data parsing and output, the StepFunction module takes care of the main logic.

import Data.Monoid import StepFunction import Data.List.Split main :: IO () main = interact process data Code = Code String | Identity deriving (Eq, Show) -- Notice the mappend is nothing more than always take the right value unless -- it is Identity instance Monoid Code where mempty = Identity mappend a b | a == Identity = b | b == Identity = a | otherwise = b process :: String -> String process input = concatMap solve problem where problem = init $ splitOn ["0"] $ lines input -- solve each individual problem solve x = head x ++ "\n" ++ build where build = concatMap writeCommand $ (\(_,t,_)->t) $ toList $ stepFunction sol sol = map readCommand (tail x) readCommand :: String -> (Int, Int, Code) readCommand s = (read a, read b + 1, Code (unwords [c,d])) where [a,b,c,d] = words s writeCommand :: (Int, Int, Code) -> String writeCommand (a, b, Code c) = show a ++ " " ++ show (b-1) ++ " " ++ c ++ "\n" writeCommand (_, _, Identity) = ""

We have a working solution for a step function problem. If a user can arbitrarily do things to the StepFunction data, they could create invalid step functions that still consistent with the type. See how the requirements for the representation of step function as lists are not enforceable through type alone.

One way to solve it is to use module as a form of encapsulation, and then only provide smart constructors and abstract data type.

Problem

Create a module for StepFunction, so the inner working of the StepFunction is unknown to the outside. Only eval, stepFunction and stepFunctionBase are exposed.

stepFunctionBase :: (Ord a, Monoid b, Eq b) => b -> [(a,a,b)] -> StepFunction a b stepFunction :: (Ord a, Monoid b, Eq b) => [(a,a,b)] -> StepFunction a b stepFunction = StepFunctionBase mempty toList :: (Ord a, Monoid b, Eq b) => StepFunction a b-> (b,[(a,a,b)],b)

stepFunctionBase creates a StepFunction by summing the list of intervals to a base interval with value b. toList create a new kind of representation of the StepFunction, the left most element is the value taken from Minimum to the start position of the first interval in the middle. The right most element is the value taken from the end position of the last interval to Maximum.

Examples

ghci> stepFunctionBase [0] [(0,1,[1]),(1,2,[2])] StepFunction [(Minimum,Value 0,[0]),(Value 0,Value 1,[1,0]),(Value 1,Value 2,[2,0]),(Value 2,Maximum,[0])] -- overlap intervals in the input is possible ghci> stepFunctionBase [0] [(0,2,[1]),(1,2,[2])] StepFunction [(Minimum,Value 0,[0]),(Value 0,Value 1,[1,0]),(Value 1,Value 2,[1,2,0]),(Value 2,Maximum,[0])] -- $(a,b,_)$ is a empty interval if $a\geq b$. ghci> stepFunction [(0,-1,[1])] StepFunction [(Minimum,Maximum,[])] ghci> toList $ stepFunctionBase [0] [(0,2,[1]),(1,2,[2])] ([0],[(0,1,[1,0]),(1,2,[1,2,0])],[0]) ghci> toList $ stepFunctionBase [0] [(0,1,[1]),(1,2,[2])] ([0],[(0,1,[1,0]),(1,2,[2,0])],[0])

Solution

Chao Xu's solution.

Following the previous exercise.

Problem

It is not surprising that the step functions form a monoid by adding the values pointwise. Implement the type StepFunction a b, such that instance (Ord x, Monoid y) => Monoid (StepFunction x y). Also implement eval :: StepFunction a b -> a -> b, which evaluates the value of a step function at a point.

Solution

Chao Xu's solution, requires the Interval a b and Bound a type from the previous exercise. Note insertInterval has the arguments switched.

Let type Interval a b = (Bound a, Bound a, b), where Bound a comes from the previous exercise. It will represent a open interval associated with a value.

We define a step function $f:X\to Y$, if $X$ is totally ordered(type class Ord), $(Y,+)$ is a monoid (type class Monoid), and we can express $f(x) = \sum_{i=1}^n y_i \chi_{[a_i,b_i)}(x)$, where $[a_i,b_i)$ are half open interval on $X$, and none of them intersects. To learn more about step functions, see here. (we use a special case of step function, we require the intervals to be half open intervals.)

We can represent a step function as a unique ordered list of disjoint Interval x y, such that:

The end point of a interval is the beginning point of the next one.

The first interval starts with Minimum and the last ends with Maximum.

Consecutive intervals doesn't have the same value.

No empty intervals.

A example, the step function: \[ f(x) = \begin{cases} "birthday" &\text{if } x \in [5,26) \newline "" & \text{otherwise} \end{cases} \]

the representation:

[(Minimum, Value 5, ""), (Value 5, Value 26, "birthday"), (Value 26, Maximum, "")]

Problem

Create the function insertInterval :: (Ord a, Eq b, Monoid b) => Interval a b->[Interval a b]->[Interval a b]. So if s is a representation of $f$, then insert (a,b,y) s = s'. s' would be a representation of $g(x) = y\chi_{[a,b)}(x) + f(x)$.

Example

ghci> insertInterval (Value 5, Value 26, [1]) [(Minimum, Maximum, [0])] [(Minimum,Value 5,[0]),(Value 5,Value 26,[1,0]),(Value 26,Maximum,[0])] ghci> insertInterval (Value 5, Value 26, []) [(Minimum, Maximum, [])] [(Minimum, Maximum, []) ghci> insertInterval (Value 26, Value 27, [1]) [(Minimum, Value 5, []), (Value 5, Value 26, [1]), (Value 26, Maximum, [])] [(Minimum,Value 5,[]),(Value 5,Value 27,[1]),(Value 27,Maximum,[])]

Solution

Chao Xu's solution.

insertInterval :: (Ord a, Eq b, Monoid b) => Interval a b->[Interval a b]->[Interval a b] insertInterval x y = merge (insert x y) where insert _ [] = [] insert (a,b,y) ((a',b',y'):xs) | a >= b' = non [(a',b',y')] ++ insert (a,b,y) xs | b >= b' = non [(a',a,y'),(a,b',y <> y')] ++ insert (b',b,y) xs | b < b' = non [(a',a,y'),(a,b, y <> y'),(b,b',y')] ++ xs where non = filter (\(a,b,_)-> a/=b) merge (h@(a,_,y):h'@(_,b',y'):xs) | y == y' = merge ((a,b',y):xs) | otherwise = h:merge (h':xs) merge x = x

Note