Skip to content

Commit 72a378a

Browse files
edskoedsko
committed
Don't use Strings (for better profiling data)
1 parent fcfc19d commit 72a378a

File tree

5 files changed

+154
-37
lines changed

5 files changed

+154
-37
lines changed

‎not-bytestring/not-bytestring.cabal

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,4 +30,5 @@ library
3030
hs-source-dirs: src
3131
ghc-options: -Wall
3232
extensions: GeneralizedNewtypeDeriving,
33-
DeriveDataTypeable
33+
DeriveDataTypeable,
34+
BangPatterns

‎not-bytestring/src/Data/NotByteString.hs

Lines changed: 50 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
module Data.NotByteString
2-
( ByteString
2+
( ByteString(Nil, Cons)
33
, fromString
44
, toString
55
, fromByteString
@@ -9,42 +9,77 @@ module Data.NotByteString
99
, null
1010
, empty
1111
, splitAt
12+
, foldr
13+
, foldl'
14+
, (++)
1215
) where
1316

14-
import Prelude hiding (length, null, concat, splitAt)
15-
import qualified Prelude (length, null, splitAt)
16-
import Data.Binary (Binary)
17+
import Prelude hiding (length, null, concat, splitAt, foldr, (++), reverse)
18+
import qualified Prelude (length, null, splitAt, foldr)
19+
import Data.Binary (Binary(get, put))
1720
import Data.Typeable (Typeable)
1821
import qualified Data.ByteString as BS (ByteString)
19-
import qualified Data.ByteString.Char8 as BSC (pack, unpack)
20-
import Control.Arrow ((***))
22+
import qualified Data.ByteString.Char8 as BSC (pack, foldr)
23+
import Control.Applicative ((<$>))
2124

22-
newtype ByteString = NotByteString { toString :: String }
23-
deriving (Eq, Ord, Binary, Typeable)
25+
data ByteString = Nil | Cons !Char !ByteString
26+
deriving (Typeable, Eq, Ord)
2427

2528
instance Show ByteString where
2629
show = toString
2730

31+
instance Binary ByteString where
32+
get = fromByteString <$> get
33+
put = put . toByteString
34+
35+
foldl' :: (a -> Char -> a) -> a -> ByteString -> a
36+
foldl' f = go
37+
where
38+
go !acc Nil = acc
39+
go !acc (Cons c cs) = go (acc `f` c) cs
40+
41+
foldr :: (Char -> a -> a) -> a -> ByteString -> a
42+
foldr f e = go
43+
where
44+
go Nil = e
45+
go (Cons c cs) = c `f` go cs
46+
47+
toString :: ByteString -> String
48+
toString = foldr (:) []
49+
2850
fromString :: String -> ByteString
29-
fromString = NotByteString
51+
fromString = Prelude.foldr Cons Nil
3052

3153
fromByteString :: BS.ByteString -> ByteString
32-
fromByteString = fromString . BSC.unpack
54+
fromByteString = BSC.foldr Cons Nil
3355

3456
toByteString :: ByteString -> BS.ByteString
3557
toByteString = BSC.pack . toString
3658

3759
length :: ByteString -> Int
38-
length = Prelude.length . toString
60+
length = foldl' (\l _ -> l + 1) 0
61+
62+
(++) :: ByteString -> ByteString -> ByteString
63+
xs ++ ys = foldr Cons ys xs
3964

4065
concat :: [ByteString] -> ByteString
41-
concat = fromString . concatMap toString
66+
concat = Prelude.foldr (++) empty
4267

4368
null :: ByteString -> Bool
44-
null = Prelude.null . toString
69+
null = foldr (\_ _ -> False) True
4570

4671
empty :: ByteString
47-
empty = fromString ""
72+
empty = Nil
73+
74+
reverse :: ByteString -> ByteString
75+
reverse = go Nil
76+
where
77+
go acc Nil = acc
78+
go acc (Cons c cs) = go (Cons c acc) cs
4879

4980
splitAt :: Int -> ByteString -> (ByteString, ByteString)
50-
splitAt i = (fromString *** fromString) . Prelude.splitAt i . toString
81+
splitAt = go Nil
82+
where
83+
go acc 0 cs = (reverse acc, cs)
84+
go acc _ Nil = (reverse acc, Nil)
85+
go acc n (Cons c cs) = go (Cons c acc) (n - 1) cs

‎not-bytestring/src/Data/NotByteString/Char8.hs

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,5 +19,6 @@ pack = fromString
1919
unpack :: ByteString -> String
2020
unpack = toString
2121

22+
-- TODO: Avoid roundtrip
2223
split :: Char -> ByteString -> [ByteString]
2324
split c = map fromByteString . BSC.split c . toByteString

‎not-bytestring/src/Data/NotByteString/Lazy.hs

Lines changed: 80 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
1-
module Data.NotByteString.Lazy
2-
( ByteString
1+
module Data.NotByteString.Lazy
2+
( ByteString(Nil, Cons)
33
, fromString
44
, toString
55
, fromByteString
@@ -9,32 +9,93 @@ module Data.NotByteString.Lazy
99
, null
1010
, empty
1111
, splitAt
12+
, foldr
13+
, foldl'
14+
, (++)
1215
, toChunks
1316
, fromChunks
1417
) where
1518

16-
import Prelude hiding (length, concat, null, splitAt)
17-
import Data.NotByteString
18-
( ByteString
19-
, fromString
20-
, toString
21-
, length
22-
, concat
23-
, null
24-
, empty
25-
, splitAt
26-
)
19+
import Prelude hiding (length, null, concat, splitAt, foldr, (++), reverse)
20+
import qualified Prelude (length, null, splitAt, foldr)
21+
import Data.Binary (Binary(get, put))
22+
import Data.Typeable (Typeable)
2723
import qualified Data.ByteString.Lazy as BSL (ByteString)
28-
import qualified Data.ByteString.Lazy.Char8 as BSLC (pack, unpack)
24+
import qualified Data.ByteString.Lazy.Char8 as BSLC (pack, foldr)
25+
import qualified Data.NotByteString as Strict (ByteString(Nil, Cons), foldr)
26+
import Control.Applicative ((<$>))
27+
28+
data ByteString = Nil | Cons !Char ByteString
29+
deriving (Typeable, Eq, Ord)
30+
31+
instance Show ByteString where
32+
show = toString
33+
34+
instance Binary ByteString where
35+
get = fromByteString <$> get
36+
put = put . toByteString
37+
38+
foldl' :: (a -> Char -> a) -> a -> ByteString -> a
39+
foldl' f = go
40+
where
41+
go !acc Nil = acc
42+
go !acc (Cons c cs) = go (acc `f` c) cs
43+
44+
foldr :: (Char -> a -> a) -> a -> ByteString -> a
45+
foldr f e = go
46+
where
47+
go Nil = e
48+
go (Cons c cs) = c `f` go cs
49+
50+
toString :: ByteString -> String
51+
toString = foldr (:) []
52+
53+
fromString :: String -> ByteString
54+
fromString = Prelude.foldr Cons Nil
2955

3056
fromByteString :: BSL.ByteString -> ByteString
31-
fromByteString = fromString . BSLC.unpack
57+
fromByteString = BSLC.foldr Cons Nil
3258

3359
toByteString :: ByteString -> BSL.ByteString
3460
toByteString = BSLC.pack . toString
3561

36-
toChunks :: ByteString -> [ByteString]
37-
toChunks = return
62+
length :: ByteString -> Int
63+
length = foldl' (\l _ -> l + 1) 0
64+
65+
(++) :: ByteString -> ByteString -> ByteString
66+
xs ++ ys = foldr Cons ys xs
67+
68+
concat :: [ByteString] -> ByteString
69+
concat = Prelude.foldr (++) empty
70+
71+
null :: ByteString -> Bool
72+
null = foldr (\_ _ -> False) True
73+
74+
empty :: ByteString
75+
empty = Nil
76+
77+
reverse :: ByteString -> ByteString
78+
reverse = go Nil
79+
where
80+
go acc Nil = acc
81+
go acc (Cons c cs) = go (Cons c acc) cs
82+
83+
splitAt :: Int -> ByteString -> (ByteString, ByteString)
84+
splitAt = go Nil
85+
where
86+
go acc 0 cs = (reverse acc, cs)
87+
go acc _ Nil = (reverse acc, Nil)
88+
go acc n (Cons c cs) = go (Cons c acc) (n - 1) cs
89+
90+
toStrict :: ByteString -> Strict.ByteString
91+
toStrict = foldr Strict.Cons Strict.Nil
92+
93+
fromStrict :: Strict.ByteString -> ByteString
94+
fromStrict = Strict.foldr Cons Nil
95+
96+
-- | This does not preserve laziness
97+
toChunks :: ByteString -> [Strict.ByteString]
98+
toChunks = return . toStrict
3899

39-
fromChunks :: [ByteString] -> ByteString
40-
fromChunks = concat
100+
fromChunks :: [Strict.ByteString] -> ByteString
101+
fromChunks = concat . map fromStrict

‎not-bytestring/src/Data/NotByteString/Lazy/Char8.hs

Lines changed: 21 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,24 @@
11
module Data.NotByteString.Lazy.Char8
2-
( module Data.NotByteString.Char8
2+
( pack
3+
, unpack
4+
, split
35
) where
46

5-
import Data.NotByteString.Char8
7+
import Data.NotByteString.Lazy
8+
( ByteString
9+
, fromString
10+
, toString
11+
, fromByteString
12+
, toByteString
13+
)
14+
import qualified Data.ByteString.Lazy.Char8 as BSC (split)
15+
16+
pack :: String -> ByteString
17+
pack = fromString
18+
19+
unpack :: ByteString -> String
20+
unpack = toString
21+
22+
-- TODO: Avoid roundtrip
23+
split :: Char -> ByteString -> [ByteString]
24+
split c = map fromByteString . BSC.split c . toByteString

0 commit comments

Comments
 (0)