git.iko.soy/streamly
on a4fa2d3 help sign in
streamly/examples/MergeSort.hs
40 lines 1.1 kB history raw
1{-# LANGUAGE FlexibleContexts #-}
3import Data.Word
4import System.Random (getStdGen, randoms)
5import Data.List (sort)
6import Streamly
7import Streamly.Prelude (yieldM)
8import qualified Streamly.Prelude as A
10getSorted :: Serial Word16
11getSorted = do
12 g <- yieldM getStdGen
13 let ls = take 100000 (randoms g) :: [Word16]
14 foldMap return (sort ls)
16-- | merge two streams generating the elements from each in parallel
17mergeAsync :: Ord a => Serial a -> Serial a -> Serial a
18mergeAsync a b = do
19 x <- yieldM $ mkAsync a
20 y <- yieldM $ mkAsync b
21 merge x y
23merge :: Ord a => Serial a -> Serial a -> Serial a
24merge a b = do
25 a1 <- yieldM $ A.uncons a
26 case a1 of
27 Nothing -> b
28 Just (x, ma) -> do
29 b1 <- yieldM $ A.uncons b
30 case b1 of
31 Nothing -> return x <> ma
32 Just (y, mb) ->
33 if y < x
34 then return y <> merge (return x <> ma) mb
35 else return x <> merge ma (return y <> mb)
37main :: IO ()
38main = do
39 xs <- A.toList $ mergeAsync getSorted getSorted
40 print $ length xs