Refactor importdecls/topdecls parsing.
[ghc.git] / libraries / base / Data / Functor / Utils.hs
1 {-# LANGUAGE Trustworthy #-}
2 {-# LANGUAGE NoImplicitPrelude #-}
3
4 -----------------------------------------------------------------------------
5 -- This is a non-exposed internal module.
6 --
7 -- This code contains utility function and data structures that are used
8 -- to improve the efficiency of several instances in the Data.* namespace.
9 -----------------------------------------------------------------------------
10 module Data.Functor.Utils where
11
12 import Data.Coerce (Coercible, coerce)
13 import GHC.Base ( Applicative(..), Functor(..), Maybe(..), Monoid(..), Ord(..)
14 , ($), otherwise )
15
16 -- We don't expose Max and Min because, as Edward Kmett pointed out to me,
17 -- there are two reasonable ways to define them. One way is to use Maybe, as we
18 -- do here; the other way is to impose a Bounded constraint on the Monoid
19 -- instance. We may eventually want to add both versions, but we don't want to
20 -- trample on anyone's toes by imposing Max = MaxMaybe.
21
22 newtype Max a = Max {getMax :: Maybe a}
23 newtype Min a = Min {getMin :: Maybe a}
24
25 -- | @since 4.8.0.0
26 instance Ord a => Monoid (Max a) where
27 mempty = Max Nothing
28
29 {-# INLINE mappend #-}
30 m `mappend` Max Nothing = m
31 Max Nothing `mappend` n = n
32 (Max m@(Just x)) `mappend` (Max n@(Just y))
33 | x >= y = Max m
34 | otherwise = Max n
35
36 -- | @since 4.8.0.0
37 instance Ord a => Monoid (Min a) where
38 mempty = Min Nothing
39
40 {-# INLINE mappend #-}
41 m `mappend` Min Nothing = m
42 Min Nothing `mappend` n = n
43 (Min m@(Just x)) `mappend` (Min n@(Just y))
44 | x <= y = Min m
45 | otherwise = Min n
46
47 -- left-to-right state transformer
48 newtype StateL s a = StateL { runStateL :: s -> (s, a) }
49
50 -- | @since 4.0
51 instance Functor (StateL s) where
52 fmap f (StateL k) = StateL $ \ s -> let (s', v) = k s in (s', f v)
53
54 -- | @since 4.0
55 instance Applicative (StateL s) where
56 pure x = StateL (\ s -> (s, x))
57 StateL kf <*> StateL kv = StateL $ \ s ->
58 let (s', f) = kf s
59 (s'', v) = kv s'
60 in (s'', f v)
61
62 -- right-to-left state transformer
63 newtype StateR s a = StateR { runStateR :: s -> (s, a) }
64
65 -- | @since 4.0
66 instance Functor (StateR s) where
67 fmap f (StateR k) = StateR $ \ s -> let (s', v) = k s in (s', f v)
68
69 -- | @since 4.0
70 instance Applicative (StateR s) where
71 pure x = StateR (\ s -> (s, x))
72 StateR kf <*> StateR kv = StateR $ \ s ->
73 let (s', v) = kv s
74 (s'', f) = kf s'
75 in (s'', f v)
76
77 -- See Note [Function coercion]
78 (#.) :: Coercible b c => (b -> c) -> (a -> b) -> (a -> c)
79 (#.) _f = coerce
80 {-# INLINE (#.) #-}
81
82 {-
83 Note [Function coercion]
84 ~~~~~~~~~~~~~~~~~~~~~~~
85
86 Several functions here use (#.) instead of (.) to avoid potential efficiency
87 problems relating to #7542. The problem, in a nutshell:
88
89 If N is a newtype constructor, then N x will always have the same
90 representation as x (something similar applies for a newtype deconstructor).
91 However, if f is a function,
92
93 N . f = \x -> N (f x)
94
95 This looks almost the same as f, but the eta expansion lifts it--the lhs could
96 be _|_, but the rhs never is. This can lead to very inefficient code. Thus we
97 steal a technique from Shachaf and Edward Kmett and adapt it to the current
98 (rather clean) setting. Instead of using N . f, we use N #. f, which is
99 just
100
101 coerce f `asTypeOf` (N . f)
102
103 That is, we just *pretend* that f has the right type, and thanks to the safety
104 of coerce, the type checker guarantees that nothing really goes wrong. We still
105 have to be a bit careful, though: remember that #. completely ignores the
106 *value* of its left operand.
107 -}