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