I got'cher DList right here!

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
module Control.DList where

import Control.Arrow (app)
import Control.Monad
import Control.Monad.Trans.Writer
import Data.Monoid

infixr 5 |>
infixl 5 <|

{--

Your basic difference list, from Haskell to Idris, and back
This answers the Haskell exercise posed at http://lpaste.net/107593

 --}

data DList a = DL { unDL :: [a] -> [a] }

cons :: a -> [a] -> [a]
cons a list = a : list

(<|) :: DList a -> a -> DList a
dlist <| a = DL $ unDL dlist . cons a

(|>) :: a -> DList a -> DList a
a |> dlist = DL $ cons a . unDL dlist

emptyDL :: DList a
emptyDL = DL id

dlToList :: DList a -> [a]
dlToList dlist = unDL dlist []

-- added a fromList for difference lists to start from somewhere

dl :: [a] -> DList a
dl = DL . (++)

dl' :: a -> DList a -- your monadic return
dl' x = dl [x]

-- DLists are monoidal (perfect for writing to *cough* Writer *cough*)

instance Monoid (DList a) where
   mempty  = emptyDL
   d1 `mappend` d2 = DL (unDL d1 . unDL d2)

samp :: Writer (DList Char) () -- from Writer w a
samp = (\f twoB -> mapM_ f [twoB, " or not ", twoB]) (tell . dl) "to be"

-- *Control.DList> dlToList $ snd $ runWriter samp ~> "to be or not to be"

-- So now let's make DList a monad
-- which means we have to make it a Functor, then an Applicative one
-- You know: because monads are functors.
-- No, they aren't but in Haskell they are required to be, because reasons.

instance Monad DList where
   return = pure
   difflist >>= f = {-- ugh! --} mconcat . map f $ dlToList difflist

-- but to be a monad these days, you MUST be applicative, so ...

instance Applicative DList where
   pure = dl'
   dlfs <*> dlargs = dl $ zipWith (curry app) (dlToList dlfs) (dlToList dlargs)

-- but applicative needs to be a functor, so ...

instance Functor DList where
   fmap f = dl . map f . dlToList

-- and while we're at it, let's make DList a Foldable instance
{--
Okay, last week, we looked at improving the views on DList so that we could
make it a monad, so that it could participate with MultiMap, which has a
requirement of monadicity on the element-container-class.

But is that the 'right' improvement?

Looking at MultiMap, it's not so that a contain should be a monad, because
what is the usage for these containers? Their monadicity?

No, it's their foldability.

This exercise is inspired by @argumatronic xxx.

What is a Foldable instance?

(quick lookup of Data.Foldable)

A Foldable instance is something that which can be folded.

(audience, sarcastically: Thank you, geophf)

me: yer welcks.

So, (... or maybe we need to ba Traversable, too?)

(... I'll put more thought into this ... laterz).

So, if what we need, really, is a Foldable instance (not a Monad), then we need
to make DList a Foldable instance, too.

Today's Haskell exercise: declare DList to be Foldable and define the Foldable
functions for it. --}

instance Foldable DList where
   foldr f z = foldr f z . dlToList

-- let's talk Traversibility, now:

{-- a solution to the problem posted at http://lpaste.net/4868288594713772032

So, we made DList a Foldable instance, all for @argumatronic, and she was 
grateful for the source material for @HaskellBook ...

(geophf waits for the influx of gratitude)

... but then she was all like, "Phfeh! Foldable is so yesterday! Traversable
is where it's at! Get with the times!"

So, there's that.

So, Traversable. What is it?

traversable, adj.: that which can be traversed, see traversable.

(audience, sarcastic: gee! thanks, geophf!)

(geophf: yer welcks)

Okay, but seriously, looking at the documentation for Data.Traversable, we see
that 

class (Functor t, Foldable t) => Traversable t where ...

Well, as we've done yesterday and the proceeding week, we've already made DList
a Functor (and an Applicative Functor, no less, which will come in (very)
handy today) and, yesterday, made it Foldable, so we've met the prerequisites
of being able to make DList Traversable.

What is the power of traversibility? Well, if you have some arbitrary type, t,
that's a Traversable type, then you know you can map(M) or sequence over it...

... and as we learned in the '70s, being able to map over a type is a very
powerful and useful thing to have.

So, let's do this for DList: let's make DList a Traversable instance.

Generally, with Applicative Functors, as the minimally-complete definition
is traverse or sequenceA.  Let's do this. --}

instance Traversable DList where
   traverse f = (pure dl <*>) . traverse f . dlToList

-- And if we just want a feelz, yo:

instance Show (DList a) where show = const "a DList"