-- (c) The University of Glasgow 2006

{-# LANGUAGE CPP #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE MagicHash #-}

{-# OPTIONS_GHC -Wno-incomplete-uni-patterns #-}

-- | Highly random utility functions
--
module GHC.Utils.Misc (
        -- * Miscellaneous higher-order functions
        applyWhen, nTimes, const2,

        -- * General list processing
        zipEqual, zipWithEqual, zipWith3Equal, zipWith4Equal,
        zipLazy, stretchZipWith, zipWithAndUnzip, zipAndUnzip,

        zipWithLazy, zipWith3Lazy,

        filterByList, filterByLists, partitionByList,

        unzipWith,

        mapFst, mapSnd, chkAppend,
        mapAndUnzip, mapAndUnzip3,
        filterOut, partitionWith,
        mapAccumM,

        dropWhileEndLE, spanEnd, last2, lastMaybe, onJust,

        List.foldl1', foldl2, count, countWhile, all2,

        lengthExceeds, lengthIs, lengthIsNot,
        lengthAtLeast, lengthAtMost, lengthLessThan,
        listLengthCmp, atLength,
        equalLength, compareLength, leLength, ltLength,

        isSingleton, only, expectOnly, GHC.Utils.Misc.singleton,
        notNull, snocView,

        chunkList,

        changeLast,
        mapLastM,

        whenNonEmpty,

        mergeListsBy,
        isSortedBy,

        -- Foldable generalised functions,

        mapMaybe',

        -- * Tuples
        fstOf3, sndOf3, thdOf3,
        firstM, first3M, secondM,
        fst3, snd3, third3,
        uncurry3,
        liftFst, liftSnd,

        -- * List operations controlled by another list
        takeList, dropList, splitAtList, split,
        dropTail, capitalise,

        -- * Sorting
        sortWith, minWith, nubSort, ordNub, ordNubOn,

        -- * Comparisons
        isEqual, eqListBy, eqMaybeBy,
        thenCmp, cmpList,
        removeSpaces,
        (<&&>), (<||>),

        -- * Edit distance
        fuzzyMatch, fuzzyLookup,

        -- * Transitive closures
        transitiveClosure,

        -- * Strictness
        seqList, strictMap, strictZipWith, strictZipWith3,

        -- * Module names
        looksLikeModuleName,
        looksLikePackageName,

        -- * Integers
        exactLog2,

        -- * Floating point
        readRational,
        readSignificandExponentPair,
        readHexRational,
        readHexSignificandExponentPair,

        -- * IO-ish utilities
        doesDirNameExist,
        getModificationUTCTime,
        modificationTimeIfExists,
        fileHashIfExists,
        withAtomicRename,

        -- * Filenames and paths
        Suffix,
        splitLongestPrefix,
        escapeSpaces,
        Direction(..), reslash,
        makeRelativeTo,

        -- * Utils for defining Data instances
        abstractConstr, abstractDataType, mkNoRepType,

        -- * Utils for printing C code
        charToC,

        -- * Hashing
        hashString,

        -- * Call stacks
        HasCallStack,
        HasDebugCallStack,
    ) where

import GHC.Prelude

import GHC.Utils.Exception
import GHC.Utils.Panic.Plain
import GHC.Utils.Constants
import GHC.Utils.Fingerprint

import Data.Data
import qualified Data.List as List
import Data.List.NonEmpty  ( NonEmpty(..) )

import GHC.Exts
import GHC.Stack (HasCallStack)

import Control.Applicative ( liftA2 )
import Control.Monad    ( liftM, guard )
import Control.Monad.IO.Class ( MonadIO, liftIO )
import System.IO.Error as IO ( isDoesNotExistError )
import System.Directory ( doesDirectoryExist, getModificationTime, renameFile )
import System.FilePath

import Data.Char        ( isUpper, isAlphaNum, isSpace, chr, ord, isDigit, toUpper
                        , isHexDigit, digitToInt )
import Data.Int
import Data.Ratio       ( (%) )
import Data.Ord         ( comparing )
import Data.Word
import qualified Data.IntMap as IM
import qualified Data.Set as Set

import Data.Time

infixr 9 `thenCmp`


{-
************************************************************************
*                                                                      *
\subsection{Miscellaneous higher-order functions}
*                                                                      *
************************************************************************
-}

-- | Apply a function iff some condition is met.
applyWhen :: Bool -> (a -> a) -> a -> a
applyWhen :: forall a. Bool -> (a -> a) -> a -> a
applyWhen Bool
True a -> a
f a
x = a -> a
f a
x
applyWhen Bool
_    a -> a
_ a
x = a
x

-- | Apply a function @n@ times to a given value.
nTimes :: Int -> (a -> a) -> (a -> a)
nTimes :: forall a. Int -> (a -> a) -> a -> a
nTimes Int
0 a -> a
_ = a -> a
forall a. a -> a
id
nTimes Int
1 a -> a
f = a -> a
f
nTimes Int
n a -> a
f = a -> a
f (a -> a) -> (a -> a) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> (a -> a) -> a -> a
forall a. Int -> (a -> a) -> a -> a
nTimes (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) a -> a
f

const2 :: a -> b -> c -> a
const2 :: forall a b c. a -> b -> c -> a
const2 a
x b
_ c
_ = a
x

fstOf3   :: (a,b,c) -> a
sndOf3   :: (a,b,c) -> b
thdOf3   :: (a,b,c) -> c
fstOf3 :: forall a b c. (a, b, c) -> a
fstOf3      (a
a,b
_,c
_) =  a
a
sndOf3 :: forall a b c. (a, b, c) -> b
sndOf3      (a
_,b
b,c
_) =  b
b
thdOf3 :: forall a b c. (a, b, c) -> c
thdOf3      (a
_,b
_,c
c) =  c
c

fst3 :: (a -> d) -> (a, b, c) -> (d, b, c)
fst3 :: forall a d b c. (a -> d) -> (a, b, c) -> (d, b, c)
fst3 a -> d
f (a
a, b
b, c
c) = (a -> d
f a
a, b
b, c
c)

snd3 :: (b -> d) -> (a, b, c) -> (a, d, c)
snd3 :: forall b d a c. (b -> d) -> (a, b, c) -> (a, d, c)
snd3 b -> d
f (a
a, b
b, c
c) = (a
a, b -> d
f b
b, c
c)

third3 :: (c -> d) -> (a, b, c) -> (a, b, d)
third3 :: forall c d a b. (c -> d) -> (a, b, c) -> (a, b, d)
third3 c -> d
f (a
a, b
b, c
c) = (a
a, b
b, c -> d
f c
c)

uncurry3 :: (a -> b -> c -> d) -> (a, b, c) -> d
uncurry3 :: forall a b c d. (a -> b -> c -> d) -> (a, b, c) -> d
uncurry3 a -> b -> c -> d
f (a
a, b
b, c
c) = a -> b -> c -> d
f a
a b
b c
c

liftFst :: (a -> b) -> (a, c) -> (b, c)
liftFst :: forall a b c. (a -> b) -> (a, c) -> (b, c)
liftFst a -> b
f (a
a,c
c) = (a -> b
f a
a, c
c)

liftSnd :: (a -> b) -> (c, a) -> (c, b)
liftSnd :: forall a b c. (a -> b) -> (c, a) -> (c, b)
liftSnd a -> b
f (c
c,a
a) = (c
c, a -> b
f a
a)

firstM :: Monad m => (a -> m c) -> (a, b) -> m (c, b)
firstM :: forall (m :: * -> *) a c b.
Monad m =>
(a -> m c) -> (a, b) -> m (c, b)
firstM a -> m c
f (a
x, b
y) = (c -> (c, b)) -> m c -> m (c, b)
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM (\c
x' -> (c
x', b
y)) (a -> m c
f a
x)

first3M :: Monad m => (a -> m d) -> (a, b, c) -> m (d, b, c)
first3M :: forall (m :: * -> *) a d b c.
Monad m =>
(a -> m d) -> (a, b, c) -> m (d, b, c)
first3M a -> m d
f (a
x, b
y, c
z) = (d -> (d, b, c)) -> m d -> m (d, b, c)
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM (\d
x' -> (d
x', b
y, c
z)) (a -> m d
f a
x)

