1Structured Loops (Direct Style)
2===============================
6 -- | Result of taking a single step in a stream
8 Yield :: a -> s -> Step s a
11 -- | Representation of a loop, step and state. Step returns the next value and
12 -- the next state. We iterate on the state to keep producing more values.
13 data Stream m a = forall s. Stream (s -> m (Step s a)) s
20 nil :: Monad m => Stream m a
21 nil = Stream (const (return Stop)) ()
24 fromPure :: Applicative m => a -> Stream m a
25 fromPure x = Stream step True
29 step True = return $ Yield x False
30 step False = return $ Stop
32 fromList :: Applicative m => [a] -> Stream m a
33 fromList = Stream step
37 step _ (x:xs) = pure $ Yield x xs
45 foldrM :: Monad m => (a -> m b -> m b) -> m b -> Stream m a -> m b
46 foldrM f z (Stream step state) = go state
53 Yield x s -> f x (go s)
56In the above code the state is explicit and being threaded around in a
57recursive loop. The state from the previous iteration is to be consumed
58by the next iteration to generate the next value. This mandates a
59closed recursive loop. This is straightforward translation of imperative
60loops to functional paradigm.
67 mapM :: Monad m => (a -> m b) -> Stream m a -> Stream m b
68 mapM f (Stream step state) = Stream step' state
75 Yield x s -> f x >>= \a -> return $ Yield a s
81Some operations like "drop" (uniq, intersperse, deleteBy, insertBy) may
82have to introduce a branch in the code by wrapping the state in another
85 drop :: Monad m => Int -> Stream m a -> Stream m a
86 drop n (Stream step state) = Stream step' (state, Just n)
95 Yield _ s -> step' (s, Just (i - 1))
97 | otherwise = step' (st, Nothing)
99 step' (st, Nothing) = do
103 Yield x s -> Yield x (s, Nothing)
106Note that the branch is always checked for every element in the stream.
107It is still quite efficient because the code fuses.
109We should use rewrite rules to fuse such consecutive operations together as
110they introduce branching which could be costly.
115Composing two independent loops together is not scalable, we need
116to create a wrapper state, wrapping the state of the old stream:
120 cons :: Monad m => m a -> Stream m a -> Stream m a
121 cons m (Stream step state) = Stream step1 Nothing
125 step1 Nothing = m >>= \x -> return $ Yield x (Just state)
130 Yield a s -> Yield a (Just s)
133As we keep consing we keep creating more layers wrapping the state in
134``Maybe``. These layers need to be traversed every time we run the step
135function of the composed stream. In the above example ``step1`` needs
136to always branch on ``Nothing/Just`` to reach to the wrapped stream. More
137layers we add the more branching needs to occur to generate an element
138of the stream. If we have ``n`` "cons" operations we need to go through:
140* 1 branch at the top level to generate the first element
141* 2 branches to generate the next element
142* 3 branches to generate the third element
143* n branches to generate the nth element
145The total number of branches that we need to take is: ``1 + 2 + 3 ... n`` i.e.
146``n * (n + 1)/2 = O(n^2)`` where ``n`` is the number of cons operations.
148Conceptually, to avoid the introduction of a branch we could use a
149mutable step function and state to modify step1/state after yielding
150the first element. The next time we call it, it would be a different
151function that i.e. "step" and its state "st". However, that would introduce
152an indirection and mutability. There is a better way to do it with
153immutability i.e. CPS.
158In the direct representation we represented a stream using a step and a
159state. This model requires us to iterate the step on the state creating
160an explicit loop. The state machine implemented by the step function is
161incrementally modified by adding new layers in the state which introduce
162branches to be traversed every time we go through the loop.
166 newtype Stream m a = Stream
167 { runStream :: forall r. (a -> Stream m a -> m r) -> m r -> m r }
169Here we represent the stream as a single function. Instead, the
170function is provided with functions to be called next.
172Notice, the function does not have to be called again and again to
173iterate on a state for generating new values. Therefore, there is no
174closed recursion. There is no explicit loop.
176We (the current ``runStream`` function) can choose which one of the supplied
177functions (continuations) to call next. If we decide to terminate
178the stream execution we call the "stop" continuation. If we decide to
179generate a value we call the "yield" continuation.
181A stream execution is composed of a progression of such continuations
182until one of those decides to call the stop continuation. It is a
183composition of functions, a tree of functions composed together.
188The yield continuation is provided with the generated value "a" and the
189"Stream m a", the function representing the rest of the stream. Notice
190that the stream function is done with one shot execution, there is no
191closed loop or recursion, the future execution of the stream is the
192responsibility of the continuation.
194The continuation consumes the element "a" and then proceeds to call
195"Stream m a" using a "yield" and "stop" continuation. By modifying the
196"yield" and "stop" continuations that it passes to call "Stream m a", it
197can control the execution of the stream.
205 nil = Stream $ \_ stp -> stp
207 fromPure :: a -> Stream m a
208 fromPure a = Stream $ \yield _ -> yield a nil
210 cons :: a -> Stream m a -> Stream m a
211 cons a r = Stream $ \yld _ -> yld a r
213 fromList :: [a] -> Stream m a
214 fromList = Prelude.foldr cons nil
221 foldrM :: (a -> m b -> m b) -> m b -> Stream m a -> m b
222 foldrM step acc m = go m
226 yieldk a r = step a (go r)
227 in runStream yieldk stop m1
229Note that unlike in direct style fold, there is no generator state being
230threaded around here instead the function yielded by the continuation is
238 map :: (a -> b) -> Stream m a -> Stream m b
245 let yieldk a r = yld (f a) (go r)
246 in runStream yieldk stp m1
248In direct style we had to examine the constructors to determine the
249current state and execute code based on that. Here, we have to make
250the next function call at each step. The former is much more efficient
251because the compiler can optimize well to remove the constructors and
252generate code with direct branches not involving the constructors. On
253the other hand placing a function call is costlier. Though in some cases
254it can be avoided by using foldr/build fusion but not always.
261 drop :: Int -> Stream m a -> Stream m a
262 drop n = Stream $ go n
268 let yieldk _ r = runStream yld stp $ go (n1 - 1) r
270 then runStream yld stp m1
271 else runStream yieldk stp m1
273This shows a crucial difference between direct style and CPS. In direct
274style we have to always check for the branch to determine if we are
275dropping the elements or consuming. In this case we can see that once
276we have taken the "then" path we never have to check the condition "n1
277<= 0", it is out of the way.
279Basically CPS provides us the ability to take an exit path and forget
280about the past code forever. So if we have a million "drop" composed
281together CPS would have no problem, after the final drop there won't be
282any branches in the way whereas direct style would introduce a million
283branches to be traversed forever.
290 cons :: a -> Stream m a -> Stream m a
291 cons a r = Stream $ \yld _ -> yld a r
293Unlike in direct style representation, the performance of stream
294generation is independent of the number of "cons" operations. There is
295no quadratic complexity, we simply call the next continuation at each
298Similarly appending streams is independent of number of appends.
302 serial :: Stream m a -> Stream m a -> Stream m a
309 let stop = runStream yld stp m2
310 yieldk a r = yld a (go r)
311 in runStream yieldk stop m
313Interleaved production and consumption
314--------------------------------------
316In the direct style we have an explicit stream generator. A consumer
317generates values using the generator and consumes them. In CPS the
318consumer and generator are interleaved. The ``runStream`` function is a
319generator and the "yield" continuation is a consumer. The consumer then
320calls the generator again and so on.
325The direct style representation is like a structured loop with well
326defined exit points. Whereas the CPS representation can exit from
327anywhere. Therefore, exception handling and resource management in
328direct style is much simpler to implement.
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list