1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
module DeferredFolds.Types where
-- |
-- A projection on data, which only knows how to execute a strict left-fold.
--
-- It is a monad and a monoid, and is very useful for
-- efficiently aggregating the projections on data intended for left-folding,
-- since its concatenation (`<>`) has complexity of @O(1)@.
--
-- [Intuition]
--
-- The intuition for this abstraction can be derived from lists.
--
-- Let's consider the `Data.List.foldl'` function for lists:
--
-- >foldl' :: (b -> a -> b) -> b -> [a] -> b
--
-- If we rearrange its parameters we get
--
-- >foldl' :: [a] -> (b -> a -> b) -> b -> b
--
-- Which in Haskell is essentially the same as
--
-- >foldl' :: [a] -> (forall b. (b -> a -> b) -> b -> b)
--
-- We can isolate that part into an abstraction:
--
-- >newtype Unfoldl a = Unfoldl (forall b. (b -> a -> b) -> b -> b)
--
-- Then we get to this simple morphism:
--
-- >list :: [a] -> Unfoldl a
-- >list list = Unfoldl (\ step init -> foldl' step init list)
--
-- We can do the same with say "Data.Text.Text":
--
-- >text :: Text -> Unfoldl Char
-- >text text = Unfoldl (\ step init -> Data.Text.foldl' step init text)
--
-- And then we can use those both to concatenate with just an @O(1)@ cost:
--
-- >abcdef :: Unfoldl Char
-- >abcdef = list ['a', 'b', 'c'] <> text "def"
--
-- Please notice that up until this moment no actual data materialization has happened and
-- hence no traversals have appeared.
-- All that we've done is just composed a function,
-- which only specifies which parts of data structures to traverse to perform a left-fold.
-- Only at the moment where the actual folding will happen will we actually traverse the source data.
-- E.g., using the "fold" function:
--
-- >abcdefLength :: Int
-- >abcdefLength = fold Control.Foldl.length abcdef
newtype Unfoldl a = Unfoldl (forall x. (x -> a -> x) -> x -> x)
-- |
-- A monadic variation of "DeferredFolds.Unfoldl"
newtype UnfoldlM m a = UnfoldlM (forall x. (x -> a -> m x) -> x -> m x)
-- |
-- A projection on data, which only knows how to execute a right-fold.
--
-- It is a monad and a monoid, and is very useful for
-- efficiently aggregating the projections on data intended for right-folding,
-- since its concatenation (`<>`) has complexity of @O(1)@.
--
-- [Intuition]
--
-- The intuition of what this abstraction is all about can be derived from lists.
--
-- Let's consider the `Data.List.foldr` function for lists:
--
-- >foldr :: (a -> b -> b) -> b -> [a] -> b
--
-- If we rearrange its parameters we get
--
-- >foldr :: [a] -> (a -> b -> b) -> b -> b
--
-- Which in Haskell is essentially the same as
--
-- >foldr :: [a] -> (forall b. (a -> b -> b) -> b -> b)
--
-- We can isolate that part into an abstraction:
--
-- >newtype Unfoldr a = Unfoldr (forall b. (a -> b -> b) -> b -> b)
--
-- Then we get to this simple morphism:
--
-- >list :: [a] -> Unfoldr a
-- >list list = Unfoldr (\ step init -> foldr step init list)
--
-- We can do the same with say "Data.Text.Text":
--
-- >text :: Text -> Unfoldr Char
-- >text text = Unfoldr (\ step init -> Data.Text.foldr step init text)
--
-- And then we can use those both to concatenate with just an @O(1)@ cost:
--
-- >abcdef :: Unfoldr Char
-- >abcdef = list ['a', 'b', 'c'] <> text "def"
--
-- Please notice that up until this moment no actual data materialization has happened and
-- hence no traversals have appeared.
-- All that we've done is just composed a function,
-- which only specifies which parts of data structures to traverse to perform a right-fold.
-- Only at the moment where the actual folding will happen will we actually traverse the source data.
-- E.g., using the "fold" function:
--
-- >abcdefLength :: Int
-- >abcdefLength = fold Control.Foldl.length abcdef
newtype Unfoldr a = Unfoldr (forall x. (a -> x -> x) -> x -> x)
newtype UnfoldrM m a = UnfoldrM (forall x. (a -> x -> m x) -> x -> m x)
|
