diff options
author | Sven Tennie <sven.tennie@gmail.com> | 2019-04-13 19:17:28 +0200 |
---|---|---|
committer | Marge Bot <ben+marge-bot@smart-cactus.org> | 2019-04-17 23:19:00 -0400 |
commit | e142ec99e91ef4bdffd367780e945526ec6ef7e2 (patch) | |
tree | 4ef00c366314ca78970633f4d366bf87be852a31 | |
parent | 894ec447955a5066faee1b87af9cc7785ae14cd8 (diff) | |
download | haskell-e142ec99e91ef4bdffd367780e945526ec6ef7e2.tar.gz |
Typeset Big-O complexities with Tex-style notation (#16090)
E.g. use `\(\mathcal{O}(n^2)\)` instead of `/O(n^2)/`.
-rw-r--r-- | libraries/base/Data/Foldable.hs | 4 | ||||
-rw-r--r-- | libraries/base/Data/OldList.hs | 56 | ||||
-rw-r--r-- | libraries/base/Data/Semigroup/Internal.hs | 4 | ||||
-rw-r--r-- | libraries/base/GHC/Base.hs | 6 | ||||
-rw-r--r-- | libraries/base/GHC/List.hs | 59 | ||||
-rw-r--r-- | libraries/base/GHC/StableName.hs | 4 | ||||
-rw-r--r-- | libraries/base/System/Mem/StableName.hs | 4 |
7 files changed, 69 insertions, 68 deletions
diff --git a/libraries/base/Data/Foldable.hs b/libraries/base/Data/Foldable.hs index 037a44b99e..c17de972af 100644 --- a/libraries/base/Data/Foldable.hs +++ b/libraries/base/Data/Foldable.hs @@ -181,8 +181,8 @@ class Foldable t where -- use 'foldl'' instead of 'foldl'. The reason for this is that latter does -- not force the "inner" results (e.g. @z \`f\` x1@ in the above example) -- before applying them to the operator (e.g. to @(\`f\` x2)@). This results - -- in a thunk chain @O(n)@ elements long, which then must be evaluated from - -- the outside-in. + -- in a thunk chain \(\mathcal{O}(n)\) elements long, which then must be + -- evaluated from the outside-in. -- -- For a general 'Foldable' structure this should be semantically identical -- to, diff --git a/libraries/base/Data/OldList.hs b/libraries/base/Data/OldList.hs index 73d81dfe03..035a969e27 100644 --- a/libraries/base/Data/OldList.hs +++ b/libraries/base/Data/OldList.hs @@ -241,9 +241,9 @@ infix 5 \\ -- comment to fool cpp: https://downloads.haskell.org/~ghc/latest/doc dropWhileEnd :: (a -> Bool) -> [a] -> [a] dropWhileEnd p = foldr (\x xs -> if p x && null xs then [] else x : xs) [] --- | /O(min(m,n))/. The 'stripPrefix' function drops the given prefix from a --- list. It returns 'Nothing' if the list did not start with the prefix given, --- or 'Just' the list after the prefix, if it does. +-- | \(\mathcal{O}(min(m,n))\). The 'stripPrefix' function drops the given +-- prefix from a list. It returns 'Nothing' if the list did not start with the +-- prefix given, or 'Just' the list after the prefix, if it does. -- -- >>> stripPrefix "foo" "foobar" -- Just "bar" @@ -319,8 +319,8 @@ findIndices p ls = build $ \c n -> in foldr go (\_ -> n) ls 0# #endif /* USE_REPORT_PRELUDE */ --- | /O(min(m,n))/. The 'isPrefixOf' function takes two lists and returns 'True' --- iff the first list is a prefix of the second. +-- | \(\mathcal{O}(min(m,n))\). The 'isPrefixOf' function takes two lists and +-- returns 'True' iff the first list is a prefix of the second. -- -- >>> "Hello" `isPrefixOf` "Hello World!" -- True @@ -388,11 +388,10 @@ dropLengthMaybe (_:x') (_:y') = dropLengthMaybe x' y' isInfixOf :: (Eq a) => [a] -> [a] -> Bool isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack) --- | /O(n^2)/. The 'nub' function removes duplicate elements from a list. --- In particular, it keeps only the first occurrence of each element. --- (The name 'nub' means \`essence\'.) --- It is a special case of 'nubBy', which allows the programmer to supply --- their own equality test. +-- | \(\mathcal{O}(n^2)\). The 'nub' function removes duplicate elements from a +-- list. In particular, it keeps only the first occurrence of each element. (The +-- name 'nub' means \`essence\'.) It is a special case of 'nubBy', which allows +-- the programmer to supply their own equality test. -- -- >>> nub [1,2,3,4,3,2,1,2,4,3,5] -- [1,2,3,4,5] @@ -431,8 +430,8 @@ elem_by eq y (x:xs) = x `eq` y || elem_by eq y xs #endif --- | /O(n)/. 'delete' @x@ removes the first occurrence of @x@ from its list --- argument. For example, +-- | \(\mathcal{O}(n)\). 'delete' @x@ removes the first occurrence of @x@ from +-- its list argument. For example, -- -- >>> delete 'a' "banana" -- "bnana" @@ -442,8 +441,8 @@ elem_by eq y (x:xs) = x `eq` y || elem_by eq y xs delete :: (Eq a) => a -> [a] -> [a] delete = deleteBy (==) --- | /O(n)/. The 'deleteBy' function behaves like 'delete', but takes a --- user-supplied equality predicate. +-- | \(\mathcal{O}(n)\). The 'deleteBy' function behaves like 'delete', but +-- takes a user-supplied equality predicate. -- -- >>> deleteBy (<=) 4 [1..10] -- [1,2,3,5,6,7,8,9,10] @@ -509,9 +508,9 @@ intersectBy _ [] _ = [] intersectBy _ _ [] = [] intersectBy eq xs ys = [x | x <- xs, any (eq x) ys] --- | /O(n)/. The 'intersperse' function takes an element and a list and --- \`intersperses\' that element between the elements of the list. --- For example, +-- | \(\mathcal{O}(n)\). The 'intersperse' function takes an element and a list +-- and \`intersperses\' that element between the elements of the list. For +-- example, -- -- >>> intersperse ',' "abcde" -- "a,b,c,d,e" @@ -618,18 +617,18 @@ mapAccumR f s (x:xs) = (s'', y:ys) where (s'',y ) = f s' x (s', ys) = mapAccumR f s xs --- | /O(n)/. The 'insert' function takes an element and a list and inserts the --- element into the list at the first position where it is less than or equal to --- the next element. In particular, if the list is sorted before the call, the --- result will also be sorted. It is a special case of 'insertBy', which allows --- the programmer to supply their own comparison function. +-- | \(\mathcal{O}(n)\). The 'insert' function takes an element and a list and +-- inserts the element into the list at the first position where it is less than +-- or equal to the next element. In particular, if the list is sorted before the +-- call, the result will also be sorted. It is a special case of 'insertBy', +-- which allows the programmer to supply their own comparison function. -- -- >>> insert 4 [1,2,3,5,6,7] -- [1,2,3,4,5,6,7] insert :: Ord a => a -> [a] -> [a] insert e ls = insertBy (compare) e ls --- | /O(n)/. The non-overloaded version of 'insert'. +-- | \(\mathcal{O}(n)\). The non-overloaded version of 'insert'. insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a] insertBy _ x [] = [x] insertBy cmp x ys@(y:ys') @@ -669,9 +668,10 @@ minimumBy cmp xs = foldl1 minBy xs GT -> y _ -> x --- | /O(n)/. The 'genericLength' function is an overloaded version of 'length'. --- In particular, instead of returning an 'Int', it returns any type which is an --- instance of 'Num'. It is, however, less efficient than 'length'. +-- | \(\mathcal{O}(n)\). The 'genericLength' function is an overloaded version +-- of 'length'. In particular, instead of returning an 'Int', it returns any +-- type which is an instance of 'Num'. It is, however, less efficient than +-- 'length'. -- -- >>> genericLength [1, 2, 3] :: Int -- 3 @@ -1029,8 +1029,8 @@ inits = map toListSB . scanl' snocSB emptySB -- if it fuses with a consumer, and it would generally lead to serious -- loss of sharing if allowed to fuse with a producer. --- | /O(n)/. The 'tails' function returns all final segments of the argument, --- longest first. For example, +-- | \(\mathcal{O}(n)\). The 'tails' function returns all final segments of the +-- argument, longest first. For example, -- -- >>> tails "abc" -- ["abc","bc","c",""] diff --git a/libraries/base/Data/Semigroup/Internal.hs b/libraries/base/Data/Semigroup/Internal.hs index 7484608c24..2dfee142c9 100644 --- a/libraries/base/Data/Semigroup/Internal.hs +++ b/libraries/base/Data/Semigroup/Internal.hs @@ -31,7 +31,7 @@ import GHC.Real -- | This is a valid definition of 'stimes' for an idempotent 'Semigroup'. -- -- When @x <> x = x@, this definition should be preferred, because it --- works in /O(1)/ rather than /O(log n)/. +-- works in \(\mathcal{O}(1)\) rather than \(\mathcal{O}(\log n)\). stimesIdempotent :: Integral b => b -> a -> a stimesIdempotent n x | n <= 0 = errorWithoutStackTrace "stimesIdempotent: positive multiplier expected" @@ -40,7 +40,7 @@ stimesIdempotent n x -- | This is a valid definition of 'stimes' for an idempotent 'Monoid'. -- -- When @mappend x x = x@, this definition should be preferred, because it --- works in /O(1)/ rather than /O(log n)/ +-- works in \(\mathcal{O}(1)\) rather than \(\mathcal{O}(\log n)\) stimesIdempotentMonoid :: (Integral b, Monoid a) => b -> a -> a stimesIdempotentMonoid n x = case compare n 0 of LT -> errorWithoutStackTrace "stimesIdempotentMonoid: negative multiplier" diff --git a/libraries/base/GHC/Base.hs b/libraries/base/GHC/Base.hs index a9923681f4..b342386edc 100644 --- a/libraries/base/GHC/Base.hs +++ b/libraries/base/GHC/Base.hs @@ -239,7 +239,7 @@ class Semigroup a where -- will do so. -- -- By making this a member of the class, idempotent semigroups - -- and monoids can upgrade this to execute in /O(1)/ by + -- and monoids can upgrade this to execute in \(\mathcal{O}(1)\) by -- picking @stimes = 'Data.Semigroup.stimesIdempotent'@ or @stimes = -- 'stimesIdempotentMonoid'@ respectively. stimes :: Integral b => b -> a -> a @@ -1083,8 +1083,8 @@ augment g xs = g (:) xs -- map ---------------------------------------------- --- | /O(n)/. 'map' @f xs@ is the list obtained by applying @f@ to each element --- of @xs@, i.e., +-- | \(\mathcal{O}(n)\). 'map' @f xs@ is the list obtained by applying @f@ to +-- each element of @xs@, i.e., -- -- > map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn] -- > map f [x1, x2, ...] == [f x1, f x2, ...] diff --git a/libraries/base/GHC/List.hs b/libraries/base/GHC/List.hs index 531669acd0..2a2b4cb58d 100644 --- a/libraries/base/GHC/List.hs +++ b/libraries/base/GHC/List.hs @@ -44,7 +44,7 @@ infix 4 `elem`, `notElem` -- List-manipulation functions -------------------------------------------------------------- --- | /O(1)/. Extract the first element of a list, which must be non-empty. +-- | \(\mathcal{O}(1)\). Extract the first element of a list, which must be non-empty. head :: [a] -> a head (x:_) = x head [] = badHead @@ -62,8 +62,8 @@ badHead = errorEmptyList "head" head (augment g xs) = g (\x _ -> x) (head xs) #-} --- | /O(1)/. Decompose a list into its head and tail. If the list is empty, --- returns 'Nothing'. If the list is non-empty, returns @'Just' (x, xs)@, +-- | \(\mathcal{O}(1)\). Decompose a list into its head and tail. If the list is +-- empty, returns 'Nothing'. If the list is non-empty, returns @'Just' (x, xs)@, -- where @x@ is the head of the list and @xs@ its tail. -- -- @since 4.8.0.0 @@ -71,14 +71,14 @@ uncons :: [a] -> Maybe (a, [a]) uncons [] = Nothing uncons (x:xs) = Just (x, xs) --- | /O(1)/. Extract the elements after the head of a list, which must be --- non-empty. +-- | \(\mathcal{O}(1)\). Extract the elements after the head of a list, which +-- must be non-empty. tail :: [a] -> [a] tail (_:xs) = xs tail [] = errorEmptyList "tail" --- | /O(n)/. Extract the last element of a list, which must be finite and --- non-empty. +-- | \(\mathcal{O}(n)\). Extract the last element of a list, which must be +-- finite and non-empty. last :: [a] -> a #if defined(USE_REPORT_PRELUDE) last [x] = x @@ -96,7 +96,7 @@ lastError :: a lastError = errorEmptyList "last" #endif --- | /O(n)/. Return all the elements of a list except the last one. +-- | \(\mathcal{O}(n)\). Return all the elements of a list except the last one. -- The list must be non-empty. init :: [a] -> [a] #if defined(USE_REPORT_PRELUDE) @@ -111,14 +111,14 @@ init (x:xs) = init' x xs init' y (z:zs) = y : init' z zs #endif --- | /O(1)/. Test whether a list is empty. +-- | \(\mathcal{O}(1)\). Test whether a list is empty. null :: [a] -> Bool null [] = True null (_:_) = False --- | /O(n)/. 'length' returns the length of a finite list as an 'Int'. --- It is an instance of the more general 'Data.List.genericLength', --- the result type of which may be any kind of number. +-- | \(\mathcal{O}(n)\). 'length' returns the length of a finite list as an +-- 'Int'. It is an instance of the more general 'Data.List.genericLength', the +-- result type of which may be any kind of number. {-# NOINLINE [1] length #-} length :: [a] -> Int length xs = lenAcc xs 0 @@ -142,8 +142,8 @@ lengthFB _ r = \ !a -> r (a + 1) idLength :: Int -> Int idLength = id --- | /O(n)/. 'filter', applied to a predicate and a list, returns the list of --- those elements that satisfy the predicate; i.e., +-- | \(\mathcal{O}(n)\). 'filter', applied to a predicate and a list, returns +-- the list of those elements that satisfy the predicate; i.e., -- -- > filter p xs = [ x | x <- xs, p x] -- @@ -262,8 +262,8 @@ product :: (Num a) => [a] -> a {-# INLINE product #-} product = foldl (*) 1 --- | /O(n)/. 'scanl' is similar to 'foldl', but returns a list of successive --- reduced values from the left: +-- | \(\mathcal{O}(n)\). 'scanl' is similar to 'foldl', but returns a list of +-- successive reduced values from the left: -- -- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...] -- @@ -300,8 +300,8 @@ constScanl :: a -> b -> a constScanl = const --- | /O(n)/. 'scanl1' is a variant of 'scanl' that has no starting value --- argument: +-- | \(\mathcal{O}(n)\). 'scanl1' is a variant of 'scanl' that has no starting +-- value argument: -- -- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...] @@ -309,7 +309,7 @@ scanl1 :: (a -> a -> a) -> [a] -> [a] scanl1 f (x:xs) = scanl f x xs scanl1 _ [] = [] --- | /O(n)/. A strictly accumulating version of 'scanl' +-- | \(\mathcal{O}(n)\). A strictly accumulating version of 'scanl' {-# NOINLINE [1] scanl' #-} scanl' :: (b -> a -> b) -> b -> [a] -> [b] -- This peculiar form is needed to prevent scanl' from being rewritten @@ -381,7 +381,7 @@ foldr1 f = go go [] = errorEmptyList "foldr1" {-# INLINE [0] foldr1 #-} --- | /O(n)/. 'scanr' is the right-to-left dual of 'scanl'. +-- | \(\mathcal{O}(n)\). 'scanr' is the right-to-left dual of 'scanl'. -- Note that -- -- > head (scanr f z xs) == foldr f z xs. @@ -408,8 +408,8 @@ scanrFB f c = \x (r, est) -> (f x r, r `c` est) scanr f q0 ls #-} --- | /O(n)/. 'scanr1' is a variant of 'scanr' that has no starting value --- argument. +-- | \(\mathcal{O}(n)\). 'scanr1' is a variant of 'scanr' that has no starting +-- value argument. scanr1 :: (a -> a -> a) -> [a] -> [a] scanr1 _ [] = [] scanr1 _ [x] = [x] @@ -852,7 +852,8 @@ notElem x (y:ys)= x /= y && notElem x ys #-} #endif --- | /O(n)/. 'lookup' @key assocs@ looks up a key in an association list. +-- | \(\mathcal{O}(n)\). 'lookup' @key assocs@ looks up a key in an association +-- list. -- -- >>> lookup 2 [(1, "first"), (2, "second"), (3, "third")] -- Just "second" @@ -1012,8 +1013,8 @@ NB: Zips for larger tuples are in the List module. -} ---------------------------------------------- --- | /O(min(m,n))/. 'zip' takes two lists and returns a list of corresponding --- pairs. +-- | \(\mathcal{O}(min(m,n))\). 'zip' takes two lists and returns a list of +-- corresponding pairs. -- -- > zip [1, 2] ['a', 'b'] = [(1, 'a'), (2, 'b')] -- @@ -1070,10 +1071,10 @@ zip3FB cons = \a b c r -> (a,b,c) `cons` r -- function given as the first argument, instead of a tupling function. ---------------------------------------------- --- | /O(min(m,n))/. 'zipWith' generalises 'zip' by zipping with the function --- given as the first argument, instead of a tupling function. For example, --- @'zipWith' (+)@ is applied to two lists to produce the list of corresponding --- sums: +-- | \(\mathcal{O}(min(m,n))\). 'zipWith' generalises 'zip' by zipping with the +-- function given as the first argument, instead of a tupling function. For +-- example, @'zipWith' (+)@ is applied to two lists to produce the list of +-- corresponding sums: -- -- >>> zipWith (+) [1, 2, 3] [4, 5, 6] -- [5,7,9] diff --git a/libraries/base/GHC/StableName.hs b/libraries/base/GHC/StableName.hs index 7369f41d72..f7eb4e40b4 100644 --- a/libraries/base/GHC/StableName.hs +++ b/libraries/base/GHC/StableName.hs @@ -13,8 +13,8 @@ -- Stability : experimental -- Portability : non-portable -- --- Stable names are a way of performing fast (O(1)), not-quite-exact --- comparison between objects. +-- Stable names are a way of performing fast ( \(\mathcal{O}(1)\) ), +-- not-quite-exact comparison between objects. -- -- Stable names solve the following problem: suppose you want to build -- a hash table with Haskell objects as keys, but you want to use diff --git a/libraries/base/System/Mem/StableName.hs b/libraries/base/System/Mem/StableName.hs index 064d928865..17392e98e3 100644 --- a/libraries/base/System/Mem/StableName.hs +++ b/libraries/base/System/Mem/StableName.hs @@ -10,8 +10,8 @@ -- Stability : experimental -- Portability : non-portable -- --- Stable names are a way of performing fast (O(1)), not-quite-exact --- comparison between objects. +-- Stable names are a way of performing fast ( \(\mathcal{O}(1)\) ), +-- not-quite-exact comparison between objects. -- -- Stable names solve the following problem: suppose you want to build -- a hash table with Haskell objects as keys, but you want to use |