/
DList.hs
52 lines (38 loc) · 998 Bytes
/
DList.hs
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
module Main where
import Criterion.Main
newtype DList a = DL { unDL :: [a] -> [a] }
empty :: DList a
empty = DL $ \ l -> l
{-# INLINE empty #-}
singleton :: a -> DList a
singleton x = DL $ \ l -> (x:l)
{-# INLINE singleton #-}
toList :: DList a -> [a]
toList dl = unDL dl []
{-# INLINE toList #-}
infixr `cons`
cons :: a -> DList a -> DList a
cons x xs = DL ((x:) . unDL xs)
{-# INLINE cons #-}
infixl `snoc`
snoc :: DList a -> a -> DList a
snoc xs x = DL (unDL xs . (x:))
{-# INLINE snoc #-}
append :: DList a -> DList a -> DList a
append x y = DL (unDL x . unDL y)
{-# INLINE append #-}
schlemiel :: Int -> [Int]
schlemiel i = go i []
where
go 0 xs = xs
go n xs = go (n - 1) ([n] ++ xs)
constructDlist :: Int -> [Int]
constructDlist i = toList $ go i empty
where
go 0 xs = xs
go n xs = go (n - 1) (singleton n `append` xs)
main :: IO ()
main = defaultMain
[ bench "concat list" $ whnf schlemiel 123456
, bench "concat dlist" $ whnf constructDlist 123456
]