git.iko.soy/elk
on 267f708 help sign in
elk/src/Reporting/Bag.hs
101 lines 1.3 kB history raw
1{-# OPTIONS_GHC -Wall #-}
2module Reporting.Bag
3 ( Bag
4 , empty, singleton, cons, append, map
5 , toList, fromList
6 )
7 where
10import Prelude hiding (map)
14-- BAGS
17data Bag a
18 = Empty
19 | One a
20 | Two (Bag a) (Bag a)
21 | Many [a]
24empty :: Bag a
25empty =
26 Empty
29singleton :: a -> Bag a
30singleton =
31 One
34cons :: a -> Bag a -> Bag a
35cons x bag =
36 case bag of
37 Empty ->
38 One x
40 _ ->
41 Two (One x) bag
44append :: Bag a -> Bag a -> Bag a
45append left right =
46 case (left, right) of
47 (other, Empty) ->
48 other
50 (Empty, other) ->
51 other
53 (_, _) ->
54 Two left right
57map :: (a -> b) -> Bag a -> Bag b
58map func bag =
59 case bag of
60 Empty ->
61 Empty
63 One x ->
64 One (func x)
66 Two left right ->
67 Two (map func left) (map func right)
69 Many xs ->
70 Many (fmap func xs)
74-- LIST CONVERSIONS
77fromList :: [a] -> Bag a
78fromList =
79 Many
82toList :: (a -> b) -> Bag a -> [b]
83toList func bag =
84 toListHelp func bag []
87toListHelp :: (a -> b) -> Bag a -> [b] -> [b]
88toListHelp func bag list =
89 case bag of
90 Empty ->
91 list
93 One x ->
94 func x : list
96 Two left right ->
97 toListHelp func left (toListHelp func right list)
99 Many xs ->
100 foldr (\x newList -> func x : newList) list xs