secondM :: Monad m => (b -> m c) -> (a, b) -> m (a, c)
secondM :: forall (m :: * -> *) b c a.
Monad m =>
(b -> m c) -> (a, b) -> m (a, c)
secondM b -> m c
f (a
x, b
y) = (a
x,) (c -> (a, c)) -> m c -> m (a, c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> b -> m c
f b
y

{-
************************************************************************
*                                                                      *
\subsection[Utils-lists]{General list processing}
*                                                                      *
************************************************************************
-}

filterOut :: (a->Bool) -> [a] -> [a]
-- ^ Like filter, only it reverses the sense of the test
filterOut :: forall a. (a -> Bool) -> [a] -> [a]
filterOut a -> Bool
p = (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)

partitionWith :: (a -> Either b c) -> [a] -> ([b], [c])
-- ^ Uses a function to determine which of two output lists an input element should join
partitionWith :: forall a b c. (a -> Either b c) -> [a] -> ([b], [c])
partitionWith a -> Either b c
_ [] = ([],[])
partitionWith a -> Either b c
f (a
x:[a]
xs) = case a -> Either b c
f a
x of
                         Left  b
b -> (b
bb -> [b] -> [b]
forall a. a -> [a] -> [a]
:[b]
bs, [c]
cs)
                         Right c
c -> ([b]
bs, c
cc -> [c] -> [c]
forall a. a -> [a] -> [a]
:[c]
cs)
    where ([b]
bs,[c]
cs) = (a -> Either b c) -> [a] -> ([b], [c])
forall a b c. (a -> Either b c) -> [a] -> ([b], [c])
partitionWith a -> Either b c
f [a]
xs

chkAppend :: [a] -> [a] -> [a]
-- Checks for the second argument being empty
-- Used in situations where that situation is common
chkAppend :: forall a. [a] -> [a] -> [a]
chkAppend [a]
xs [a]
ys
  | [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
ys   = [a]
xs
  | Bool
otherwise = [a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
ys

{-
A paranoid @zip@ (and some @zipWith@ friends) that checks the lists
are of equal length.  Alastair Reid thinks this should only happen if
DEBUGging on; hey, why not?
-}

zipEqual        :: String -> [a] -> [b] -> [(a,b)]
zipWithEqual    :: String -> (a->b->c) -> [a]->[b]->[c]
zipWith3Equal   :: String -> (a->b->c->d) -> [a]->[b]->[c]->[d]
zipWith4Equal   :: String -> (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]

#if !defined(DEBUG)
zipEqual :: forall a b. String -> [a] -> [b] -> [(a, b)]
zipEqual      String
_ = [a] -> [b] -> [(a, b)]
forall a b. [a] -> [b] -> [(a, b)]
zip
zipWithEqual :: forall a b c. String -> (a -> b -> c) -> [a] -> [b] -> [c]
zipWithEqual  String
_ = (a -> b -> c) -> [a] -> [b] -> [c]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith
zipWith3Equal :: forall a b c d.
String -> (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith3Equal String
_ = (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith3
zipWith4Equal :: forall a b c d e.
String
-> (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e]
zipWith4Equal String
_ = (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e]
forall a b c d e.
(a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e]
List.zipWith4
#else
zipEqual _   []     []     = []
zipEqual msg (a:as) (b:bs) = (a,b) : zipEqual msg as bs
zipEqual msg _      _      = panic ("zipEqual: unequal lists: "++msg)

zipWithEqual msg z (a:as) (b:bs)=  z a b : zipWithEqual msg z as bs
zipWithEqual _   _ [] []        =  []
zipWithEqual msg _ _ _          =  panic ("zipWithEqual: unequal lists: "++msg)

zipWith3Equal msg z (a:as) (b:bs) (c:cs)
                                =  z a b c : zipWith3Equal msg z as bs cs
zipWith3Equal _   _ [] []  []   =  []
zipWith3Equal msg _ _  _   _    =  panic ("zipWith3Equal: unequal lists: "++msg)

zipWith4Equal msg z (a:as) (b:bs) (c:cs) (d:ds)
                                =  z a b c d : zipWith4Equal msg z as bs cs ds
zipWith4Equal _   _ [] [] [] [] =  []
zipWith4Equal msg _ _  _  _  _  =  panic ("zipWith4Equal: unequal lists: "++msg)
#endif

-- | 'zipLazy' is a kind of 'zip' that is lazy in the second list (observe the ~)
zipLazy :: [a] -> [b] -> [(a,b)]
zipLazy :: forall a b. [a] -> [b] -> [(a, b)]
zipLazy []     [b]
_       = []
zipLazy (a
x:[a]
xs) ~(b
y:[b]
ys) = (a
x,b
y) (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [a] -> [b] -> [(a, b)]
forall a b. [a] -> [b] -> [(a, b)]
zipLazy [a]
xs [b]
ys

-- | 'zipWithLazy' is like 'zipWith' but is lazy in the second list.
-- The length of the output is always the same as the length of the first
-- list.
zipWithLazy :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWithLazy :: forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWithLazy a -> b -> c
_ []     [b]
_       = []
zipWithLazy a -> b -> c
f (a
a:[a]
as) ~(b
b:[b]
bs) = a -> b -> c
f a
a b
b c -> [c] -> [c]
forall a. a -> [a] -> [a]
: (a -> b -> c) -> [a] -> [b] -> [c]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWithLazy a -> b -> c
f [a]
as [b]
bs

-- | 'zipWith3Lazy' is like 'zipWith3' but is lazy in the second and third lists.
-- The length of the output is always the same as the length of the first
-- list.
zipWith3Lazy :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith3Lazy :: forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith3Lazy a -> b -> c -> d
_ []     [b]
_       [c]
_       = []
zipWith3Lazy a -> b -> c -> d
f (a
a:[a]
as) ~(b
b:[b]
bs) ~(c
c:[c]
cs) = a -> b -> c -> d
f a
a b
b c
c d -> [d] -> [d]
forall a. a -> [a] -> [a]
: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith3Lazy a -> b -> c -> d
f [a]
as [b]
bs [c]
cs

-- | 'filterByList' takes a list of Bools and a list of some elements and
-- filters out these elements for which the corresponding value in the list of
-- Bools is False. This function does not check whether the lists have equal
-- length.
filterByList :: [Bool] -> [a] -> [a]
filterByList :: forall a. [Bool] -> [a] -> [a]
filterByList (Bool
True:[Bool]
bs)  (a
x:[a]
xs) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [Bool] -> [a] -> [a]
forall a. [Bool] -> [a] -> [a]
filterByList [Bool]
bs [a]
xs
filterByList (Bool
False:[Bool]
bs) (a
_:[a]
xs) =     [Bool] -> [a] -> [a]
forall a. [Bool] -> [a] -> [a]
filterByList [Bool]
bs [a]
xs
filterByList [Bool]
_          [a]
_      = []

-- | 'filterByLists' takes a list of Bools and two lists as input, and
-- outputs a new list consisting of elements from the last two input lists. For
-- each Bool in the list, if it is 'True', then it takes an element from the
-- former list. If it is 'False', it takes an element from the latter list.
-- The elements taken correspond to the index of the Bool in its list.
-- For example:
--
-- @
-- filterByLists [True, False, True, False] \"abcd\" \"wxyz\" = \"axcz\"
-- @
--
-- This function does not check whether the lists have equal length.
filterByLists :: [Bool] -> [a] -> [a] -> [a]
filterByLists :: forall a. [Bool] -> [a] -> [a] -> [a]
filterByLists (Bool
True:[Bool]
bs)  (a
x:[a]
xs) (a
_:[a]
ys) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [Bool] -> [a] -> [a] -> [a]
forall a. [Bool] -> [a] -> [a] -> [a]
filterByLists [Bool]
bs [a]
xs [a]
ys
filterByLists (Bool
False:[Bool]
bs) (a
_:[a]
xs) (a
y:[a]
ys) = a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [Bool] -> [a] -> [a] -> [a]
forall a. [Bool] -> [a] -> [a] -> [a]
filterByLists [Bool]
bs [a]
xs [a]
ys
filterByLists [Bool]
_          [a]
_      [a]
_      = []

-- | 'partitionByList' takes a list of Bools and a list of some elements and
-- partitions the list according to the list of Bools. Elements corresponding
-- to 'True' go to the left; elements corresponding to 'False' go to the right.
-- For example, @partitionByList [True, False, True] [1,2,3] == ([1,3], [2])@
-- This function does not check whether the lists have equal
-- length; when one list runs out, the function stops.
partitionByList :: [Bool] -> [a] -> ([a], [a])
partitionByList :: forall a. [Bool] -> [a] -> ([a], [a])
partitionByList = [a] -> [a] -> [Bool] -> [a] -> ([a], [a])
forall {a}. [a] -> [a] -> [Bool] -> [a] -> ([a], [a])
go [] []
  where
    go :: [a] -> [a] -> [Bool] -> [a] -> ([a], [a])
go [a]
trues [a]
falses (Bool
True  : [Bool]
bs) (a
x : [a]
xs) = [a] -> [a] -> [Bool] -> [a] -> ([a], [a])
go (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
trues) [a]
falses [Bool]
bs [a]
xs
    go [a]
trues [a]
falses (Bool
False : [Bool]
bs) (a
x : [a]
xs) = [a] -> [a] -> [Bool] -> [a] -> ([a], [a])
go [a]
trues (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
falses) [Bool]
bs [a]
xs
    go [a]
trues [a]
falses [Bool]
_ [a]
_ = ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
trues, [a] -> [a]
forall a. [a] -> [a]
reverse [a]
falses)

stretchZipWith :: (a -> Bool) -> b -> (a->b->c) -> [a] -> [b] -> [c]
-- ^ @stretchZipWith p z f xs ys@ stretches @ys@ by inserting @z@ in
-- the places where @p@ returns @True@

stretchZipWith :: forall a b c.
(a -> Bool) -> b -> (a -> b -> c) -> [a] -> [b] -> [c]
stretchZipWith a -> Bool
_ b
_ a -> b -> c
_ []     [b]
_ = []
stretchZipWith a -> Bool
p b
z a -> b -> c
f (a
x:[a]
xs) [b]
ys
  | a -> Bool
p a
x       = a -> b -> c
f a
x b
z c -> [c] -> [c]
forall a. a -> [a] -> [a]
: (a -> Bool) -> b -> (a -> b -> c) -> [a] -> [b] -> [c]
forall a b c.
(a -> Bool) -> b -> (a -> b -> c) -> [a] -> [b] -> [c]
stretchZipWith a -> Bool
p b
z a -> b -> c
f [a]
xs [b]
ys
  | Bool
otherwise = case [b]
ys of
                []     -> []
                (b
y:[b]
ys) -> a -> b -> c
f a
x b
y c -> [c] -> [c]
forall a. a -> [a] -> [a]
: (a -> Bool) -> b -> (a -> b -> c) -> [a] -> [b] -> [c]
forall a b c.
(a -> Bool) -> b -> (a -> b -> c) -> [a] -> [b] -> [c]
stretchZipWith a -> Bool
p b
z a -> b -> c
f [a]
xs [b]
ys

mapFst :: (a->c) -> [(a,b)] -> [(c,b)]
mapSnd :: (b->c) -> [(a,b)] -> [(a,c)]

mapFst :: forall a c b. (a -> c) -> [(a, b)] -> [(c, b)]
mapFst a -> c
f [(a, b)]
xys = [(a -> c
f a
x, b
y) | (a
x,b
y) <- [(a, b)]
xys]
mapSnd :: forall b c a. (b -> c) -> [(a, b)] -> [(a, c)]
mapSnd b -> c
f [(a, b)]
xys = [(a
x, b -> c
f b
y) | (a
x,b
y) <- [(a, b)]
xys]

mapAndUnzip :: (a -> (b, c)) -> [a] -> ([b], [c])

mapAndUnzip :: forall a b c. (a -> (b, c)) -> [a] -> ([b], [c])
mapAndUnzip a -> (b, c)
_ [] = ([], [])
mapAndUnzip a -> (b, c)
f (a
x:[a]
xs)
  = let (b
r1,  c
r2)  = a -> (b, c)
f a
x
        ([b]
rs1, [c]
rs2) = (a -> (b, c)) -> [a] -> ([b], [c])
forall a b c. (a -> (b, c)) -> [a] -> ([b], [c])
mapAndUnzip a -> (b, c)
f [a]
xs
    in
    (b
r1b -> [b] -> [b]
forall a. a -> [a] -> [a]
:[b]
rs1, c
r2c -> [c] -> [c]
forall a. a -> [a] -> [a]
:[c]
rs2)

mapAndUnzip3 :: (a -> (b, c, d)) -> [a] -> ([b], [c], [d])

mapAndUnzip3 :: forall a b c d. (a -> (b, c, d)) -> [a] -> ([b], [c], [d])
mapAndUnzip3 a -> (b, c, d)
_ [] = ([], [], [])
mapAndUnzip3 a -> (b, c, d)
f (a
x:[a]
xs)
  = let (b
r1,  c
r2,  d
r3)  = a -> (b, c, d)
f a
x
        ([b]
rs1, [c]
rs2, [d]
rs3) = (a -> (b, c, d)) -> [a] -> ([b], [c], [d])
forall a b c d. (a -> (b, c, d)) -> [a] -> ([b], [c], [d])
mapAndUnzip3 a -> (b, c, d)
f [a]
xs
    in
    (b
r1b -> [b] -> [b]
forall a. a -> [a] -> [a]
:[b]
rs1, c
r2c -> [c] -> [c]
forall a. a -> [a] -> [a]
:[c]
rs2, d
r3d -> [d] -> [d]
forall a. a -> [a] -> [a]
:[d]
rs3)

zipWithAndUnzip :: (a -> b -> (c,d)) -> [a] -> [b] -> ([c],[d])
zipWithAndUnzip :: forall a b c d. (a -> b -> (c, d)) -> [a] -> [b] -> ([c], [d])
zipWithAndUnzip a -> b -> (c, d)
f (a
a:[a]
as) (b
b:[b]
bs)
  = let (c
r1,  d
r2)  = a -> b -> (c, d)
f a
a b
b
        ([c]
rs1, [d]
rs2) = (a -> b -> (c, d)) -> [a] -> [b] -> ([c], [d])
forall a b c d. (a -> b -> (c, d)) -> [a] -> [b] -> ([c], [d])
zipWithAndUnzip a -> b -> (c, d)
f [a]
as [b]
bs
    in
    (c
r1c -> [c] -> [c]
forall a. a -> [a] -> [a]
:[c]
rs1, d
r2d -> [d] -> [d]
forall a. a -> [a] -> [a]
:[d]
rs2)
zipWithAndUnzip a -> b -> (c, d)
_ [a]
_ [b]
_ = ([],[])

-- | This has the effect of making the two lists have equal length by dropping
-- the tail of the longer one.
zipAndUnzip :: [a] -> [b] -> ([a],[b])
zipAndUnzip :: forall a b. [a] -> [b] -> ([a], [b])
zipAndUnzip (a
a:[a]
as) (b
b:[b]
bs)
  = let ([a]
rs1, [b]
rs2) = [a] -> [b] -> ([a], [b])
forall a b. [a] -> [b] -> ([a], [b])
zipAndUnzip [a]
as [b]
bs
    in
    (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
rs1, b
bb -> [b] -> [b]
forall a. a -> [a] -> [a]
:[b]
rs2)
zipAndUnzip [a]
_ [b]
_ = ([],[])

-- | @atLength atLen atEnd ls n@ unravels list @ls@ to position @n@. Precisely:
--
-- @
--  atLength atLenPred atEndPred ls n
--   | n < 0         = atLenPred ls
--   | length ls < n = atEndPred (n - length ls)
--   | otherwise     = atLenPred (drop n ls)
-- @
atLength :: ([a] -> b)   -- Called when length ls >= n, passed (drop n ls)
                         --    NB: arg passed to this function may be []
         -> b            -- Called when length ls <  n
         -> [a]
         -> Int
         -> b
atLength :: forall a b. ([a] -> b) -> b -> [a] -> Int -> b
atLength [a] -> b
atLenPred b
atEnd [a]
ls0 Int
n0
  | Int
n0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0    = [a] -> b
atLenPred [a]
ls0
  | Bool
otherwise = Int -> [a] -> b
go Int
n0 [a]
ls0
  where
    -- go's first arg n >= 0
    go :: Int -> [a] -> b
go Int
0 [a]
ls     = [a] -> b
atLenPred [a]
ls
    go Int
_ []     = b
atEnd           -- n > 0 here
    go Int
n (a
_:[a]
xs) = Int -> [a] -> b
go (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) [a]
xs

-- Some special cases of atLength:

-- | @(lengthExceeds xs n) = (length xs > n)@
lengthExceeds :: [a] -> Int -> Bool
lengthExceeds :: forall a. [a] -> Int -> Bool
lengthExceeds [a]
lst Int
n
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0
  = Bool
True
  | Bool
otherwise
  = ([a] -> Bool) -> Bool -> [a] -> Int -> Bool
forall a b. ([a] -> b) -> b -> [a] -> Int -> b
atLength [a] -> Bool
forall (f :: * -> *) a. Foldable f => f a -> Bool
notNull Bool
False [a]
lst Int
n

-- | @(lengthAtLeast xs n) = (length xs >= n)@
lengthAtLeast :: [a] -> Int -> Bool
lengthAtLeast :: forall a. [a] -> Int -> Bool
lengthAtLeast = ([a] -> Bool) -> Bool -> [a] -> Int -> Bool
forall a b. ([a] -> b) -> b -> [a] -> Int -> b
atLength (Bool -> [a] -> Bool
forall a b. a -> b -> a
const Bool
True) Bool
False

-- | @(lengthIs xs n) = (length xs == n)@
lengthIs :: [a] -> Int -> Bool
lengthIs :: forall a. [a] -> Int -> Bool
lengthIs [a]
lst Int
n
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0
  = Bool
False
  | Bool
otherwise
  = ([a] -> Bool) -> Bool -> [a] -> Int -> Bool
forall a b. ([a] -> b) -> b -> [a] -> Int -> b
atLength [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null Bool
False [a]
lst Int
n

-- | @(lengthIsNot xs n) = (length xs /= n)@
lengthIsNot :: [a] -> Int -> Bool
lengthIsNot :: forall a. [a] -> Int -> Bool
lengthIsNot [a]
lst Int
n
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = Bool
True
  | Bool
otherwise = ([a] -> Bool) -> Bool -> [a] -> Int -> Bool
forall a b. ([a] -> b) -> b -> [a] -> Int -> b
atLength [a] -> Bool
forall (f :: * -> *) a. Foldable f => f a -> Bool
notNull Bool
True [a]
lst Int
n

-- | @(lengthAtMost xs n) = (length xs <= n)@
lengthAtMost :: [a] -> Int -> Bool
lengthAtMost :: forall a. [a] -> Int -> Bool
lengthAtMost [a]
lst Int
n
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0
  = Bool
False
  | Bool
otherwise
  = ([a] -> Bool) -> Bool -> [a] -> Int -> Bool
forall a b. ([a] -> b) -> b -> [a] -> Int -> b
atLength [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null Bool
True [a]
lst Int
n

-- | @(lengthLessThan xs n) == (length xs < n)@
lengthLessThan :: [a] -> Int -> Bool
lengthLessThan :: forall a. [a] -> Int -> Bool
lengthLessThan = ([a] -> Bool) -> Bool -> [a] -> Int -> Bool
forall a b. ([a] -> b) -> b -> [a] -> Int -> b
atLength (Bool -> [a] -> Bool
forall a b. a -> b -> a
const Bool
False) Bool
True

listLengthCmp :: [a] -> Int -> Ordering
listLengthCmp :: forall a. [a] -> Int -> Ordering
listLengthCmp = ([a] -> Ordering) -> Ordering -> [a] -> Int -> Ordering
forall a b. ([a] -> b) -> b -> [a] -> Int -> b
atLength [a] -> Ordering
forall {a}. [a] -> Ordering
atLen Ordering
atEnd
 where
  atEnd :: Ordering
atEnd = Ordering
LT    -- Not yet seen 'n' elts, so list length is < n.

  atLen :: [a] -> Ordering
atLen []     = Ordering
EQ
  atLen [a]
_      = Ordering
GT

equalLength :: [a] -> [b] -> Bool
-- ^ True if length xs == length ys
equalLength :: forall a b. [a] -> [b] -> Bool
equalLength []     []     = Bool
True
equalLength (a
_:[a]
xs) (b
_:[b]
ys) = [a] -> [b] -> Bool
forall a b. [a] -> [b] -> Bool
equalLength [a]
xs [b]
ys
equalLength [a]
_      [b]
_      = Bool
False

compareLength :: [a] -> [b] -> Ordering
compareLength :: forall a b. [a] -> [b] -> Ordering
compareLength []     []     = Ordering
EQ
compareLength (a
_:[a]
xs) (b
_:[b]
ys) = [a] -> [b] -> Ordering
forall a b. [a] -> [b] -> Ordering
compareLength [a]
xs [b]
ys
compareLength []     [b]
_      = Ordering
LT
compareLength [a]
_      []     = Ordering
GT

leLength :: [a] -> [b] -> Bool
-- ^ True if length xs <= length ys
leLength :: forall a b. [a] -> [b] -> Bool
leLength [a]
xs [b]
ys = case [a] -> [b] -> Ordering
forall a b. [a] -> [b] -> Ordering
compareLength [a]
xs [b]
ys of
                   Ordering
LT -> Bool
True
                   Ordering
EQ -> Bool
True
                   Ordering
GT -> Bool
False

ltLength :: [a] -> [b] -> Bool
-- ^ True if length xs < length ys
ltLength :: forall a b. [a] -> [b] -> Bool
ltLength [a]
xs [b]
ys = case [a] -> [b] -> Ordering
forall a b. [a] -> [b] -> Ordering
compareLength [a]
xs [b]
ys of
                   Ordering
LT -> Bool
True
                   Ordering
EQ -> Bool
False
                   Ordering
GT -> Bool
False

----------------------------
singleton :: a -> [a]
singleton :: forall a. a -> [a]
singleton a
x = [a
x]

isSingleton :: [a] -> Bool
isSingleton :: forall a. [a] -> Bool
isSingleton [a
_] = Bool
True
isSingleton [a]
_   = Bool
False

notNull :: Foldable f => f a -> Bool
notNull :: forall (f :: * -> *) a. Foldable f => f a -> Bool
notNull = Bool -> Bool
not (Bool -> Bool) -> (f a -> Bool) -> f a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f a -> Bool
forall a. f a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null

-- | Utility function to go from a singleton list to it's element.
--
-- Wether or not the argument is a singleton list is only checked
-- in debug builds.
only :: [a] -> a
#if defined(DEBUG)
only [a] = a
#else
only :: forall a. [a] -> a
only (a
a:[a]
_) = a
a
#endif
only [a]
_ = String -> a
forall a. String -> a
panic String
"Util: only"

-- | Extract the single element of a list and panic with the given message if
-- there are more elements or the list was empty.
-- Like 'expectJust', but for lists.
expectOnly :: HasCallStack => String -> [a] -> a
{-# INLINE expectOnly #-}
#if defined(DEBUG)
expectOnly _   [a]   = a
#else
expectOnly :: forall a. HasCallStack => String -> [a] -> a
expectOnly String
_   (a
a:[a]
_) = a
a
#endif
expectOnly String
msg [a]
_     = String -> a
forall a. String -> a
panic (String
"expectOnly: " String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
msg)


-- | Split a list into chunks of /n/ elements
chunkList :: Int -> [a] -> [[a]]
chunkList :: forall a. Int -> [a] -> [[a]]
chunkList Int
_ [] = []
chunkList Int
n [a]
xs = [a]
as [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
chunkList Int
n [a]
bs where ([a]
as,[a]
bs) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt Int
n [a]
xs

-- | Replace the last element of a list with another element.
changeLast :: [a] -> a -> [a]
changeLast :: forall a. [a] -> a -> [a]
changeLast []     a
_  = String -> [a]
forall a. String -> a
panic String
"changeLast"
changeLast [a
_]    a
x  = [a
x]
changeLast (a
x:[a]
xs) a
x' = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> a -> [a]
forall a. [a] -> a -> [a]
changeLast [a]
xs a
x'

-- | Apply an effectful function to the last list element.
-- Assumes a non-empty list (panics otherwise).
mapLastM :: Functor f => (a -> f a) -> [a] -> f [a]
mapLastM :: forall (f :: * -> *) a. Functor f => (a -> f a) -> [a] -> f [a]
mapLastM a -> f a
_ [] = String -> f [a]
forall a. String -> a
panic String
"mapLastM: empty list"
mapLastM a -> f a
f [a
x] = (\a
x' -> [a
x']) (a -> [a]) -> f a -> f [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f a
f a
x
mapLastM a -> f a
f (a
x:[a]
xs) = (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> f [a] -> f [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f a) -> [a] -> f [a]
forall (f :: * -> *) a. Functor f => (a -> f a) -> [a] -> f [a]
mapLastM a -> f a
f [a]
xs

mapAccumM :: (Monad m) => (r -> a -> m (r, b)) -> r -> [a] -> m (r, [b])
mapAccumM :: forall (m :: * -> *) r a b.
Monad m =>
(r -> a -> m (r, b)) -> r -> [a] -> m (r, [b])
mapAccumM r -> a -> m (r, b)
f = r -> [a] -> m (r, [b])
go
  where
    go :: r -> [a] -> m (r, [b])
go r
acc [] = (r, [b]) -> m (r, [b])
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (r
acc,[])
    go r
acc (a
x:[a]
xs) = do
      (r
acc',b
y) <- r -> a -> m (r, b)
f r
acc a
x
      (r
acc'',[b]
ys) <- r -> [a] -> m (r, [b])
go r
acc' [a]
xs
      (r, [b]) -> m (r, [b])
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (r
acc'', b
yb -> [b] -> [b]
forall a. a -> [a] -> [a]
:[b]
ys)

whenNonEmpty :: Applicative m => [a] -> (NonEmpty a -> m ()) -> m ()
whenNonEmpty :: forall (m :: * -> *) a.
Applicative m =>
[a] -> (NonEmpty a -> m ()) -> m ()
whenNonEmpty []     NonEmpty a -> m ()
_ = () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
whenNonEmpty (a
x:[a]
xs) NonEmpty a -> m ()
f = NonEmpty a -> m ()
f (a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
xs)

-- | Merge an unsorted list of sorted lists, for example:
--
--  > mergeListsBy compare [ [2,5,15], [1,10,100] ] = [1,2,5,10,15,100]
--
--  \( O(n \log{} k) \)
mergeListsBy :: forall a. (a -> a -> Ordering) -> [[a]] -> [a]
mergeListsBy :: forall a. (a -> a -> Ordering) -> [[a]] -> [a]
mergeListsBy a -> a -> Ordering
cmp [[a]]
lists | Bool
debugIsOn, Bool -> Bool
not (([a] -> Bool) -> [[a]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all [a] -> Bool
sorted [[a]]
lists) =
  -- When debugging is on, we check that the input lists are sorted.
  String -> [a]
forall a. String -> a
panic String
"mergeListsBy: input lists must be sorted"
  where sorted :: [a] -> Bool
sorted = (a -> a -> Ordering) -> [a] -> Bool
forall a. (a -> a -> Ordering) -> [a] -> Bool
isSortedBy a -> a -> Ordering
cmp
mergeListsBy a -> a -> Ordering
cmp [[a]]
all_lists = [[a]] -> [a]
merge_lists [[a]]
all_lists
  where
    -- Implements "Iterative 2-Way merge" described at
    -- https://en.wikipedia.org/wiki/K-way_merge_algorithm

    -- Merge two sorted lists into one in O(n).
    merge2 :: [a] -> [a] -> [a]
    merge2 :: [a] -> [a] -> [a]
merge2 [] [a]
ys = [a]
ys
    merge2 [a]
xs [] = [a]
xs
    merge2 (a
x:[a]
xs) (a
y:[a]
ys) =
      case a -> a -> Ordering
cmp a
x a
y of
        Ordering
GT -> a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge2 (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) [a]
ys
        Ordering
_  -> a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge2 [a]
xs (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys)

    -- Merge the first list with the second, the third with the fourth, and so
    -- on. The output has half as much lists as the input.
    merge_neighbours :: [[a]] -> [[a]]
    merge_neighbours :: [[a]] -> [[a]]
merge_neighbours []   = []
    merge_neighbours [[a]
xs] = [[a]
xs]
    merge_neighbours ([a]
xs : [a]
ys : [[a]]
lists) =
      [a] -> [a] -> [a]
merge2 [a]
xs [a]
ys [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: [[a]] -> [[a]]
merge_neighbours [[a]]
lists

    -- Since 'merge_neighbours' halves the amount of lists in each iteration,
    -- we perform O(log k) iteration. Each iteration is O(n). The total running
    -- time is therefore O(n log k).
    merge_lists :: [[a]] -> [a]
    merge_lists :: [[a]] -> [a]
merge_lists [[a]]
lists =
      case [[a]] -> [[a]]
merge_neighbours [[a]]
lists of
        []     -> []
        [[a]
xs]   -> [a]
xs
        [[a]]
lists' -> [[a]] -> [a]
merge_lists [[a]]
lists'

isSortedBy :: (a -> a -> Ordering) -> [a] -> Bool
isSortedBy :: forall a. (a -> a -> Ordering) -> [a] -> Bool
isSortedBy a -> a -> Ordering
cmp = [a] -> Bool
sorted
  where
    sorted :: [a] -> Bool
sorted [] = Bool
True
    sorted [a
_] = Bool
True
    sorted (a
x:a
y:[a]
xs) = a -> a -> Ordering
cmp a
x a
y Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
/= Ordering
GT Bool -> Bool -> Bool
&& [a] -> Bool
sorted (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)
{-
************************************************************************
*                                                                      *
\subsubsection{Sort utils}
*                                                                      *
************************************************************************
-}

minWith :: Ord b => (a -> b) -> [a] -> a
minWith :: forall b a. Ord b => (a -> b) -> [a] -> a
minWith a -> b
get_key [a]
xs = Bool -> ([a] -> a) -> [a] -> a
forall a. HasCallStack => Bool -> a -> a
assert (Bool -> Bool
not ([a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
xs) )
                     [a] -> a
forall a. HasCallStack => [a] -> a
head ((a -> b) -> [a] -> [a]
forall b a. Ord b => (a -> b) -> [a] -> [a]
sortWith a -> b
get_key [a]
xs)

nubSort :: Ord a => [a] -> [a]
nubSort :: forall a. Ord a => [a] -> [a]
nubSort = Set a -> [a]
forall a. Set a -> [a]
Set.toAscList (Set a -> [a]) -> ([a] -> Set a) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Set a
forall a. Ord a => [a] -> Set a
Set.fromList

-- | Remove duplicates but keep elements in order.
--   O(n * log n)
ordNub :: Ord a => [a] -> [a]
ordNub :: forall a. Ord a => [a] -> [a]
ordNub [a]
xs = (a -> a) -> [a] -> [a]
forall b a. Ord b => (a -> b) -> [a] -> [a]
ordNubOn a -> a
forall a. a -> a
id [a]
xs

-- | Remove duplicates but keep elements in order.
--   O(n * log n)
ordNubOn :: Ord b => (a -> b) -> [a] -> [a]
ordNubOn :: forall b a. Ord b => (a -> b) -> [a] -> [a]
ordNubOn a -> b
f [a]
xs
  = Set b -> [a] -> [a]
go Set b
forall a. Set a
Set.empty [a]
xs
  where
    go :: Set b -> [a] -> [a]
go Set b
_ [] = []
    go Set b
s (a
x:[a]
xs)
      | b -> Set b -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member (a -> b
f a
x) Set b
s = Set b -> [a] -> [a]
go Set b
s [a]
xs
      | Bool
otherwise = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: Set b -> [a] -> [a]
go (b -> Set b -> Set b
forall a. Ord a => a -> Set a -> Set a
Set.insert (a -> b
f a
x) Set b
s) [a]
xs


{-
************************************************************************
*                                                                      *
\subsection[Utils-transitive-closure]{Transitive closure}
*                                                                      *
************************************************************************

This algorithm for transitive closure is straightforward, albeit quadratic.
-}

transitiveClosure :: (a -> [a])         -- Successor function
                  -> (a -> a -> Bool)   -- Equality predicate
                  -> [a]
                  -> [a]                -- The transitive closure

transitiveClosure :: forall a. (a -> [a]) -> (a -> a -> Bool) -> [a] -> [a]
transitiveClosure a -> [a]
succ a -> a -> Bool
eq [a]
xs
 = [a] -> [a] -> [a]
go [] [a]
xs
 where
   go :: [a] -> [a] -> [a]
go [a]
done []                      = [a]
done
   go [a]
done (a
x:[a]
xs) | a
x a -> [a] -> Bool
`is_in` [a]
done = [a] -> [a] -> [a]
go [a]
done [a]
xs
                  | Bool
otherwise      = [a] -> [a] -> [a]
go (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
done) (a -> [a]
succ a
x [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
xs)

   a
_ is_in :: a -> [a] -> Bool
`is_in` []                 = Bool
False
   a
x `is_in` (a
y:[a]
ys) | a -> a -> Bool
eq a
x a
y    = Bool
True
                    | Bool
otherwise = a
x a -> [a] -> Bool
`is_in` [a]
ys

{-
************************************************************************
*                                                                      *
\subsection[Utils-accum]{Accumulating}
*                                                                      *
************************************************************************

A combination of foldl with zip.  It works with equal length lists.
-}

foldl2 :: (acc -> a -> b -> acc) -> acc -> [a] -> [b] -> acc
foldl2 :: forall acc a b. (acc -> a -> b -> acc) -> acc -> [a] -> [b] -> acc
foldl2 acc -> a -> b -> acc
_ acc
z [] [] = acc
z
foldl2 acc -> a -> b -> acc
k acc
z (a
a:[a]
as) (b
b:[b]
bs) = (acc -> a -> b -> acc) -> acc -> [a] -> [b] -> acc
forall acc a b. (acc -> a -> b -> acc) -> acc -> [a] -> [b] -> acc
foldl2 acc -> a -> b -> acc
k (acc -> a -> b -> acc
k acc
z a
a b
b) [a]
as [b]
bs
foldl2 acc -> a -> b -> acc
_ acc
_ [a]
_      [b]
_      = String -> acc
forall a. String -> a
panic String
"Util: foldl2"

all2 :: (a -> b -> Bool) -> [a] -> [b] -> Bool
-- True if the lists are the same length, and
-- all corresponding elements satisfy the predicate
all2 :: forall a b. (a -> b -> Bool) -> [a] -> [b] -> Bool
all2 a -> b -> Bool
_ []     []     = Bool
True
all2 a -> b -> Bool
p (a
x:[a]
xs) (b
y:[b]
ys) = a -> b -> Bool
p a
x b
y Bool -> Bool -> Bool
&& (a -> b -> Bool) -> [a] -> [b] -> Bool
forall a b. (a -> b -> Bool) -> [a] -> [b] -> Bool
all2 a -> b -> Bool
p [a]
xs [b]
ys
all2 a -> b -> Bool
_ [a]
_      [b]
_      = Bool
False

-- Count the number of times a predicate is true

count :: (a -> Bool) -> [a] -> Int
count :: forall a. (a -> Bool) -> [a] -> Int
count a -> Bool
p = Int -> [a] -> Int
go Int
0
  where go :: Int -> [a] -> Int
go !Int
n [] = Int
n
        go !Int
n (a
x:[a]
xs) | a -> Bool
p a
x       = Int -> [a] -> Int
go (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) [a]
xs
                     | Bool
otherwise = Int -> [a] -> Int
go Int
n [a]
xs

countWhile :: (a -> Bool) -> [a] -> Int
-- Length of an /initial prefix/ of the list satisfying p
countWhile :: forall a. (a -> Bool) -> [a] -> Int
countWhile a -> Bool
p = Int -> [a] -> Int
go Int
0
  where go :: Int -> [a] -> Int
go !Int
n (a
x:[a]
xs) | a -> Bool
p a
x = Int -> [a] -> Int
go (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) [a]
xs
        go !Int
n [a]
_            = Int
n

{-
@splitAt@, @take@, and @drop@ but with length of another
list giving the break-off point:
-}

takeList :: [b] -> [a] -> [a]
-- (takeList as bs) trims bs to the be same length
-- as as, unless as is longer in which case it's a no-op
takeList :: forall b a. [b] -> [a] -> [a]
takeList [] [a]
_ = []
takeList (b
_:[b]
xs) [a]
ls =
   case [a]
ls of
     [] -> []
     (a
y:[a]
ys) -> a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [b] -> [a] -> [a]
forall b a. [b] -> [a] -> [a]
takeList [b]
xs [a]
ys

dropList :: [b] -> [a] -> [a]
dropList :: forall b a. [b] -> [a] -> [a]
dropList [] [a]
xs    = [a]
xs
dropList [b]
_  xs :: [a]
xs@[] = [a]
xs
dropList (b
_:[b]
xs) (a
_:[a]
ys) = [b] -> [a] -> [a]
forall b a. [b] -> [a] -> [a]
dropList [b]
xs [a]
ys


-- | Given two lists xs and ys, return `splitAt (length xs) ys`.
splitAtList :: [b] -> [a] -> ([a], [a])
splitAtList :: forall b a. [b] -> [a] -> ([a], [a])
splitAtList [b]
xs [a]
ys = Int# -> [b] -> [a] -> ([a], [a])
go Int#
0# [b]
xs [a]
ys
   where
      -- we are careful to avoid allocating when there are no leftover
      -- arguments: in this case we can return "ys" directly (cf #18535)
      --
      -- We make `xs` strict because in the general case `ys` isn't `[]` so we
      -- will have to evaluate `xs` anyway.
      go :: Int# -> [b] -> [a] -> ([a], [a])
go Int#
_  ![b]
_     []     = ([a]
ys, [])             -- length ys <= length xs
      go Int#
n  []     [a]
bs     = (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take (Int# -> Int
I# Int#
n) [a]
ys, [a]
bs) -- = splitAt n ys
      go Int#
n  (b
_:[b]
as) (a
_:[a]
bs) = Int# -> [b] -> [a] -> ([a], [a])
go (Int#
n Int# -> Int# -> Int#
+# Int#
1#) [b]
as [a]
bs

-- | drop from the end of a list
dropTail :: Int -> [a] -> [a]
-- Specification: dropTail n = reverse . drop n . reverse
-- Better implementation due to Joachim Breitner
-- http://www.joachim-breitner.de/blog/archives/600-On-taking-the-last-n-elements-of-a-list.html
dropTail :: forall a. Int -> [a] -> [a]
dropTail Int
n [a]
xs
  = [a] -> [a] -> [a]
forall b a. [b] -> [a] -> [a]
go (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
drop Int
n [a]
xs) [a]
xs
  where
    go :: [a] -> [a] -> [a]
go (a
_:[a]
ys) (a
x:[a]
xs) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
go [a]
ys [a]
xs
    go [a]
_      [a]
_      = []  -- Stop when ys runs out
                           -- It'll always run out before xs does

-- dropWhile from the end of a list. This is similar to Data.List.dropWhileEnd,
-- but is lazy in the elements and strict in the spine. For reasonably short lists,
-- such as path names and typical lines of text, dropWhileEndLE is generally
-- faster than dropWhileEnd. Its advantage is magnified when the predicate is
-- expensive--using dropWhileEndLE isSpace to strip the space off a line of text
-- is generally much faster than using dropWhileEnd isSpace for that purpose.
-- Specification: dropWhileEndLE p = reverse . dropWhile p . reverse
-- Pay attention to the short-circuit (&&)! The order of its arguments is the only
-- difference between dropWhileEnd and dropWhileEndLE.
dropWhileEndLE :: (a -> Bool) -> [a] -> [a]
dropWhileEndLE :: forall a. (a -> Bool) -> [a] -> [a]
dropWhileEndLE a -> Bool
p = (a -> [a] -> [a]) -> [a] -> [a] -> [a]
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\a
x [a]
r -> if [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
r Bool -> Bool -> Bool
&& a -> Bool
p a
x then [] else a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
r) []

-- | @spanEnd p l == reverse (span p (reverse l))@. The first list
-- returns actually comes after the second list (when you look at the
-- input list).
spanEnd :: (a -> Bool) -> [a] -> ([a], [a])
spanEnd :: forall a. (a -> Bool) -> [a] -> ([a], [a])
spanEnd a -> Bool
p [a]
l = [a] -> [a] -> [a] -> [a] -> ([a], [a])
go [a]
l [] [] [a]
l
  where go :: [a] -> [a] -> [a] -> [a] -> ([a], [a])
go [a]
yes [a]
_rev_yes [a]
rev_no [] = ([a]
yes, [a] -> [a]
forall a. [a] -> [a]
reverse [a]
rev_no)
        go [a]
yes [a]
rev_yes  [a]
rev_no (a
x:[a]
xs)
          | a -> Bool
p a
x       = [a] -> [a] -> [a] -> [a] -> ([a], [a])
go [a]
yes (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
rev_yes) [a]
rev_no                  [a]
xs
          | Bool
otherwise = [a] -> [a] -> [a] -> [a] -> ([a], [a])
go [a]
xs  []            (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
rev_yes [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
rev_no) [a]
xs

-- | Get the last two elements in a list. Partial!
{-# INLINE last2 #-}
last2 :: [a] -> (a,a)
last2 :: forall a. [a] -> (a, a)
last2 = ((a, a) -> a -> (a, a)) -> (a, a) -> [a] -> (a, a)
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\(a
_,a
x2) a
x -> (a
x2,a
x)) (a
forall {a}. a
partialError,a
forall {a}. a
partialError)
  where
    partialError :: a
partialError = String -> a
forall a. String -> a
panic String
"last2 - list length less than two"

lastMaybe :: [a] -> Maybe a
lastMaybe :: forall a. [a] -> Maybe a
lastMaybe [] = Maybe a
forall a. Maybe a
Nothing
lastMaybe [a]
xs = a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$ [a] -> a
forall a. HasCallStack => [a] -> a
last [a]
xs

-- | @onJust x m f@ applies f to the value inside the Just or returns the default.
onJust :: b -> Maybe a -> (a->b) -> b
onJust :: forall b a. b -> Maybe a -> (a -> b) -> b
onJust b
dflt = ((a -> b) -> Maybe a -> b) -> Maybe a -> (a -> b) -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip (b -> (a -> b) -> Maybe a -> b
forall b a. b -> (a -> b) -> Maybe a -> b
maybe b
dflt)

-- | Split a list into its last element and the initial part of the list.
-- @snocView xs = Just (init xs, last xs)@ for non-empty lists.
-- @snocView xs = Nothing@ otherwise.
-- Unless both parts of the result are guaranteed to be used
-- prefer separate calls to @last@ + @init@.
-- If you are guaranteed to use both, this will
-- be more efficient.
snocView :: [a] -> Maybe ([a],a)
snocView :: forall a. [a] -> Maybe ([a], a)
snocView [] = Maybe ([a], a)
forall a. Maybe a
Nothing
snocView [a]
xs
    | ([a]
xs,a
x) <- [a] -> ([a], a)
forall a. [a] -> ([a], a)
go [a]
xs
    = ([a], a) -> Maybe ([a], a)
forall a. a -> Maybe a
Just ([a]
xs,a
x)
  where
    go :: [a] -> ([a],a)
    go :: forall a. [a] -> ([a], a)
go [a
x] = ([],a
x)
    go (a
x:[a]
xs)
        | !([a]
xs',a
x') <- [a] -> ([a], a)
forall a. [a] -> ([a], a)
go [a]
xs
        = (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs', a
x')
    go [] = String -> ([a], a)
forall a. HasCallStack => String -> a
error String
"impossible"

split :: Char -> String -> [String]
split :: Char -> String -> [String]
split Char
c String
s = case String
rest of
                []     -> [String
chunk]
                Char
_:String
rest -> String
chunk String -> [String] -> [String]
forall a. a -> [a] -> [a]
: Char -> String -> [String]
split Char
c String
rest
  where (String
chunk, String
rest) = (Char -> Bool) -> String -> (String, String)
forall a. (a -> Bool) -> [a] -> ([a], [a])
break (Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
==Char
c) String
s

-- | Convert a word to title case by capitalising the first letter
capitalise :: String -> String
capitalise :: String -> String
capitalise [] = []
capitalise (Char
c:String
cs) = Char -> Char
toUpper Char
c Char -> String -> String
forall a. a -> [a] -> [a]
: String
cs


{-
************************************************************************
*                                                                      *
\subsection[Utils-comparison]{Comparisons}
*                                                                      *
************************************************************************
-}

isEqual :: Ordering -> Bool
-- Often used in (isEqual (a `compare` b))
isEqual :: Ordering -> Bool
isEqual Ordering
GT = Bool
False
isEqual Ordering
EQ = Bool
True
isEqual Ordering
LT = Bool
False

thenCmp :: Ordering -> Ordering -> Ordering
{-# INLINE thenCmp #-}
thenCmp :: Ordering -> Ordering -> Ordering
thenCmp Ordering
EQ       Ordering
ordering = Ordering
ordering
thenCmp Ordering
ordering Ordering
_        = Ordering
ordering

eqListBy :: (a->a->Bool) -> [a] -> [a] -> Bool
eqListBy :: forall a. (a -> a -> Bool) -> [a] -> [a] -> Bool
eqListBy a -> a -> Bool
_  []     []     = Bool
True
eqListBy a -> a -> Bool
eq (a
x:[a]
xs) (a
y:[a]
ys) = a -> a -> Bool
eq a
x a
y Bool -> Bool -> Bool
&& (a -> a -> Bool) -> [a] -> [a] -> Bool
forall a. (a -> a -> Bool) -> [a] -> [a] -> Bool
eqListBy a -> a -> Bool
eq [a]
xs [a]
ys
eqListBy a -> a -> Bool
_  [a]
_      [a]
_      = Bool
False

eqMaybeBy :: (a ->a->Bool) -> Maybe a -> Maybe a -> Bool
eqMaybeBy :: forall a. (a -> a -> Bool) -> Maybe a -> Maybe a -> Bool
eqMaybeBy a -> a -> Bool
_  Maybe a
Nothing  Maybe a
Nothing  = Bool
True
eqMaybeBy a -> a -> Bool
eq (Just a
x) (Just a
y) = a -> a -> Bool
eq a
x a
y
eqMaybeBy a -> a -> Bool
_  Maybe a
_        Maybe a
_        = Bool
False

cmpList :: (a -> a -> Ordering) -> [a] -> [a] -> Ordering
    -- `cmpList' uses a user-specified comparer

cmpList :: forall a. (a -> a -> Ordering) -> [a] -> [a] -> Ordering
cmpList a -> a -> Ordering
_   []     [] = Ordering
EQ
cmpList a -> a -> Ordering
_   []     [a]
_  = Ordering
LT
cmpList a -> a -> Ordering
_   [a]
_      [] = Ordering
GT
cmpList a -> a -> Ordering
cmp (a
a:[a]
as) (a
b:[a]
bs)
  = case a -> a -> Ordering
cmp a
a a
b of { Ordering
EQ -> (a -> a -> Ordering) -> [a] -> [a] -> Ordering
forall a. (a -> a -> Ordering) -> [a] -> [a] -> Ordering
cmpList a -> a -> Ordering
cmp [a]
as [a]
bs; Ordering
xxx -> Ordering
xxx }

removeSpaces :: String -> String
removeSpaces :: String -> String
removeSpaces = (Char -> Bool) -> String -> String
forall a. (a -> Bool) -> [a] -> [a]
dropWhileEndLE Char -> Bool
isSpace (String -> String) -> (String -> String) -> String -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Char -> Bool) -> String -> String
forall a. (a -> Bool) -> [a] -> [a]
dropWhile Char -> Bool
isSpace

-- Boolean operators lifted to Applicative
(<&&>) :: Applicative f => f Bool -> f Bool -> f Bool
<&&> :: forall (f :: * -> *). Applicative f => f Bool -> f Bool -> f Bool
(<&&>) = (Bool -> Bool -> Bool) -> f Bool -> f Bool -> f Bool
forall a b c. (a -> b -> c) -> f a -> f b -> f c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Bool -> Bool -> Bool
(&&)
infixr 3 <&&> -- same as (&&)

(<||>) :: Applicative f => f Bool -> f Bool -> f Bool
<||> :: forall (f :: * -> *). Applicative f => f Bool -> f Bool -> f Bool
(<||>) = (Bool -> Bool -> Bool) -> f Bool -> f Bool -> f Bool
forall a b c. (a -> b -> c) -> f a -> f b -> f c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Bool -> Bool -> Bool
(||)
infixr 2 <||> -- same as (||)

{-
************************************************************************
*                                                                      *
\subsection{Edit distance}
*                                                                      *
************************************************************************
-}

-- | Find the "restricted" Damerau-Levenshtein edit distance between two strings.
-- See: <http://en.wikipedia.org/wiki/Damerau-Levenshtein_distance>.
-- Based on the algorithm presented in "A Bit-Vector Algorithm for Computing
-- Levenshtein and Damerau Edit Distances" in PSC'02 (Heikki Hyyro).
-- See http://www.cs.uta.fi/~helmu/pubs/psc02.pdf and
--     http://www.cs.uta.fi/~helmu/pubs/PSCerr.html for an explanation
restrictedDamerauLevenshteinDistance :: String -> String -> Int
restrictedDamerauLevenshteinDistance :: String -> String -> Int
restrictedDamerauLevenshteinDistance String
str1 String
str2
  = Int -> Int -> String -> String -> Int
restrictedDamerauLevenshteinDistanceWithLengths Int
m Int
n String
str1 String
str2
  where
    m :: Int
m = String -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length String
str1
    n :: Int
n = String -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length String
str2

restrictedDamerauLevenshteinDistanceWithLengths
  :: Int -> Int -> String -> String -> Int
restrictedDamerauLevenshteinDistanceWithLengths :: Int -> Int -> String -> String -> Int
restrictedDamerauLevenshteinDistanceWithLengths Int
m Int
n String
str1 String
str2
  | Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
n
  = if Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
32 -- n must be larger so this check is sufficient
    then Word32 -> Int -> Int -> String -> String -> Int
forall bv.
(Bits bv, Num bv) =>
bv -> Int -> Int -> String -> String -> Int
restrictedDamerauLevenshteinDistance' (Word32
forall a. HasCallStack => a
undefined :: Word32) Int
m Int
n String
str1 String
str2
    else Integer -> Int -> Int -> String -> String -> Int
forall bv.
(Bits bv, Num bv) =>
bv -> Int -> Int -> String -> String -> Int
restrictedDamerauLevenshteinDistance' (Integer
forall a. HasCallStack => a
undefined :: Integer) Int
m Int
n String
str1 String
str2

  | Bool
otherwise
  = if Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
32 -- m must be larger so this check is sufficient
    then Word32 -> Int -> Int -> String -> String -> Int
forall bv.
(Bits bv, Num bv) =>
bv -> Int -> Int -> String -> String -> Int
restrictedDamerauLevenshteinDistance' (Word32
forall a. HasCallStack => a
undefined :: Word32) Int
n Int
m String
str2 String
str1
    else Integer -> Int -> Int -> String -> String -> Int
forall bv.
(Bits bv, Num bv) =>
bv -> Int -> Int -> String -> String -> Int
restrictedDamerauLevenshteinDistance' (Integer
forall a. HasCallStack => a
undefined :: Integer) Int
n Int
m String
str2 String
str1

restrictedDamerauLevenshteinDistance'
  :: (Bits bv, Num bv) => bv -> Int -> Int -> String -> String -> Int
restrictedDamerauLevenshteinDistance' :: forall bv.
(Bits bv, Num bv) =>
bv -> Int -> Int -> String -> String -> Int
restrictedDamerauLevenshteinDistance' bv
_bv_dummy Int
m Int
n String
str1 String
str2
  | [] <- String
str1 = Int
n
  | Bool
otherwise  = (bv, bv, bv, bv, Int) -> Int
forall {a} {b} {c} {d} {e}. (a, b, c, d, e) -> e
extractAnswer ((bv, bv, bv, bv, Int) -> Int) -> (bv, bv, bv, bv, Int) -> Int
forall a b. (a -> b) -> a -> b
$
                 ((bv, bv, bv, bv, Int) -> Char -> (bv, bv, bv, bv, Int))
-> (bv, bv, bv, bv, Int) -> String -> (bv, bv, bv, bv, Int)
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (IntMap bv
-> bv
-> bv
-> (bv, bv, bv, bv, Int)
-> Char
-> (bv, bv, bv, bv, Int)
forall bv.
(Bits bv, Num bv) =>
IntMap bv
-> bv
-> bv
-> (bv, bv, bv, bv, Int)
-> Char
-> (bv, bv, bv, bv, Int)
restrictedDamerauLevenshteinDistanceWorker
                             (String -> IntMap bv
forall bv. (Bits bv, Num bv) => String -> IntMap bv
matchVectors String
str1) bv
top_bit_mask bv
vector_mask)
                        (bv
0, bv
0, bv
m_ones, bv
0, Int
m) String
str2
  where
    m_ones :: bv
m_ones@bv
vector_mask = (bv
2 bv -> Int -> bv
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
m) bv -> bv -> bv
forall a. Num a => a -> a -> a
- bv
1
    top_bit_mask :: bv
top_bit_mask = (bv
1 bv -> Int -> bv
forall a. Bits a => a -> Int -> a
`shiftL` (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)) bv -> bv -> bv
forall a. a -> a -> a
`asTypeOf` bv
_bv_dummy
    extractAnswer :: (a, b, c, d, e) -> e
extractAnswer (a
_, b
_, c
_, d
_, e
distance) = e
distance

restrictedDamerauLevenshteinDistanceWorker
      :: (Bits bv, Num bv) => IM.IntMap bv -> bv -> bv
      -> (bv, bv, bv, bv, Int) -> Char -> (bv, bv, bv, bv, Int)
restrictedDamerauLevenshteinDistanceWorker :: forall bv.
(Bits bv, Num bv) =>
IntMap bv
-> bv
-> bv
-> (bv, bv, bv, bv, Int)
-> Char
-> (bv, bv, bv, bv, Int)
restrictedDamerauLevenshteinDistanceWorker IntMap bv
str1_mvs bv
top_bit_mask bv
vector_mask
                                           (bv
pm, bv
d0, bv
vp, bv
vn, Int
distance) Char
char2
  = IntMap bv -> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. a -> b -> b
seq IntMap bv
str1_mvs ((bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int))
-> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. (a -> b) -> a -> b
$ bv -> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. a -> b -> b
seq bv
top_bit_mask ((bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int))
-> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. (a -> b) -> a -> b
$ bv -> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. a -> b -> b
seq bv
vector_mask ((bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int))
-> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. (a -> b) -> a -> b
$
    bv -> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. a -> b -> b
seq bv
pm' ((bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int))
-> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. (a -> b) -> a -> b
$ bv -> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. a -> b -> b
seq bv
d0' ((bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int))
-> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. (a -> b) -> a -> b
$ bv -> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. a -> b -> b
seq bv
vp' ((bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int))
-> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. (a -> b) -> a -> b
$ bv -> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. a -> b -> b
seq bv
vn' ((bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int))
-> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. (a -> b) -> a -> b
$
    Int -> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. a -> b -> b
seq Int
distance'' ((bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int))
-> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. (a -> b) -> a -> b
$ Char -> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. a -> b -> b
seq Char
char2 ((bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int))
-> (bv, bv, bv, bv, Int) -> (bv, bv, bv, bv, Int)
forall a b. (a -> b) -> a -> b
$
    (bv
pm', bv
d0', bv
vp', bv
vn', Int
distance'')
  where
    pm' :: bv
pm' = bv -> Int -> IntMap bv -> bv
forall a. a -> Int -> IntMap a -> a
IM.findWithDefault bv
0 (Char -> Int
ord Char
char2) IntMap bv
str1_mvs

    d0' :: bv
d0' = ((((bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
sizedComplement bv
vector_mask bv
d0) bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.&. bv
pm') bv -> Int -> bv
forall a. Bits a => a -> Int -> a
`shiftL` Int
1) bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.&. bv
pm)
      bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.|. ((((bv
pm' bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.&. bv
vp) bv -> bv -> bv
forall a. Num a => a -> a -> a
+ bv
vp) bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.&. bv
vector_mask) bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
`xor` bv
vp) bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.|. bv
pm' bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.|. bv
vn
          -- No need to mask the shiftL because of the restricted range of pm

    hp' :: bv
hp' = bv
vn bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.|. bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
sizedComplement bv
vector_mask (bv
d0' bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.|. bv
vp)
    hn' :: bv
hn' = bv
d0' bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.&. bv
vp

    hp'_shift :: bv
hp'_shift = ((bv
hp' bv -> Int -> bv
forall a. Bits a => a -> Int -> a
`shiftL` Int
1) bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.|. bv
1) bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.&. bv
vector_mask
    hn'_shift :: bv
hn'_shift = (bv
hn' bv -> Int -> bv
forall a. Bits a => a -> Int -> a
`shiftL` Int
1) bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.&. bv
vector_mask
    vp' :: bv
vp' = bv
hn'_shift bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.|. bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
sizedComplement bv
vector_mask (bv
d0' bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.|. bv
hp'_shift)
    vn' :: bv
vn' = bv
d0' bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.&. bv
hp'_shift

    distance' :: Int
distance' = if bv
hp' bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.&. bv
top_bit_mask bv -> bv -> Bool
forall a. Eq a => a -> a -> Bool
/= bv
0 then Int
distance Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 else Int
distance
    distance'' :: Int
distance'' = if bv
hn' bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
.&. bv
top_bit_mask bv -> bv -> Bool
forall a. Eq a => a -> a -> Bool
/= bv
0 then Int
distance' Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 else Int
distance'

sizedComplement :: Bits bv => bv -> bv -> bv
sizedComplement :: forall bv. Bits bv => bv -> bv -> bv
sizedComplement bv
vector_mask bv
vect = bv
vector_mask bv -> bv -> bv
forall bv. Bits bv => bv -> bv -> bv
`xor` bv
vect

matchVectors :: (Bits bv, Num bv) => String -> IM.IntMap bv
matchVectors :: forall bv. (Bits bv, Num bv) => String -> IntMap bv
matchVectors = (Int, IntMap bv) -> IntMap bv
forall a b. (a, b) -> b
snd ((Int, IntMap bv) -> IntMap bv)
-> (String -> (Int, IntMap bv)) -> String -> IntMap bv
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, IntMap bv) -> Char -> (Int, IntMap bv))
-> (Int, IntMap bv) -> String -> (Int, IntMap bv)
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (Int, IntMap bv) -> Char -> (Int, IntMap bv)
forall {a} {a}.
(Bits a, Integral a, Num a) =>
(a, IntMap a) -> Char -> (a, IntMap a)
go (Int
0 :: Int, IntMap bv
forall a. IntMap a
IM.empty)
  where
    go :: (a, IntMap a) -> Char -> (a, IntMap a)
go (a
ix, IntMap a
im) Char
char = let ix' :: a
ix' = a
ix a -> a -> a
forall a. Num a => a -> a -> a
+ a
1
                           im' :: IntMap a
im' = (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
forall a. (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
IM.insertWith a -> a -> a
forall bv. Bits bv => bv -> bv -> bv
(.|.) (Char -> Int
ord Char
char) (a
2 a -> a -> a
forall a b. (Num a, Integral b) => a -> b -> a
^ a
ix) IntMap a
im
                       in a -> (a, IntMap a) -> (a, IntMap a)
forall a b. a -> b -> b
seq a
ix' ((a, IntMap a) -> (a, IntMap a)) -> (a, IntMap a) -> (a, IntMap a)
forall a b. (a -> b) -> a -> b
$ IntMap a -> (a, IntMap a) -> (a, IntMap a)
forall a b. a -> b -> b
seq IntMap a
im' ((a, IntMap a) -> (a, IntMap a)) -> (a, IntMap a) -> (a, IntMap a)
forall a b. (a -> b) -> a -> b
$ (a
ix', IntMap a
im')

{-# SPECIALIZE INLINE restrictedDamerauLevenshteinDistance'
                      :: Word32 -> Int -> Int -> String -> String -> Int #-}
{-# SPECIALIZE INLINE restrictedDamerauLevenshteinDistance'
                      :: Integer -> Int -> Int -> String -> String -> Int #-}

{-# SPECIALIZE restrictedDamerauLevenshteinDistanceWorker
               :: IM.IntMap Word32 -> Word32 -> Word32
               -> (Word32, Word32, Word32, Word32, Int)
               -> Char -> (Word32, Word32, Word32, Word32, Int) #-}
{-# SPECIALIZE restrictedDamerauLevenshteinDistanceWorker
               :: IM.IntMap Integer -> Integer -> Integer
               -> (Integer, Integer, Integer, Integer, Int)
               -> Char -> (Integer, Integer, Integer, Integer, Int) #-}

{-# SPECIALIZE INLINE sizedComplement :: Word32 -> Word32 -> Word32 #-}
{-# SPECIALIZE INLINE sizedComplement :: Integer -> Integer -> Integer #-}

{-# SPECIALIZE matchVectors :: String -> IM.IntMap Word32 #-}
{-# SPECIALIZE matchVectors :: String -> IM.IntMap Integer #-}

fuzzyMatch :: String -> [String] -> [String]
fuzzyMatch :: String -> [String] -> [String]
fuzzyMatch String
key [String]
vals = String -> [(String, String)] -> [String]
forall a. String -> [(String, a)] -> [a]
fuzzyLookup String
key [(String
v,String
v) | String
v <- [String]
vals]

-- | Search for possible matches to the users input in the given list,
-- returning a small number of ranked results
fuzzyLookup :: String -> [(String,a)] -> [a]
fuzzyLookup :: forall a. String -> [(String, a)] -> [a]
fuzzyLookup String
user_entered [(String, a)]
possibilites
  = ((a, (Int, Int, String)) -> a) -> [(a, (Int, Int, String))] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (a, (Int, Int, String)) -> a
forall a b. (a, b) -> a
fst ([(a, (Int, Int, String))] -> [a])
-> [(a, (Int, Int, String))] -> [a]
forall a b. (a -> b) -> a -> b
$ Int -> [(a, (Int, Int, String))] -> [(a, (Int, Int, String))]
forall a. Int -> [a] -> [a]
take Int
mAX_RESULTS ([(a, (Int, Int, String))] -> [(a, (Int, Int, String))])
-> [(a, (Int, Int, String))] -> [(a, (Int, Int, String))]
forall a b. (a -> b) -> a -> b
$ ((a, (Int, Int, String)) -> (a, (Int, Int, String)) -> Ordering)
-> [(a, (Int, Int, String))] -> [(a, (Int, Int, String))]
forall a. (a -> a -> Ordering) -> [a] -> [a]
List.sortBy (((a, (Int, Int, String)) -> (Int, Int, String))
-> (a, (Int, Int, String)) -> (a, (Int, Int, String)) -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (a, (Int, Int, String)) -> (Int, Int, String)
forall a b. (a, b) -> b
snd)
    [ (a
poss_val, (Int, Int, String)
sort_key)
    | (String
poss_str, a
poss_val) <- [(String, a)]
possibilites
    , let distance :: Int
distance = String -> String -> Int
restrictedDamerauLevenshteinDistance String
poss_str String
user_entered
    , Int
distance Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
fuzzy_threshold
    , let sort_key :: (Int, Int, String)
sort_key = (Int
distance, String -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length String
poss_str, String
poss_str)
    ]
  where
    -- Work out an appropriate match threshold:
    -- We report a candidate if its edit distance is <= the threshold,
    -- The threshold is set to about a quarter of the # of characters the user entered
    --   Length    Threshold
    --     1         0          -- Don't suggest *any* candidates
    --     2         1          -- for single-char identifiers
    --     3         1
    --     4         1
    --     5         1
    --     6         2
    --
    -- Candidates with the same distance are sorted by their length. We also
    -- use the actual string as the third sorting criteria the sort key to get
    -- deterministic output, even if the input may have depended on the uniques
    -- in question
    fuzzy_threshold :: Int
fuzzy_threshold = Rational -> Int
forall b. Integral b => Rational -> b
forall a b. (RealFrac a, Integral b) => a -> b
truncate (Rational -> Int) -> Rational -> Int
forall a b. (a -> b) -> a -> b
$ Int -> Rational
forall a b. (Integral a, Num b) => a -> b
fromIntegral (String -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length String
user_entered Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
2) Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/ (Rational
4 :: Rational)
    mAX_RESULTS :: Int
mAX_RESULTS = Int
3

{-
************************************************************************
*                                                                      *
\subsection[Utils-pairs]{Pairs}
*                                                                      *
************************************************************************
-}

unzipWith :: (a -> b -> c) -> [(a, b)] -> [c]
unzipWith :: forall a b c. (a -> b -> c) -> [(a, b)] -> [c]
unzipWith a -> b -> c
f [(a, b)]
pairs = ((a, b) -> c) -> [(a, b)] -> [c]
forall a b. (a -> b) -> [a] -> [b]
map ( \ (a
a, b
b) -> a -> b -> c
f a
a b
b ) [(a, b)]
pairs

seqList :: [a] -> b -> b
seqList :: forall a b. [a] -> b -> b
seqList [] b
b = b
b
seqList (a
x:[a]
xs) b
b = a
x a -> b -> b
forall a b. a -> b -> b
`seq` [a] -> b -> b
forall a b. [a] -> b -> b
seqList [a]
xs b
b

strictMap :: (a -> b) -> [a] -> [b]
strictMap :: forall a b. (a -> b) -> [a] -> [b]
strictMap a -> b
_ []     = []
strictMap a -> b
f (a
x:[a]
xs) =
  let
    !x' :: b
x' = a -> b
f a
x
    !xs' :: [b]
xs' = (a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
strictMap a -> b
f [a]
xs
  in
    b
x' b -> [b] -> [b]
forall a. a -> [a] -> [a]
: [b]
xs'

strictZipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
strictZipWith :: forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
strictZipWith a -> b -> c
_ []     [b]
_      = []
strictZipWith a -> b -> c
_ [a]
_      []     = []
strictZipWith a -> b -> c
f (a
x:[a]
xs) (b
y:[b]
ys) =
  let
    !x' :: c
x' = a -> b -> c
f a
x b
y
    !xs' :: [c]
xs' = (a -> b -> c) -> [a] -> [b] -> [c]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
strictZipWith a -> b -> c
f [a]
xs [b]
ys
  in
    c
x' c -> [c] -> [c]
forall a. a -> [a] -> [a]
: [c]
xs'

strictZipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
strictZipWith3 :: forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
strictZipWith3 a -> b -> c -> d
_ []     [b]
_      [c]
_      = []
strictZipWith3 a -> b -> c -> d
_ [a]
_      []     [c]
_      = []
strictZipWith3 a -> b -> c -> d
_ [a]
_      [b]
_      []     = []
strictZipWith3 a -> b -> c -> d
f (a
x:[a]
xs) (b
y:[b]
ys) (c
z:[c]
zs) =
  let
    !x' :: d
x' = a -> b -> c -> d
f a
x b
y c
z
    !xs' :: [d]
xs' = (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
strictZipWith3 a -> b -> c -> d
f [a]
xs [b]
ys [c]
zs
  in
    d
x' d -> [d] -> [d]
forall a. a -> [a] -> [a]
: [d]
xs'


-- Module names:

looksLikeModuleName :: String -> Bool
looksLikeModuleName :: String -> Bool
looksLikeModuleName [] = Bool
False
looksLikeModuleName (Char
c:String
cs) = Char -> Bool
isUpper Char
c Bool -> Bool -> Bool
&& String -> Bool
go String
cs
  where go :: String -> Bool
go [] = Bool
True
        go (Char
'.':String
cs) = String -> Bool
looksLikeModuleName String
cs
        go (Char
c:String
cs)   = (Char -> Bool
isAlphaNum Char
c Bool -> Bool -> Bool
|| Char
c Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'_' Bool -> Bool -> Bool
|| Char
c Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'\'') Bool -> Bool -> Bool
&& String -> Bool
go String
cs

-- Similar to 'parse' for Distribution.Package.PackageName,
-- but we don't want to depend on Cabal.
looksLikePackageName :: String -> Bool
looksLikePackageName :: String -> Bool
looksLikePackageName = (String -> Bool) -> [String] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all ((Char -> Bool) -> String -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Char -> Bool
isAlphaNum (String -> Bool) -> (String -> Bool) -> String -> Bool
forall (f :: * -> *). Applicative f => f Bool -> f Bool -> f Bool
<&&> Bool -> Bool
not (Bool -> Bool) -> (String -> Bool) -> String -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Char -> Bool) -> String -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Char -> Bool
isDigit)) ([String] -> Bool) -> (String -> [String]) -> String -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> String -> [String]
split Char
'-'

-----------------------------------------------------------------------------
-- Integers

-- | Determine the $\log_2$ of exact powers of 2
exactLog2 :: Integer -> Maybe Integer
exactLog2 :: Integer -> Maybe Integer
exactLog2 Integer
x
   | Integer
x Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
0                               = Maybe Integer
forall a. Maybe a
Nothing
   | Integer
x Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Int32 -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int32
forall a. Bounded a => a
maxBound :: Int32) = Maybe Integer
forall a. Maybe a
Nothing
   | Int32
x' Int32 -> Int32 -> Int32
forall bv. Bits bv => bv -> bv -> bv
.&. (-Int32
x') Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
/= Int32
x'                   = Maybe Integer
forall a. Maybe a
Nothing
   | Bool
otherwise                            = Integer -> Maybe Integer
forall a. a -> Maybe a
Just (Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
c)
      where
         x' :: Int32
x' = Integer -> Int32
forall a b. (Integral a, Num b) => a -> b
fromIntegral Integer
x :: Int32
         c :: Int
c = Int32 -> Int
forall b. FiniteBits b => b -> Int
countTrailingZeros Int32
x'

{-
-- -----------------------------------------------------------------------------
-- Floats
-}

readRational__ :: ReadS Rational -- NB: doesn't handle leading "-"
readRational__ :: ReadS Rational
readRational__ String
r = do
      ((Integer
i, Integer
e), String
t) <- ReadS (Integer, Integer)
readSignificandExponentPair__ String
r
      (Rational, String) -> [(Rational, String)]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return ((Integer
iInteger -> Integer -> Rational
forall a. Integral a => a -> a -> Ratio a
%Integer
1)Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
*Rational
10Rational -> Integer -> Rational
forall a b. (Fractional a, Integral b) => a -> b -> a
^^Integer
e, String
t)

readRational :: String -> Rational -- NB: *does* handle a leading "-"
readRational :: String -> Rational
readRational String
top_s
  = case String
top_s of
      Char
'-' : String
xs -> Rational -> Rational
forall a. Num a => a -> a
negate (String -> Rational
read_me String
xs)
      String
xs       -> String -> Rational
read_me String
xs
  where
    read_me :: String -> Rational
read_me String
s
      = case (do { (Rational
x,String
"") <- ReadS Rational
readRational__ String
s ; Rational -> [Rational]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return Rational
x }) of
          [Rational
x] -> Rational
x
          []  -> String -> Rational
forall a. HasCallStack => String -> a
error (String
"readRational: no parse:"        String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
top_s)
          [Rational]
_   -> String -> Rational
forall a. HasCallStack => String -> a
error (String
"readRational: ambiguous parse:" String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
top_s)


readSignificandExponentPair__ :: ReadS (Integer, Integer) -- NB: doesn't handle leading "-"
readSignificandExponentPair__ :: ReadS (Integer, Integer)
readSignificandExponentPair__ String
r = do
     (Integer
n,Int
d,String
s) <- String -> [(Integer, Int, String)]
readFix String
r
     (Int
k,String
t)   <- String -> [(Int, String)]
forall {m :: * -> *}. MonadFail m => String -> m (Int, String)
readExp String
s
     let pair :: (Integer, Integer)
pair = (Integer
n, Int -> Integer
forall a. Integral a => a -> Integer
toInteger (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
d))
     ((Integer, Integer), String) -> [((Integer, Integer), String)]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return ((Integer, Integer)
pair, String
t)
 where
     readFix :: String -> [(Integer, Int, String)]
readFix String
r = do
        (String
ds,String
s)  <- String -> [(String, String)]
lexDecDigits String
r
        (String
ds',String
t) <- String -> [(String, String)]
forall {m :: * -> *}. Monad m => String -> m (String, String)
lexDotDigits String
s
        (Integer, Int, String) -> [(Integer, Int, String)]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return (String -> Integer
forall a. Read a => String -> a
read (String
dsString -> String -> String
forall a. [a] -> [a] -> [a]
++String
ds'), String -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length String
ds', String
t)

     readExp :: String -> m (Int, String)
readExp (Char
e:String
s) | Char
e Char -> String -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` String
"eE" = String -> m (Int, String)
forall {m :: * -> *}. MonadFail m => String -> m (Int, String)
readExp' String
s
     readExp String
s                     = (Int, String) -> m (Int, String)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
0,String
s)

     readExp' :: String -> m (Int, String)
readExp' (Char
'+':String
s) = String -> m (Int, String)
forall {m :: * -> *}. MonadFail m => String -> m (Int, String)
readDec String
s
     readExp' (Char
'-':String
s) = do (Int
k,String
t) <- String -> m (Int, String)
forall {m :: * -> *}. MonadFail m => String -> m (Int, String)
readDec String
s
                           (Int, String) -> m (Int, String)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (-Int
k,String
t)
     readExp' String
s       = String -> m (Int, String)
forall {m :: * -> *}. MonadFail m => String -> m (Int, String)
readDec String
s

     readDec :: String -> m (Int, String)
readDec String
s = do
        (String
ds,String
r) <- (Char -> Bool) -> String -> m (String, String)
forall {m :: * -> *}.
MonadFail m =>
(Char -> Bool) -> String -> m (String, String)
nonnull Char -> Bool
isDigit String
s
        (Int, String) -> m (Int, String)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ((Int -> Int -> Int) -> [Int] -> Int
forall a. (a -> a -> a) -> [a] -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldl1 (\Int
n Int
d -> Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
10 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
d) [ Char -> Int
ord Char
d Int -> Int -> Int
forall a. Num a => a -> a -> a
- Char -> Int
ord Char
'0' | Char
d <- String
ds ],
                String
r)

     lexDecDigits :: String -> [(String, String)]
lexDecDigits = (Char -> Bool) -> String -> [(String, String)]
forall {m :: * -> *}.
MonadFail m =>
(Char -> Bool) -> String -> m (String, String)
nonnull Char -> Bool
isDigit

     lexDotDigits :: String -> m (String, String)
lexDotDigits (Char
'.':String
s) = (String, String) -> m (String, String)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ((Char -> Bool) -> String -> (String, String)
span' Char -> Bool
isDigit String
s)
     lexDotDigits String
s       = (String, String) -> m (String, String)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (String
"",String
s)

     nonnull :: (Char -> Bool) -> String -> m (String, String)
nonnull Char -> Bool
p String
s = do (cs :: String
cs@(Char
_:String
_),String
t) <- (String, String) -> m (String, String)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ((Char -> Bool) -> String -> (String, String)
span' Char -> Bool
p String
s)
                      (String, String) -> m (String, String)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (String
cs,String
t)

     span' :: (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
_ xs :: String
xs@[]         =  (String
xs, String
xs)
     span' Char -> Bool
p xs :: String
xs@(Char
x:String
xs')
               | Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'_'  = (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
p String
xs'   -- skip "_" (#14473)
               | Char -> Bool
p Char
x       =  let (String
ys,String
zs) = (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
p String
xs' in (Char
xChar -> String -> String
forall a. a -> [a] -> [a]
:String
ys,String
zs)
               | Bool
otherwise =  ([],String
xs)

-- | Parse a string into a significand and exponent.
-- A trivial example might be:
--   ghci> readSignificandExponentPair "1E2"
--   (1,2)
-- In a more complex case we might return a exponent different than that
-- which the user wrote. This is needed in order to use a Integer significand.
--   ghci> readSignificandExponentPair "-1.11E5"
--   (-111,3)
readSignificandExponentPair :: String -> (Integer, Integer) -- NB: *does* handle a leading "-"
readSignificandExponentPair :: String -> (Integer, Integer)
readSignificandExponentPair String
top_s
  = case String
top_s of
      Char
'-' : String
xs -> let (Integer
i, Integer
e) = String -> (Integer, Integer)
read_me String
xs in (-Integer
i, Integer
e)
      String
xs       -> String -> (Integer, Integer)
read_me String
xs
  where
    read_me :: String -> (Integer, Integer)
read_me String
s
      = case (do { ((Integer, Integer)
x,String
"") <- ReadS (Integer, Integer)
readSignificandExponentPair__ String
s ; (Integer, Integer) -> [(Integer, Integer)]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return (Integer, Integer)
x }) of
          [(Integer, Integer)
x] -> (Integer, Integer)
x
          []  -> String -> (Integer, Integer)
forall a. HasCallStack => String -> a
error (String
"readSignificandExponentPair: no parse:"        String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
top_s)
          [(Integer, Integer)]
_   -> String -> (Integer, Integer)
forall a. HasCallStack => String -> a
error (String
"readSignificandExponentPair: ambiguous parse:" String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
top_s)


readHexRational :: String -> Rational
readHexRational :: String -> Rational
readHexRational String
str =
  case String
str of
    Char
'-' : String
xs -> Rational -> Rational
forall a. Num a => a -> a
negate (String -> Rational
readMe String
xs)
    String
xs       -> String -> Rational
readMe String
xs
  where
  readMe :: String -> Rational
readMe String
as =
    case String -> Maybe Rational
readHexRational__ String
as of
      Just Rational
n -> Rational
n
      Maybe Rational
_      -> String -> Rational
forall a. HasCallStack => String -> a
error (String
"readHexRational: no parse:" String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
str)


readHexRational__ :: String -> Maybe Rational
readHexRational__ :: String -> Maybe Rational
readHexRational__ (Char
'0' : Char
x : String
rest)
  | Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'X' Bool -> Bool -> Bool
|| Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'x' =
  do let (String
front,String
rest2) = (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
isHexDigit String
rest
     Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Bool -> Bool
not (String -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null String
front))
     let frontNum :: Integer
frontNum = Integer -> Integer -> String -> Integer
forall {t :: * -> *} {b}.
(Foldable t, Num b) =>
b -> b -> t Char -> b
steps Integer
16 Integer
0 String
front
     case String
rest2 of
       Char
'.' : String
rest3 ->
          do let (String
back,String
rest4) = (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
isHexDigit String
rest3
             Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Bool -> Bool
not (String -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null String
back))
             let backNum :: Integer
backNum = Integer -> Integer -> String -> Integer
forall {t :: * -> *} {b}.
(Foldable t, Num b) =>
b -> b -> t Char -> b
steps Integer
16 Integer
frontNum String
back
                 exp1 :: Int
exp1    = -Int
4 Int -> Int -> Int
forall a. Num a => a -> a -> a
* String -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length String
back
             case String
rest4 of
               Char
p : String
ps | Char -> Bool
isExp Char
p -> (Int -> Rational) -> Maybe Int -> Maybe Rational
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Integer -> Int -> Rational
mk Integer
backNum (Int -> Rational) -> (Int -> Int) -> Int -> Rational
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
exp1)) (String -> Maybe Int
forall {a}. Num a => String -> Maybe a
getExp String
ps)
               String
_ -> Rational -> Maybe Rational
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (Integer -> Int -> Rational
mk Integer
backNum Int
exp1)
       Char
p : String
ps | Char -> Bool
isExp Char
p -> (Int -> Rational) -> Maybe Int -> Maybe Rational
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Integer -> Int -> Rational
mk Integer
frontNum) (String -> Maybe Int
forall {a}. Num a => String -> Maybe a
getExp String
ps)
       String
_ -> Maybe Rational
forall a. Maybe a
Nothing

  where
  isExp :: Char -> Bool
isExp Char
p = Char
p Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'p' Bool -> Bool -> Bool
|| Char
p Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'P'

  getExp :: String -> Maybe a
getExp (Char
'+' : String
ds) = String -> Maybe a
forall {a}. Num a => String -> Maybe a
dec String
ds
  getExp (Char
'-' : String
ds) = (a -> a) -> Maybe a -> Maybe a
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> a
forall a. Num a => a -> a
negate (String -> Maybe a
forall {a}. Num a => String -> Maybe a
dec String
ds)
  getExp String
ds         = String -> Maybe a
forall {a}. Num a => String -> Maybe a
dec String
ds

  mk :: Integer -> Int -> Rational
  mk :: Integer -> Int -> Rational
mk Integer
n Int
e = Integer -> Rational
forall a. Num a => Integer -> a
fromInteger Integer
n Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
* Rational
2Rational -> Int -> Rational
forall a b. (Fractional a, Integral b) => a -> b -> a
^^Int
e

  dec :: String -> Maybe a
dec String
cs = case (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
isDigit String
cs of
             (String
ds,String
"") | Bool -> Bool
not (String -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null String
ds) -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> a -> String -> a
forall {t :: * -> *} {b}.
(Foldable t, Num b) =>
b -> b -> t Char -> b
steps a
10 a
0 String
ds)
             (String, String)
_ -> Maybe a
forall a. Maybe a
Nothing

  steps :: b -> b -> t Char -> b
steps b
base b
n t Char
ds = (b -> Char -> b) -> b -> t Char -> b
forall b a. (b -> a -> b) -> b -> t a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (b -> b -> Char -> b
forall {a}. Num a => a -> a -> Char -> a
step b
base) b
n t Char
ds
  step :: a -> a -> Char -> a
step  a
base a
n Char
d  = a
base a -> a -> a
forall a. Num a => a -> a -> a
* a
n a -> a -> a
forall a. Num a => a -> a -> a
+ Int -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Char -> Int
digitToInt Char
d)

  span' :: (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
_ xs :: String
xs@[]         =  (String
xs, String
xs)
  span' Char -> Bool
p xs :: String
xs@(Char
x:String
xs')
            | Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'_'  = (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
p String
xs'   -- skip "_"  (#14473)
            | Char -> Bool
p Char
x       =  let (String
ys,String
zs) = (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
p String
xs' in (Char
xChar -> String -> String
forall a. a -> [a] -> [a]
:String
ys,String
zs)
            | Bool
otherwise =  ([],String
xs)

readHexRational__ String
_ = Maybe Rational
forall a. Maybe a
Nothing

-- | Parse a string into a significand and exponent according to
-- the "Hexadecimal Floats in Haskell" proposal.
-- A trivial example might be:
--   ghci> readHexSignificandExponentPair "0x1p+1"
--   (1,1)
-- Behaves similar to readSignificandExponentPair but the base is 16
-- and numbers are given in hexadecimal:
--   ghci> readHexSignificandExponentPair "0xAp-4"
--   (10,-4)
--   ghci> readHexSignificandExponentPair "0x1.2p3"
--   (18,-1)
readHexSignificandExponentPair :: String -> (Integer, Integer)
readHexSignificandExponentPair :: String -> (Integer, Integer)
readHexSignificandExponentPair String
str =
  case String
str of
    Char
'-' : String
xs -> let (Integer
i, Integer
e) = String -> (Integer, Integer)
readMe String
xs in (-Integer
i, Integer
e)
    String
xs       -> String -> (Integer, Integer)
readMe String
xs
  where
  readMe :: String -> (Integer, Integer)
readMe String
as =
    case String -> Maybe (Integer, Integer)
readHexSignificandExponentPair__ String
as of
      Just (Integer, Integer)
n -> (Integer, Integer)
n
      Maybe (Integer, Integer)
_      -> String -> (Integer, Integer)
forall a. HasCallStack => String -> a
error (String
"readHexSignificandExponentPair: no parse:" String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
str)


readHexSignificandExponentPair__ :: String -> Maybe (Integer, Integer)
readHexSignificandExponentPair__ :: String -> Maybe (Integer, Integer)
readHexSignificandExponentPair__ (Char
'0' : Char
x : String
rest)
  | Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'X' Bool -> Bool -> Bool
|| Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'x' =
  do let (String
front,String
rest2) = (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
isHexDigit String
rest
     Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Bool -> Bool
not (String -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null String
front))
     let frontNum :: Integer
frontNum = Integer -> Integer -> String -> Integer
forall {t :: * -> *} {b}.
(Foldable t, Num b) =>
b -> b -> t Char -> b
steps Integer
16 Integer
0 String
front
     case String
rest2 of
       Char
'.' : String
rest3 ->
          do let (String
back,String
rest4) = (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
isHexDigit String
rest3
             Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Bool -> Bool
not (String -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null String
back))
             let backNum :: Integer
backNum = Integer -> Integer -> String -> Integer
forall {t :: * -> *} {b}.
(Foldable t, Num b) =>
b -> b -> t Char -> b
steps Integer
16 Integer
frontNum String
back
                 exp1 :: Int
exp1    = -Int
4 Int -> Int -> Int
forall a. Num a => a -> a -> a
* String -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length String
back
             case String
rest4 of
               Char
p : String
ps | Char -> Bool
isExp Char
p -> (Int -> (Integer, Integer))
-> Maybe Int -> Maybe (Integer, Integer)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Integer -> Int -> (Integer, Integer)
mk Integer
backNum (Int -> (Integer, Integer))
-> (Int -> Int) -> Int -> (Integer, Integer)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
exp1)) (String -> Maybe Int
forall {a}. Num a => String -> Maybe a
getExp String
ps)
               String
_ -> (Integer, Integer) -> Maybe (Integer, Integer)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (Integer -> Int -> (Integer, Integer)
mk Integer
backNum Int
exp1)
       Char
p : String
ps | Char -> Bool
isExp Char
p -> (Int -> (Integer, Integer))
-> Maybe Int -> Maybe (Integer, Integer)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Integer -> Int -> (Integer, Integer)
mk Integer
frontNum) (String -> Maybe Int
forall {a}. Num a => String -> Maybe a
getExp String
ps)
       String
_ -> Maybe (Integer, Integer)
forall a. Maybe a
Nothing

  where
  isExp :: Char -> Bool
isExp Char
p = Char
p Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'p' Bool -> Bool -> Bool
|| Char
p Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'P'

  getExp :: String -> Maybe a
getExp (Char
'+' : String
ds) = String -> Maybe a
forall {a}. Num a => String -> Maybe a
dec String
ds
  getExp (Char
'-' : String
ds) = (a -> a) -> Maybe a -> Maybe a
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> a
forall a. Num a => a -> a
negate (String -> Maybe a
forall {a}. Num a => String -> Maybe a
dec String
ds)
  getExp String
ds         = String -> Maybe a
forall {a}. Num a => String -> Maybe a
dec String
ds

  mk :: Integer -> Int -> (Integer, Integer)
  mk :: Integer -> Int -> (Integer, Integer)
mk Integer
n Int
e = (Integer
n, Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
e)

  dec :: String -> Maybe a
dec String
cs = case (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
isDigit String
cs of
             (String
ds,String
"") | Bool -> Bool
not (String -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null String
ds) -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> a -> String -> a
forall {t :: * -> *} {b}.
(Foldable t, Num b) =>
b -> b -> t Char -> b
steps a
10 a
0 String
ds)
             (String, String)
_ -> Maybe a
forall a. Maybe a
Nothing

  steps :: b -> b -> t Char -> b
steps b
base b
n t Char
ds = (b -> Char -> b) -> b -> t Char -> b
forall b a. (b -> a -> b) -> b -> t a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (b -> b -> Char -> b
forall {a}. Num a => a -> a -> Char -> a
step b
base) b
n t Char
ds
  step :: a -> a -> Char -> a
step  a
base a
n Char
d  = a
base a -> a -> a
forall a. Num a => a -> a -> a
* a
n a -> a -> a
forall a. Num a => a -> a -> a
+ Int -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Char -> Int
digitToInt Char
d)

  span' :: (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
_ xs :: String
xs@[]         =  (String
xs, String
xs)
  span' Char -> Bool
p xs :: String
xs@(Char
x:String
xs')
            | Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'_'  = (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
p String
xs'   -- skip "_"  (#14473)
            | Char -> Bool
p Char
x       =  let (String
ys,String
zs) = (Char -> Bool) -> String -> (String, String)
span' Char -> Bool
p String
xs' in (Char
xChar -> String -> String
forall a. a -> [a] -> [a]
:String
ys,String
zs)
            | Bool
otherwise =  ([],String
xs)

readHexSignificandExponentPair__ String
_ = Maybe (Integer, Integer)
forall a. Maybe a
Nothing


-----------------------------------------------------------------------------
-- Verify that the 'dirname' portion of a FilePath exists.
--
doesDirNameExist :: FilePath -> IO Bool
doesDirNameExist :: String -> IO Bool
doesDirNameExist String
fpath = String -> IO Bool
doesDirectoryExist (String -> String
takeDirectory String
fpath)

-----------------------------------------------------------------------------
-- Backwards compatibility definition of getModificationTime

getModificationUTCTime :: FilePath -> IO UTCTime
getModificationUTCTime :: String -> IO UTCTime
getModificationUTCTime = String -> IO UTCTime
getModificationTime

-- --------------------------------------------------------------
-- check existence & modification time at the same time

modificationTimeIfExists :: FilePath -> IO (Maybe UTCTime)
modificationTimeIfExists :: String -> IO (Maybe UTCTime)
modificationTimeIfExists String
f =
  (do UTCTime
t <- String -> IO UTCTime
getModificationUTCTime String
f; Maybe UTCTime -> IO (Maybe UTCTime)
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return (UTCTime -> Maybe UTCTime
forall a. a -> Maybe a
Just UTCTime
t))
        IO (Maybe UTCTime)
-> (IOException -> IO (Maybe UTCTime)) -> IO (Maybe UTCTime)
forall a. IO a -> (IOException -> IO a) -> IO a
`catchIO` \IOException
e -> if IOException -> Bool
isDoesNotExistError IOException
e
                        then Maybe UTCTime -> IO (Maybe UTCTime)
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe UTCTime
forall a. Maybe a
Nothing
                        else IOException -> IO (Maybe UTCTime)
forall a. IOException -> IO a
ioError IOException
e

-- --------------------------------------------------------------
-- check existence & hash at the same time

fileHashIfExists :: FilePath -> IO (Maybe Fingerprint)
fileHashIfExists :: String -> IO (Maybe Fingerprint)
fileHashIfExists String
f =
  (do Fingerprint
t <- String -> IO Fingerprint
getFileHash String
f; Maybe Fingerprint -> IO (Maybe Fingerprint)
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return (Fingerprint -> Maybe Fingerprint
forall a. a -> Maybe a
Just Fingerprint
t))
        IO (Maybe Fingerprint)
-> (IOException -> IO (Maybe Fingerprint))
-> IO (Maybe Fingerprint)
forall a. IO a -> (IOException -> IO a) -> IO a
`catchIO` \IOException
e -> if IOException -> Bool
isDoesNotExistError IOException
e
                        then Maybe Fingerprint -> IO (Maybe Fingerprint)
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe Fingerprint
forall a. Maybe a
Nothing
                        else IOException -> IO (Maybe Fingerprint)
forall a. IOException -> IO a
ioError IOException
e

-- --------------------------------------------------------------
-- atomic file writing by writing to a temporary file first (see #14533)
--
-- This should be used in all cases where GHC writes files to disk
-- and uses their modification time to skip work later,
-- as otherwise a partially written file (e.g. due to crash or Ctrl+C)
-- also results in a skip.

withAtomicRename :: (MonadIO m) => FilePath -> (FilePath -> m a) -> m a
withAtomicRename :: forall (m :: * -> *) a.
MonadIO m =>
String -> (String -> m a) -> m a
withAtomicRename String
targetFile String -> m a
f = do
  -- The temp file must be on the same file system (mount) as the target file
  -- to result in an atomic move on most platforms.
  -- The standard way to ensure that is to place it into the same directory.
  -- This can still be fooled when somebody mounts a different file system
  -- at just the right time, but that is not a case we aim to cover here.
  let temp :: String
temp = String
targetFile String -> String -> String
<.> String
"tmp"
  a
res <- String -> m a
f String
temp
  IO () -> m ()
forall a. IO a -> m a
forall (m :: * -> *) a. MonadIO m => IO a -> m a
liftIO (IO () -> m ()) -> IO () -> m ()
forall a b. (a -> b) -> a -> b
$ String -> String -> IO ()
renameFile String
temp String
targetFile
  a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return a
res

-- --------------------------------------------------------------
-- split a string at the last character where 'pred' is True,
-- returning a pair of strings. The first component holds the string
-- up (but not including) the last character for which 'pred' returned
-- True, the second whatever comes after (but also not including the
-- last character).
--
-- If 'pred' returns False for all characters in the string, the original
-- string is returned in the first component (and the second one is just
-- empty).
splitLongestPrefix :: String -> (Char -> Bool) -> (String,String)
splitLongestPrefix :: String -> (Char -> Bool) -> (String, String)
splitLongestPrefix String
str Char -> Bool
pred
  | String -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null String
r_pre = (String
str,           [])
  | Bool
otherwise  = (String -> String
forall a. [a] -> [a]
reverse (String -> String
forall a. HasCallStack => [a] -> [a]
tail String
r_pre), String -> String
forall a. [a] -> [a]
reverse String
r_suf)
                           -- 'tail' drops the char satisfying 'pred'
  where (String
r_suf, String
r_pre) = (Char -> Bool) -> String -> (String, String)
forall a. (a -> Bool) -> [a] -> ([a], [a])
break Char -> Bool
pred (String -> String
forall a. [a] -> [a]
reverse String
str)

escapeSpaces :: String -> String
escapeSpaces :: String -> String
escapeSpaces = (Char -> String -> String) -> String -> String -> String
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\Char
c String
s -> if Char -> Bool
isSpace Char
c then Char
'\\'Char -> String -> String
forall a. a -> [a] -> [a]
:Char
cChar -> String -> String
forall a. a -> [a] -> [a]
:String
s else Char
cChar -> String -> String
forall a. a -> [a] -> [a]
:String
s) String
""

type Suffix = String

--------------------------------------------------------------
-- * Search path
--------------------------------------------------------------

data Direction = Forwards | Backwards

reslash :: Direction -> FilePath -> FilePath
reslash :: Direction -> String -> String
reslash Direction
d = String -> String
f
    where f :: String -> String
f (Char
'/'  : String
xs) = Char
slash Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
f String
xs
          f (Char
'\\' : String
xs) = Char
slash Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
f String
xs
          f (Char
x    : String
xs) = Char
x     Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
f String
xs
          f String
""          = String
""
          slash :: Char
slash = case Direction
d of
                  Direction
Forwards -> Char
'/'
                  Direction
Backwards -> Char
'\\'

makeRelativeTo :: FilePath -> FilePath -> FilePath
String
this makeRelativeTo :: String -> String -> String
`makeRelativeTo` String
that = String
directory String -> String -> String
</> String
thisFilename
    where (String
thisDirectory, String
thisFilename) = String -> (String, String)
splitFileName String
this
          thatDirectory :: String
thatDirectory = String -> String
dropFileName String
that
          directory :: String
directory = [String] -> String
joinPath ([String] -> String) -> [String] -> String
forall a b. (a -> b) -> a -> b
$ [String] -> [String] -> [String]
f (String -> [String]
splitPath String
thisDirectory)
                                   (String -> [String]
splitPath String
thatDirectory)

          f :: [String] -> [String] -> [String]
f (String
x : [String]
xs) (String
y : [String]
ys)
           | String
x String -> String -> Bool
forall a. Eq a => a -> a -> Bool
== String
y = [String] -> [String] -> [String]
f [String]
xs [String]
ys
          f [String]
xs [String]
ys = Int -> String -> [String]
forall a. Int -> a -> [a]
replicate ([String] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [String]
ys) String
".." [String] -> [String] -> [String]
forall a. [a] -> [a] -> [a]
++ [String]
xs

{-
************************************************************************
*                                                                      *
\subsection[Utils-Data]{Utils for defining Data instances}
*                                                                      *
************************************************************************

These functions helps us to define Data instances for abstract types.
-}

abstractConstr :: String -> Constr
abstractConstr :: String -> Constr
abstractConstr String
n = DataType -> String -> [String] -> Fixity -> Constr
mkConstr (String -> DataType
abstractDataType String
n) (String
"{abstract:"String -> String -> String
forall a. [a] -> [a] -> [a]
++String
nString -> String -> String
forall a. [a] -> [a] -> [a]
++String
"}") [] Fixity
Prefix

abstractDataType :: String -> DataType
abstractDataType :: String -> DataType
abstractDataType String
n = String -> [Constr] -> DataType
mkDataType String
n [String -> Constr
abstractConstr String
n]

{-
************************************************************************
*                                                                      *
\subsection[Utils-C]{Utils for printing C code}
*                                                                      *
************************************************************************
-}

charToC :: Word8 -> String
charToC :: Word8 -> String
charToC Word8
w =
  case Int -> Char
chr (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
w) of
        Char
'\"' -> String
"\\\""
        Char
'\'' -> String
"\\\'"
        Char
'\\' -> String
"\\\\"
        Char
c | Char
c Char -> Char -> Bool
forall a. Ord a => a -> a -> Bool
>= Char
' ' Bool -> Bool -> Bool
&& Char
c Char -> Char -> Bool
forall a. Ord a => a -> a -> Bool
<= Char
'~' -> [Char
c]
          | Bool
otherwise -> [Char
'\\',
                         Int -> Char
chr (Char -> Int
ord Char
'0' Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Char -> Int
ord Char
c Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
64),
                         Int -> Char
chr (Char -> Int
ord Char
'0' Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Char -> Int
ord Char
c Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
8 Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
8),
                         Int -> Char
chr (Char -> Int
ord Char
'0' Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Char -> Int
ord Char
c         Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
8)]

{-
************************************************************************
*                                                                      *
\subsection[Utils-Hashing]{Utils for hashing}
*                                                                      *
************************************************************************
-}

-- | A sample hash function for Strings.  We keep multiplying by the
-- golden ratio and adding.  The implementation is:
--
-- > hashString = foldl' f golden
-- >   where f m c = fromIntegral (ord c) * magic + hashInt32 m
-- >         magic = 0xdeadbeef
--
-- Where hashInt32 works just as hashInt shown above.
--
-- Knuth argues that repeated multiplication by the golden ratio
-- will minimize gaps in the hash space, and thus it's a good choice
-- for combining together multiple keys to form one.
--
-- Here we know that individual characters c are often small, and this
-- produces frequent collisions if we use ord c alone.  A
-- particular problem are the shorter low ASCII and ISO-8859-1
-- character strings.  We pre-multiply by a magic twiddle factor to
-- obtain a good distribution.  In fact, given the following test:
--
-- > testp :: Int32 -> Int
-- > testp k = (n - ) . length . group . sort . map hs . take n $ ls
-- >   where ls = [] : [c : l | l <- ls, c <- ['\0'..'\xff']]
-- >         hs = foldl' f golden
-- >         f m c = fromIntegral (ord c) * k + hashInt32 m
-- >         n = 100000
--
-- We discover that testp magic = 0.
hashString :: String -> Int32
hashString :: String -> Int32
hashString = (Int32 -> Char -> Int32) -> Int32 -> String -> Int32
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Int32 -> Char -> Int32
f Int32
golden
   where f :: Int32 -> Char -> Int32
f Int32
m Char
c = Int -> Int32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Char -> Int
ord Char
c) Int32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
* Int32
magic Int32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
+ Int32 -> Int32
hashInt32 Int32
m
         magic :: Int32
magic = Word32 -> Int32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word32
0xdeadbeef :: Word32)

golden :: Int32
golden :: Int32
golden = Int32
1013904242 -- = round ((sqrt 5 - 1) * 2^32) :: Int32
-- was -1640531527 = round ((sqrt 5 - 1) * 2^31) :: Int32
-- but that has bad mulHi properties (even adding 2^32 to get its inverse)
-- Whereas the above works well and contains no hash duplications for
-- [-32767..65536]

-- | A sample (and useful) hash function for Int32,
-- implemented by extracting the uppermost 32 bits of the 64-bit
-- result of multiplying by a 33-bit constant.  The constant is from
-- Knuth, derived from the golden ratio:
--
-- > golden = round ((sqrt 5 - 1) * 2^32)
--
-- We get good key uniqueness on small inputs
-- (a problem with previous versions):
--  (length $ group $ sort $ map hashInt32 [-32767..65536]) == 65536 + 32768
--
hashInt32 :: Int32 -> Int32
hashInt32 :: Int32 -> Int32
hashInt32 Int32
x = Int32 -> Int32 -> Int32
mulHi Int32
x Int32
golden Int32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
+ Int32
x

-- hi 32 bits of a x-bit * 32 bit -> 64-bit multiply
mulHi :: Int32 -> Int32 -> Int32
mulHi :: Int32 -> Int32 -> Int32
mulHi Int32
a Int32
b = Int64 -> Int32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int64
r Int64 -> Int -> Int64
forall a. Bits a => a -> Int -> a
`shiftR` Int
32)
   where r :: Int64
         r :: Int64
r = Int32 -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int32
a Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
* Int32 -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int32
b

-- | A call stack constraint, but only when 'isDebugOn'.
#if defined(DEBUG)
type HasDebugCallStack = HasCallStack
#else
type HasDebugCallStack = (() :: Constraint)
#endif

mapMaybe' :: Foldable f => (a -> Maybe b) -> f a -> [b]
mapMaybe' :: forall (f :: * -> *) a b.
Foldable f =>
(a -> Maybe b) -> f a -> [b]
mapMaybe' a -> Maybe b
f = (a -> [b] -> [b]) -> [b] -> f a -> [b]
forall a b. (a -> b -> b) -> b -> f a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> [b] -> [b]
g []
  where
    g :: a -> [b] -> [b]
g a
x [b]
rest
      | Just b
y <- a -> Maybe b
f a
x = b
y b -> [b] -> [b]
forall a. a -> [a] -> [a]
: [b]
rest
      | Bool
otherwise     = [b]
rest