2 % (c) The University of Glasgow 2006
3 % (c) The University of Glasgow 1992-2002
5 \section[Util]{Highly random utility functions}
9 ghciSupported, debugIsOn, ghciTablesNextToCode, picIsOn,
10 isWindowsHost, isWindowsTarget, isDarwinTarget,
12 -- general list processing
13 zipEqual, zipWithEqual, zipWith3Equal, zipWith4Equal,
14 zipLazy, stretchZipWith,
16 mapAndUnzip, mapAndUnzip3,
17 nOfThem, filterOut, partitionWith, splitEithers,
20 lengthExceeds, lengthIs, lengthAtLeast,
21 listLengthCmp, atLength, equalLength, compareLength,
23 isSingleton, only, singleton,
34 -- transitive closures
40 takeList, dropList, splitAtList, split,
44 thenCmp, cmpList, maybePrefixMatch,
58 getCmd, toCmdArgs, toArgs,
60 -- Floating point stuff
64 createDirectoryHierarchy,
66 modificationTimeIfExists,
73 Direction(..), reslash,
76 #include "HsVersions.h"
80 import Data.IORef ( IORef, newIORef )
81 import System.IO.Unsafe ( unsafePerformIO )
82 import Data.IORef ( readIORef, writeIORef )
83 import Data.List hiding (group)
85 import qualified Data.List as List ( elem )
87 import qualified Data.List as List ( notElem )
91 import Control.Monad ( unless )
92 import System.IO.Error as IO ( catch, isDoesNotExistError )
93 import System.Directory ( doesDirectoryExist, createDirectory,
95 import System.FilePath hiding ( searchPathSeparator )
96 import Data.Char ( isUpper, isAlphaNum, isSpace, ord, isDigit )
97 import Data.Ratio ( (%) )
98 import System.Time ( ClockTime )
103 %************************************************************************
105 \subsection{Is DEBUG on, are we on Windows, etc?}
107 %************************************************************************
110 ghciSupported :: Bool
114 ghciSupported = False
124 ghciTablesNextToCode :: Bool
125 #ifdef GHCI_TABLES_NEXT_TO_CODE
126 ghciTablesNextToCode = True
128 ghciTablesNextToCode = False
138 isWindowsHost :: Bool
139 #ifdef mingw32_HOST_OS
142 isWindowsHost = False
145 isWindowsTarget :: Bool
146 #ifdef mingw32_TARGET_OS
147 isWindowsTarget = True
149 isWindowsTarget = False
152 isDarwinTarget :: Bool
153 #ifdef darwin_TARGET_OS
154 isDarwinTarget = True
156 isDarwinTarget = False
160 %************************************************************************
162 \subsection{A for loop}
164 %************************************************************************
167 -- Compose a function with itself n times. (nth rather than twice)
168 nTimes :: Int -> (a -> a) -> (a -> a)
171 nTimes n f = f . nTimes (n-1) f
174 %************************************************************************
176 \subsection[Utils-lists]{General list processing}
178 %************************************************************************
181 filterOut :: (a->Bool) -> [a] -> [a]
182 -- Like filter, only reverses the sense of the test
184 filterOut p (x:xs) | p x = filterOut p xs
185 | otherwise = x : filterOut p xs
187 partitionWith :: (a -> Either b c) -> [a] -> ([b], [c])
188 partitionWith _ [] = ([],[])
189 partitionWith f (x:xs) = case f x of
191 Right c -> (bs, c:cs)
192 where (bs,cs) = partitionWith f xs
194 splitEithers :: [Either a b] -> ([a], [b])
195 splitEithers [] = ([],[])
196 splitEithers (e : es) = case e of
198 Right y -> (xs, y:ys)
199 where (xs,ys) = splitEithers es
202 A paranoid @zip@ (and some @zipWith@ friends) that checks the lists
203 are of equal length. Alastair Reid thinks this should only happen if
204 DEBUGging on; hey, why not?
207 zipEqual :: String -> [a] -> [b] -> [(a,b)]
208 zipWithEqual :: String -> (a->b->c) -> [a]->[b]->[c]
209 zipWith3Equal :: String -> (a->b->c->d) -> [a]->[b]->[c]->[d]
210 zipWith4Equal :: String -> (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
214 zipWithEqual _ = zipWith
215 zipWith3Equal _ = zipWith3
216 zipWith4Equal _ = zipWith4
218 zipEqual _ [] [] = []
219 zipEqual msg (a:as) (b:bs) = (a,b) : zipEqual msg as bs
220 zipEqual msg _ _ = panic ("zipEqual: unequal lists:"++msg)
222 zipWithEqual msg z (a:as) (b:bs)= z a b : zipWithEqual msg z as bs
223 zipWithEqual _ _ [] [] = []
224 zipWithEqual msg _ _ _ = panic ("zipWithEqual: unequal lists:"++msg)
226 zipWith3Equal msg z (a:as) (b:bs) (c:cs)
227 = z a b c : zipWith3Equal msg z as bs cs
228 zipWith3Equal _ _ [] [] [] = []
229 zipWith3Equal msg _ _ _ _ = panic ("zipWith3Equal: unequal lists:"++msg)
231 zipWith4Equal msg z (a:as) (b:bs) (c:cs) (d:ds)
232 = z a b c d : zipWith4Equal msg z as bs cs ds
233 zipWith4Equal _ _ [] [] [] [] = []
234 zipWith4Equal msg _ _ _ _ _ = panic ("zipWith4Equal: unequal lists:"++msg)
239 -- zipLazy is lazy in the second list (observe the ~)
241 zipLazy :: [a] -> [b] -> [(a,b)]
243 -- We want to write this, but with GHC 6.4 we get a warning, so it
245 -- zipLazy (x:xs) ~(y:ys) = (x,y) : zipLazy xs ys
246 -- so we write this instead:
247 zipLazy (x:xs) zs = let y : ys = zs
248 in (x,y) : zipLazy xs ys
253 stretchZipWith :: (a -> Bool) -> b -> (a->b->c) -> [a] -> [b] -> [c]
254 -- (stretchZipWith p z f xs ys) stretches ys by inserting z in
255 -- the places where p returns *True*
257 stretchZipWith _ _ _ [] _ = []
258 stretchZipWith p z f (x:xs) ys
259 | p x = f x z : stretchZipWith p z f xs ys
260 | otherwise = case ys of
262 (y:ys) -> f x y : stretchZipWith p z f xs ys
267 mapFst :: (a->c) -> [(a,b)] -> [(c,b)]
268 mapSnd :: (b->c) -> [(a,b)] -> [(a,c)]
270 mapFst f xys = [(f x, y) | (x,y) <- xys]
271 mapSnd f xys = [(x, f y) | (x,y) <- xys]
273 mapAndUnzip :: (a -> (b, c)) -> [a] -> ([b], [c])
275 mapAndUnzip _ [] = ([], [])
278 (rs1, rs2) = mapAndUnzip f xs
282 mapAndUnzip3 :: (a -> (b, c, d)) -> [a] -> ([b], [c], [d])
284 mapAndUnzip3 _ [] = ([], [], [])
285 mapAndUnzip3 f (x:xs)
286 = let (r1, r2, r3) = f x
287 (rs1, rs2, rs3) = mapAndUnzip3 f xs
289 (r1:rs1, r2:rs2, r3:rs3)
293 nOfThem :: Int -> a -> [a]
294 nOfThem n thing = replicate n thing
296 -- 'atLength atLen atEnd ls n' unravels list 'ls' to position 'n';
299 -- atLength atLenPred atEndPred ls n
300 -- | n < 0 = atLenPred n
301 -- | length ls < n = atEndPred (n - length ls)
302 -- | otherwise = atLenPred (drop n ls)
304 atLength :: ([a] -> b)
309 atLength atLenPred atEndPred ls n
310 | n < 0 = atEndPred n
311 | otherwise = go n ls
313 go n [] = atEndPred n
314 go 0 ls = atLenPred ls
315 go n (_:xs) = go (n-1) xs
318 lengthExceeds :: [a] -> Int -> Bool
319 -- (lengthExceeds xs n) = (length xs > n)
320 lengthExceeds = atLength notNull (const False)
322 lengthAtLeast :: [a] -> Int -> Bool
323 lengthAtLeast = atLength notNull (== 0)
325 lengthIs :: [a] -> Int -> Bool
326 lengthIs = atLength null (==0)
328 listLengthCmp :: [a] -> Int -> Ordering
329 listLengthCmp = atLength atLen atEnd
333 | x > 0 = LT -- not yet seen 'n' elts, so list length is < n.
339 equalLength :: [a] -> [b] -> Bool
340 equalLength [] [] = True
341 equalLength (_:xs) (_:ys) = equalLength xs ys
342 equalLength _ _ = False
344 compareLength :: [a] -> [b] -> Ordering
345 compareLength [] [] = EQ
346 compareLength (_:xs) (_:ys) = compareLength xs ys
347 compareLength [] _ = LT
348 compareLength _ [] = GT
350 ----------------------------
351 singleton :: a -> [a]
354 isSingleton :: [a] -> Bool
355 isSingleton [_] = True
356 isSingleton _ = False
358 notNull :: [a] -> Bool
368 only _ = panic "Util: only"
371 Debugging/specialising versions of \tr{elem} and \tr{notElem}
374 isIn, isn'tIn :: Eq a => String -> a -> [a] -> Bool
377 isIn _msg x ys = elem__ x ys
378 isn'tIn _msg x ys = notElem__ x ys
380 --these are here to be SPECIALIZEd (automagically)
381 elem__ :: Eq a => a -> [a] -> Bool
383 elem__ x (y:ys) = x == y || elem__ x ys
385 notElem__ :: Eq a => a -> [a] -> Bool
386 notElem__ _ [] = True
387 notElem__ x (y:ys) = x /= y && notElem__ x ys
391 = elem (_ILIT(0)) x ys
395 | i ># _ILIT(100) = trace ("Over-long elem in " ++ msg)
396 (x `List.elem` (y:ys))
397 | otherwise = x == y || elem (i +# _ILIT(1)) x ys
400 = notElem (_ILIT(0)) x ys
402 notElem _ _ [] = True
404 | i ># _ILIT(100) = trace ("Over-long notElem in " ++ msg)
405 (x `List.notElem` (y:ys))
406 | otherwise = x /= y && notElem (i +# _ILIT(1)) x ys
410 %************************************************************************
412 \subsubsection[Utils-Carsten-mergesort]{A mergesort from Carsten}
414 %************************************************************************
417 Date: Mon, 3 May 93 20:45:23 +0200
418 From: Carsten Kehler Holst <kehler@cs.chalmers.se>
419 To: partain@dcs.gla.ac.uk
420 Subject: natural merge sort beats quick sort [ and it is prettier ]
422 Here is a piece of Haskell code that I'm rather fond of. See it as an
423 attempt to get rid of the ridiculous quick-sort routine. group is
424 quite useful by itself I think it was John's idea originally though I
425 believe the lazy version is due to me [surprisingly complicated].
426 gamma [used to be called] is called gamma because I got inspired by
427 the Gamma calculus. It is not very close to the calculus but does
428 behave less sequentially than both foldr and foldl. One could imagine
429 a version of gamma that took a unit element as well thereby avoiding
430 the problem with empty lists.
432 I've tried this code against
434 1) insertion sort - as provided by haskell
435 2) the normal implementation of quick sort
436 3) a deforested version of quick sort due to Jan Sparud
437 4) a super-optimized-quick-sort of Lennart's
439 If the list is partially sorted both merge sort and in particular
440 natural merge sort wins. If the list is random [ average length of
441 rising subsequences = approx 2 ] mergesort still wins and natural
442 merge sort is marginally beaten by Lennart's soqs. The space
443 consumption of merge sort is a bit worse than Lennart's quick sort
444 approx a factor of 2. And a lot worse if Sparud's bug-fix [see his
445 fpca article ] isn't used because of group.
452 group :: (a -> a -> Bool) -> [a] -> [[a]]
453 -- Given a <= function, group finds maximal contiguous up-runs
454 -- or down-runs in the input list.
455 -- It's stable, in the sense that it never re-orders equal elements
457 -- Date: Mon, 12 Feb 1996 15:09:41 +0000
458 -- From: Andy Gill <andy@dcs.gla.ac.uk>
459 -- Here is a `better' definition of group.
462 group p (x:xs) = group' xs x x (x :)
464 group' [] _ _ s = [s []]
465 group' (x:xs) x_min x_max s
466 | x_max `p` x = group' xs x_min x (s . (x :))
467 | not (x_min `p` x) = group' xs x x_max ((x :) . s)
468 | otherwise = s [] : group' xs x x (x :)
469 -- NB: the 'not' is essential for stablity
470 -- x `p` x_min would reverse equal elements
472 generalMerge :: (a -> a -> Bool) -> [a] -> [a] -> [a]
473 generalMerge _ xs [] = xs
474 generalMerge _ [] ys = ys
475 generalMerge p (x:xs) (y:ys) | x `p` y = x : generalMerge p xs (y:ys)
476 | otherwise = y : generalMerge p (x:xs) ys
478 -- gamma is now called balancedFold
480 balancedFold :: (a -> a -> a) -> [a] -> a
481 balancedFold _ [] = error "can't reduce an empty list using balancedFold"
482 balancedFold _ [x] = x
483 balancedFold f l = balancedFold f (balancedFold' f l)
485 balancedFold' :: (a -> a -> a) -> [a] -> [a]
486 balancedFold' f (x:y:xs) = f x y : balancedFold' f xs
487 balancedFold' _ xs = xs
489 generalNaturalMergeSort :: (a -> a -> Bool) -> [a] -> [a]
490 generalNaturalMergeSort _ [] = []
491 generalNaturalMergeSort p xs = (balancedFold (generalMerge p) . group p) xs
494 generalMergeSort p [] = []
495 generalMergeSort p xs = (balancedFold (generalMerge p) . map (: [])) xs
497 mergeSort, naturalMergeSort :: Ord a => [a] -> [a]
499 mergeSort = generalMergeSort (<=)
500 naturalMergeSort = generalNaturalMergeSort (<=)
502 mergeSortLe le = generalMergeSort le
505 sortLe :: (a->a->Bool) -> [a] -> [a]
506 sortLe le = generalNaturalMergeSort le
508 sortWith :: Ord b => (a->b) -> [a] -> [a]
509 sortWith get_key xs = sortLe le xs
511 x `le` y = get_key x < get_key y
513 on :: (a -> a -> Ordering) -> (b -> a) -> b -> b -> Ordering
514 on cmp sel = \x y -> sel x `cmp` sel y
518 %************************************************************************
520 \subsection[Utils-transitive-closure]{Transitive closure}
522 %************************************************************************
524 This algorithm for transitive closure is straightforward, albeit quadratic.
527 transitiveClosure :: (a -> [a]) -- Successor function
528 -> (a -> a -> Bool) -- Equality predicate
530 -> [a] -- The transitive closure
532 transitiveClosure succ eq xs
536 go done (x:xs) | x `is_in` done = go done xs
537 | otherwise = go (x:done) (succ x ++ xs)
540 x `is_in` (y:ys) | eq x y = True
541 | otherwise = x `is_in` ys
544 %************************************************************************
546 \subsection[Utils-accum]{Accumulating}
548 %************************************************************************
550 A combination of foldl with zip. It works with equal length lists.
553 foldl2 :: (acc -> a -> b -> acc) -> acc -> [a] -> [b] -> acc
555 foldl2 k z (a:as) (b:bs) = foldl2 k (k z a b) as bs
556 foldl2 _ _ _ _ = panic "Util: foldl2"
558 all2 :: (a -> b -> Bool) -> [a] -> [b] -> Bool
559 -- True if the lists are the same length, and
560 -- all corresponding elements satisfy the predicate
562 all2 p (x:xs) (y:ys) = p x y && all2 p xs ys
566 Count the number of times a predicate is true
569 count :: (a -> Bool) -> [a] -> Int
571 count p (x:xs) | p x = 1 + count p xs
572 | otherwise = count p xs
575 @splitAt@, @take@, and @drop@ but with length of another
576 list giving the break-off point:
579 takeList :: [b] -> [a] -> [a]
584 (y:ys) -> y : takeList xs ys
586 dropList :: [b] -> [a] -> [a]
588 dropList _ xs@[] = xs
589 dropList (_:xs) (_:ys) = dropList xs ys
592 splitAtList :: [b] -> [a] -> ([a], [a])
593 splitAtList [] xs = ([], xs)
594 splitAtList _ xs@[] = (xs, xs)
595 splitAtList (_:xs) (y:ys) = (y:ys', ys'')
597 (ys', ys'') = splitAtList xs ys
599 snocView :: [a] -> Maybe ([a],a)
600 -- Split off the last element
601 snocView [] = Nothing
602 snocView xs = go [] xs
604 -- Invariant: second arg is non-empty
605 go acc [x] = Just (reverse acc, x)
606 go acc (x:xs) = go (x:acc) xs
607 go _ [] = panic "Util: snocView"
609 split :: Char -> String -> [String]
610 split c s = case rest of
612 _:rest -> chunk : split c rest
613 where (chunk, rest) = break (==c) s
617 %************************************************************************
619 \subsection[Utils-comparison]{Comparisons}
621 %************************************************************************
624 isEqual :: Ordering -> Bool
625 -- Often used in (isEqual (a `compare` b))
630 thenCmp :: Ordering -> Ordering -> Ordering
631 {-# INLINE thenCmp #-}
632 thenCmp EQ ordering = ordering
633 thenCmp ordering _ = ordering
635 eqListBy :: (a->a->Bool) -> [a] -> [a] -> Bool
636 eqListBy _ [] [] = True
637 eqListBy eq (x:xs) (y:ys) = eq x y && eqListBy eq xs ys
638 eqListBy _ _ _ = False
640 cmpList :: (a -> a -> Ordering) -> [a] -> [a] -> Ordering
641 -- `cmpList' uses a user-specified comparer
646 cmpList cmp (a:as) (b:bs)
647 = case cmp a b of { EQ -> cmpList cmp as bs; xxx -> xxx }
651 -- This (with a more general type) is Data.List.stripPrefix from GHC 6.8.
652 -- This definition can be removed once we require at least 6.8 to build.
653 maybePrefixMatch :: String -> String -> Maybe String
654 maybePrefixMatch [] rest = Just rest
655 maybePrefixMatch (_:_) [] = Nothing
656 maybePrefixMatch (p:pat) (r:rest)
657 | p == r = maybePrefixMatch pat rest
658 | otherwise = Nothing
660 removeSpaces :: String -> String
661 removeSpaces = reverse . dropWhile isSpace . reverse . dropWhile isSpace
664 %************************************************************************
666 \subsection[Utils-pairs]{Pairs}
668 %************************************************************************
671 unzipWith :: (a -> b -> c) -> [(a, b)] -> [c]
672 unzipWith f pairs = map ( \ (a, b) -> f a b ) pairs
676 seqList :: [a] -> b -> b
678 seqList (x:xs) b = x `seq` seqList xs b
684 global :: a -> IORef a
685 global a = unsafePerformIO (newIORef a)
689 consIORef :: IORef [a] -> a -> IO ()
692 writeIORef var (x:xs)
698 looksLikeModuleName :: String -> Bool
699 looksLikeModuleName [] = False
700 looksLikeModuleName (c:cs) = isUpper c && go cs
702 go ('.':cs) = looksLikeModuleName cs
703 go (c:cs) = (isAlphaNum c || c == '_') && go cs
706 Akin to @Prelude.words@, but acts like the Bourne shell, treating
707 quoted strings as Haskell Strings, and also parses Haskell [String]
711 getCmd :: String -> Either String -- Error
712 (String, String) -- (Cmd, Rest)
713 getCmd s = case break isSpace $ dropWhile isSpace s of
714 ([], _) -> Left ("Couldn't find command in " ++ show s)
717 toCmdArgs :: String -> Either String -- Error
718 (String, [String]) -- (Cmd, Args)
719 toCmdArgs s = case getCmd s of
721 Right (cmd, s') -> case toArgs s' of
723 Right args -> Right (cmd, args)
725 toArgs :: String -> Either String -- Error
728 = case dropWhile isSpace str of
729 s@('[':_) -> case reads s of
731 | all isSpace spaces ->
734 Left ("Couldn't read " ++ show str ++ "as [String]")
737 toArgs' s = case dropWhile isSpace s of
739 ('"' : _) -> case reads s of
741 -- rest must either be [] or start with a space
742 | all isSpace (take 1 rest) ->
745 Right args -> Right (arg : args)
747 Left ("Couldn't read " ++ show s ++ "as String")
748 s' -> case break isSpace s' of
749 (arg, s'') -> case toArgs' s'' of
751 Right args -> Right (arg : args)
754 -- -----------------------------------------------------------------------------
758 readRational__ :: ReadS Rational -- NB: doesn't handle leading "-"
759 readRational__ r = do
762 return ((n%1)*10^^(k-d), t)
765 (ds,s) <- lexDecDigits r
766 (ds',t) <- lexDotDigits s
767 return (read (ds++ds'), length ds', t)
769 readExp (e:s) | e `elem` "eE" = readExp' s
770 readExp s = return (0,s)
772 readExp' ('+':s) = readDec s
773 readExp' ('-':s) = do (k,t) <- readDec s
775 readExp' s = readDec s
778 (ds,r) <- nonnull isDigit s
779 return (foldl1 (\n d -> n * 10 + d) [ ord d - ord '0' | d <- ds ],
782 lexDecDigits = nonnull isDigit
784 lexDotDigits ('.':s) = return (span isDigit s)
785 lexDotDigits s = return ("",s)
787 nonnull p s = do (cs@(_:_),t) <- return (span p s)
790 readRational :: String -> Rational -- NB: *does* handle a leading "-"
793 '-' : xs -> - (read_me xs)
797 = case (do { (x,"") <- readRational__ s ; return x }) of
799 [] -> error ("readRational: no parse:" ++ top_s)
800 _ -> error ("readRational: ambiguous parse:" ++ top_s)
803 -----------------------------------------------------------------------------
804 -- Create a hierarchy of directories
806 createDirectoryHierarchy :: FilePath -> IO ()
807 createDirectoryHierarchy dir | isDrive dir = return () -- XXX Hack
808 createDirectoryHierarchy dir = do
809 b <- doesDirectoryExist dir
810 unless b $ do createDirectoryHierarchy (takeDirectory dir)
813 -----------------------------------------------------------------------------
814 -- Verify that the 'dirname' portion of a FilePath exists.
816 doesDirNameExist :: FilePath -> IO Bool
817 doesDirNameExist fpath = case takeDirectory fpath of
818 "" -> return True -- XXX Hack
819 _ -> doesDirectoryExist (takeDirectory fpath)
821 -- --------------------------------------------------------------
822 -- check existence & modification time at the same time
824 modificationTimeIfExists :: FilePath -> IO (Maybe ClockTime)
825 modificationTimeIfExists f = do
826 (do t <- getModificationTime f; return (Just t))
827 `IO.catch` \e -> if isDoesNotExistError e
831 -- split a string at the last character where 'pred' is True,
832 -- returning a pair of strings. The first component holds the string
833 -- up (but not including) the last character for which 'pred' returned
834 -- True, the second whatever comes after (but also not including the
837 -- If 'pred' returns False for all characters in the string, the original
838 -- string is returned in the first component (and the second one is just
840 splitLongestPrefix :: String -> (Char -> Bool) -> (String,String)
841 splitLongestPrefix str pred
842 | null r_pre = (str, [])
843 | otherwise = (reverse (tail r_pre), reverse r_suf)
844 -- 'tail' drops the char satisfying 'pred'
845 where (r_suf, r_pre) = break pred (reverse str)
847 escapeSpaces :: String -> String
848 escapeSpaces = foldr (\c s -> if isSpace c then '\\':c:s else c:s) ""
852 --------------------------------------------------------------
854 --------------------------------------------------------------
856 -- | The function splits the given string to substrings
857 -- using the 'searchPathSeparator'.
858 parseSearchPath :: String -> [FilePath]
859 parseSearchPath path = split path
861 split :: String -> [String]
865 _:rest -> chunk : split rest
869 #ifdef mingw32_HOST_OS
870 ('\"':xs@(_:_)) | last xs == '\"' -> init xs
874 (chunk', rest') = break (==searchPathSeparator) s
876 -- | A platform-specific character used to separate search path strings in
877 -- environment variables. The separator is a colon (\":\") on Unix and
878 -- Macintosh, and a semicolon (\";\") on the Windows operating system.
879 searchPathSeparator :: Char
880 #if mingw32_HOST_OS || mingw32_TARGET_OS
881 searchPathSeparator = ';'
883 searchPathSeparator = ':'
886 data Direction = Forwards | Backwards
888 reslash :: Direction -> FilePath -> FilePath
890 where f ('/' : xs) = slash : f xs
891 f ('\\' : xs) = slash : f xs
892 f (x : xs) = x : f xs