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
module Control.DList where

import Data.Monoid
import Control.Monad.Writer

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"
22:18: Warning: Redundant bracket
Found:
(unDL dlist) . (cons a)
Why not:
unDL dlist . (cons a)
22:18: Warning: Redundant bracket
Found:
(unDL dlist) . (cons a)
Why not:
(unDL dlist) . cons a
25:18: Warning: Redundant bracket
Found:
(cons a) . (unDL dlist)
Why not:
cons a . (unDL dlist)
25:18: Warning: Redundant bracket
Found:
(cons a) . (unDL dlist)
Why not:
(cons a) . unDL dlist