<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<!-- Generated by HsColour, http://www.cs.york.ac.uk/fp/darcs/hscolour/ -->
<title>utils/Util.lhs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
%
% (c) The University of Glasgow 2006
% (c) The University of Glasgow 1992-2002
%
\begin{code}
<pre><a name="line-1"></a><span class='hs-comment'>-- | Highly random utility functions</span>
<a name="line-2"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Util</span> <span class='hs-layout'>(</span>
<a name="line-3"></a> <span class='hs-comment'>-- * Flags dependent on the compiler build</span>
<a name="line-4"></a> <span class='hs-varid'>ghciSupported</span><span class='hs-layout'>,</span> <span class='hs-varid'>debugIsOn</span><span class='hs-layout'>,</span> <span class='hs-varid'>ghciTablesNextToCode</span><span class='hs-layout'>,</span> <span class='hs-varid'>isDynamicGhcLib</span><span class='hs-layout'>,</span>
<a name="line-5"></a> <span class='hs-varid'>isWindowsHost</span><span class='hs-layout'>,</span> <span class='hs-varid'>isWindowsTarget</span><span class='hs-layout'>,</span> <span class='hs-varid'>isDarwinTarget</span><span class='hs-layout'>,</span>
<a name="line-6"></a>
<a name="line-7"></a> <span class='hs-comment'>-- * General list processing</span>
<a name="line-8"></a> <span class='hs-varid'>zipEqual</span><span class='hs-layout'>,</span> <span class='hs-varid'>zipWithEqual</span><span class='hs-layout'>,</span> <span class='hs-varid'>zipWith3Equal</span><span class='hs-layout'>,</span> <span class='hs-varid'>zipWith4Equal</span><span class='hs-layout'>,</span>
<a name="line-9"></a> <span class='hs-varid'>zipLazy</span><span class='hs-layout'>,</span> <span class='hs-varid'>stretchZipWith</span><span class='hs-layout'>,</span>
<a name="line-10"></a>
<a name="line-11"></a> <span class='hs-varid'>unzipWith</span><span class='hs-layout'>,</span>
<a name="line-12"></a>
<a name="line-13"></a> <span class='hs-varid'>mapFst</span><span class='hs-layout'>,</span> <span class='hs-varid'>mapSnd</span><span class='hs-layout'>,</span>
<a name="line-14"></a> <span class='hs-varid'>mapAndUnzip</span><span class='hs-layout'>,</span> <span class='hs-varid'>mapAndUnzip3</span><span class='hs-layout'>,</span>
<a name="line-15"></a> <span class='hs-varid'>nOfThem</span><span class='hs-layout'>,</span> <span class='hs-varid'>filterOut</span><span class='hs-layout'>,</span> <span class='hs-varid'>partitionWith</span><span class='hs-layout'>,</span> <span class='hs-varid'>splitEithers</span><span class='hs-layout'>,</span>
<a name="line-16"></a>
<a name="line-17"></a> <span class='hs-varid'>foldl1'</span><span class='hs-layout'>,</span> <span class='hs-varid'>foldl2</span><span class='hs-layout'>,</span> <span class='hs-varid'>count</span><span class='hs-layout'>,</span> <span class='hs-varid'>all2</span><span class='hs-layout'>,</span>
<a name="line-18"></a>
<a name="line-19"></a> <span class='hs-varid'>lengthExceeds</span><span class='hs-layout'>,</span> <span class='hs-varid'>lengthIs</span><span class='hs-layout'>,</span> <span class='hs-varid'>lengthAtLeast</span><span class='hs-layout'>,</span>
<a name="line-20"></a> <span class='hs-varid'>listLengthCmp</span><span class='hs-layout'>,</span> <span class='hs-varid'>atLength</span><span class='hs-layout'>,</span> <span class='hs-varid'>equalLength</span><span class='hs-layout'>,</span> <span class='hs-varid'>compareLength</span><span class='hs-layout'>,</span>
<a name="line-21"></a>
<a name="line-22"></a> <span class='hs-varid'>isSingleton</span><span class='hs-layout'>,</span> <span class='hs-varid'>only</span><span class='hs-layout'>,</span> <span class='hs-varid'>singleton</span><span class='hs-layout'>,</span>
<a name="line-23"></a> <span class='hs-varid'>notNull</span><span class='hs-layout'>,</span> <span class='hs-varid'>snocView</span><span class='hs-layout'>,</span>
<a name="line-24"></a>
<a name="line-25"></a> <span class='hs-varid'>isIn</span><span class='hs-layout'>,</span> <span class='hs-varid'>isn'tIn</span><span class='hs-layout'>,</span>
<a name="line-26"></a>
<a name="line-27"></a> <span class='hs-comment'>-- * List operations controlled by another list</span>
<a name="line-28"></a> <span class='hs-varid'>takeList</span><span class='hs-layout'>,</span> <span class='hs-varid'>dropList</span><span class='hs-layout'>,</span> <span class='hs-varid'>splitAtList</span><span class='hs-layout'>,</span> <span class='hs-varid'>split</span><span class='hs-layout'>,</span>
<a name="line-29"></a> <span class='hs-varid'>dropTail</span><span class='hs-layout'>,</span>
<a name="line-30"></a>
<a name="line-31"></a> <span class='hs-comment'>-- * For loop</span>
<a name="line-32"></a> <span class='hs-varid'>nTimes</span><span class='hs-layout'>,</span>
<a name="line-33"></a>
<a name="line-34"></a> <span class='hs-comment'>-- * Sorting</span>
<a name="line-35"></a> <span class='hs-varid'>sortLe</span><span class='hs-layout'>,</span> <span class='hs-varid'>sortWith</span><span class='hs-layout'>,</span> <span class='hs-varid'>on</span><span class='hs-layout'>,</span>
<a name="line-36"></a>
<a name="line-37"></a> <span class='hs-comment'>-- * Comparisons</span>
<a name="line-38"></a> <span class='hs-varid'>isEqual</span><span class='hs-layout'>,</span> <span class='hs-varid'>eqListBy</span><span class='hs-layout'>,</span>
<a name="line-39"></a> <span class='hs-varid'>thenCmp</span><span class='hs-layout'>,</span> <span class='hs-varid'>cmpList</span><span class='hs-layout'>,</span>
<a name="line-40"></a> <span class='hs-varid'>removeSpaces</span><span class='hs-layout'>,</span>
<a name="line-41"></a>
<a name="line-42"></a> <span class='hs-comment'>-- * Transitive closures</span>
<a name="line-43"></a> <span class='hs-varid'>transitiveClosure</span><span class='hs-layout'>,</span>
<a name="line-44"></a>
<a name="line-45"></a> <span class='hs-comment'>-- * Strictness</span>
<a name="line-46"></a> <span class='hs-varid'>seqList</span><span class='hs-layout'>,</span>
<a name="line-47"></a>
<a name="line-48"></a> <span class='hs-comment'>-- * Module names</span>
<a name="line-49"></a> <span class='hs-varid'>looksLikeModuleName</span><span class='hs-layout'>,</span>
<a name="line-50"></a>
<a name="line-51"></a> <span class='hs-comment'>-- * Argument processing</span>
<a name="line-52"></a> <span class='hs-varid'>getCmd</span><span class='hs-layout'>,</span> <span class='hs-varid'>toCmdArgs</span><span class='hs-layout'>,</span> <span class='hs-varid'>toArgs</span><span class='hs-layout'>,</span>
<a name="line-53"></a>
<a name="line-54"></a> <span class='hs-comment'>-- * Floating point</span>
<a name="line-55"></a> <span class='hs-varid'>readRational</span><span class='hs-layout'>,</span>
<a name="line-56"></a>
<a name="line-57"></a> <span class='hs-comment'>-- * IO-ish utilities</span>
<a name="line-58"></a> <span class='hs-varid'>createDirectoryHierarchy</span><span class='hs-layout'>,</span>
<a name="line-59"></a> <span class='hs-varid'>doesDirNameExist</span><span class='hs-layout'>,</span>
<a name="line-60"></a> <span class='hs-varid'>modificationTimeIfExists</span><span class='hs-layout'>,</span>
<a name="line-61"></a>
<a name="line-62"></a> <span class='hs-varid'>global</span><span class='hs-layout'>,</span> <span class='hs-varid'>consIORef</span><span class='hs-layout'>,</span> <span class='hs-varid'>globalMVar</span><span class='hs-layout'>,</span> <span class='hs-varid'>globalEmptyMVar</span><span class='hs-layout'>,</span>
<a name="line-63"></a>
<a name="line-64"></a> <span class='hs-comment'>-- * Filenames and paths</span>
<a name="line-65"></a> <span class='hs-conid'>Suffix</span><span class='hs-layout'>,</span>
<a name="line-66"></a> <span class='hs-varid'>splitLongestPrefix</span><span class='hs-layout'>,</span>
<a name="line-67"></a> <span class='hs-varid'>escapeSpaces</span><span class='hs-layout'>,</span>
<a name="line-68"></a> <span class='hs-varid'>parseSearchPath</span><span class='hs-layout'>,</span>
<a name="line-69"></a> <span class='hs-conid'>Direction</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>reslash</span><span class='hs-layout'>,</span>
<a name="line-70"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-71"></a>
<a name="line-72"></a><span class='hs-cpp'>#include "HsVersions.h"</span>
<a name="line-73"></a>
<a name="line-74"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Panic</span>
<a name="line-75"></a>
<a name="line-76"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>IORef</span> <span class='hs-layout'>(</span> <span class='hs-conid'>IORef</span><span class='hs-layout'>,</span> <span class='hs-varid'>newIORef</span><span class='hs-layout'>,</span> <span class='hs-varid'>atomicModifyIORef</span> <span class='hs-layout'>)</span>
<a name="line-77"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>System</span><span class='hs-varop'>.</span><span class='hs-conid'>IO</span><span class='hs-varop'>.</span><span class='hs-conid'>Unsafe</span> <span class='hs-layout'>(</span> <span class='hs-varid'>unsafePerformIO</span> <span class='hs-layout'>)</span>
<a name="line-78"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>List</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-varid'>group</span><span class='hs-layout'>)</span>
<a name="line-79"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Concurrent</span><span class='hs-varop'>.</span><span class='hs-conid'>MVar</span> <span class='hs-layout'>(</span> <span class='hs-conid'>MVar</span><span class='hs-layout'>,</span> <span class='hs-varid'>newMVar</span><span class='hs-layout'>,</span> <span class='hs-varid'>newEmptyMVar</span> <span class='hs-layout'>)</span>
<a name="line-80"></a>
<a name="line-81"></a><span class='hs-cpp'>#ifdef DEBUG</span>
<a name="line-82"></a><span class='hs-keyword'>import</span> <span class='hs-keyword'>qualified</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>List</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>List</span> <span class='hs-layout'>(</span> <span class='hs-varid'>elem</span><span class='hs-layout'>,</span> <span class='hs-varid'>notElem</span> <span class='hs-layout'>)</span>
<a name="line-83"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>FastTypes</span>
<a name="line-84"></a><span class='hs-cpp'>#endif</span>
<a name="line-85"></a>
<a name="line-86"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Monad</span> <span class='hs-layout'>(</span> <span class='hs-varid'>unless</span> <span class='hs-layout'>)</span>
<a name="line-87"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>System</span><span class='hs-varop'>.</span><span class='hs-conid'>IO</span><span class='hs-varop'>.</span><span class='hs-conid'>Error</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>IO</span> <span class='hs-layout'>(</span> <span class='hs-varid'>catch</span><span class='hs-layout'>,</span> <span class='hs-varid'>isDoesNotExistError</span> <span class='hs-layout'>)</span>
<a name="line-88"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>System</span><span class='hs-varop'>.</span><span class='hs-conid'>Directory</span> <span class='hs-layout'>(</span> <span class='hs-varid'>doesDirectoryExist</span><span class='hs-layout'>,</span> <span class='hs-varid'>createDirectory</span><span class='hs-layout'>,</span>
<a name="line-89"></a> <span class='hs-varid'>getModificationTime</span> <span class='hs-layout'>)</span>
<a name="line-90"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>System</span><span class='hs-varop'>.</span><span class='hs-conid'>FilePath</span>
<a name="line-91"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Char</span> <span class='hs-layout'>(</span> <span class='hs-varid'>isUpper</span><span class='hs-layout'>,</span> <span class='hs-varid'>isAlphaNum</span><span class='hs-layout'>,</span> <span class='hs-varid'>isSpace</span><span class='hs-layout'>,</span> <span class='hs-varid'>ord</span><span class='hs-layout'>,</span> <span class='hs-varid'>isDigit</span> <span class='hs-layout'>)</span>
<a name="line-92"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Ratio</span> <span class='hs-layout'>(</span> <span class='hs-layout'>(</span><span class='hs-varop'>%</span><span class='hs-layout'>)</span> <span class='hs-layout'>)</span>
<a name="line-93"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>System</span><span class='hs-varop'>.</span><span class='hs-conid'>Time</span> <span class='hs-layout'>(</span> <span class='hs-conid'>ClockTime</span> <span class='hs-layout'>)</span>
<a name="line-94"></a>
<a name="line-95"></a><span class='hs-keyword'>infixr</span> <span class='hs-num'>9</span> <span class='hs-varop'>`thenCmp`</span>
</pre>\end{code}
%************************************************************************
%* *
\subsection{Is DEBUG on, are we on Windows, etc?}
%* *
%************************************************************************
These booleans are global constants, set by CPP flags. They allow us to
recompile a single module (this one) to change whether or not debug output
appears. They sometimes let us avoid even running CPP elsewhere.
It's important that the flags are literal constants (True/False). Then,
with -0, tests of the flags in other modules will simplify to the correct
branch of the conditional, thereby dropping debug code altogether when
the flags are off.
\begin{code}
<pre><a name="line-1"></a><a name="ghciSupported"></a><span class='hs-definition'>ghciSupported</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Bool</span>
<a name="line-2"></a><span class='hs-cpp'>#ifdef GHCI</span>
<a name="line-3"></a><span class='hs-definition'>ghciSupported</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-4"></a><span class='hs-cpp'>#else</span>
<a name="line-5"></a><span class='hs-definition'>ghciSupported</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-6"></a><span class='hs-cpp'>#endif</span>
<a name="line-7"></a>
<a name="line-8"></a><a name="debugIsOn"></a><span class='hs-definition'>debugIsOn</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Bool</span>
<a name="line-9"></a><span class='hs-cpp'>#ifdef DEBUG</span>
<a name="line-10"></a><span class='hs-definition'>debugIsOn</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-11"></a><span class='hs-cpp'>#else</span>
<a name="line-12"></a><span class='hs-definition'>debugIsOn</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-13"></a><span class='hs-cpp'>#endif</span>
<a name="line-14"></a>
<a name="line-15"></a><a name="ghciTablesNextToCode"></a><span class='hs-definition'>ghciTablesNextToCode</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Bool</span>
<a name="line-16"></a><span class='hs-cpp'>#ifdef GHCI_TABLES_NEXT_TO_CODE</span>
<a name="line-17"></a><span class='hs-definition'>ghciTablesNextToCode</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-18"></a><span class='hs-cpp'>#else</span>
<a name="line-19"></a><span class='hs-definition'>ghciTablesNextToCode</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-20"></a><span class='hs-cpp'>#endif</span>
<a name="line-21"></a>
<a name="line-22"></a><a name="isDynamicGhcLib"></a><span class='hs-definition'>isDynamicGhcLib</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Bool</span>
<a name="line-23"></a><span class='hs-cpp'>#ifdef DYNAMIC</span>
<a name="line-24"></a><span class='hs-definition'>isDynamicGhcLib</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-25"></a><span class='hs-cpp'>#else</span>
<a name="line-26"></a><span class='hs-definition'>isDynamicGhcLib</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-27"></a><span class='hs-cpp'>#endif</span>
<a name="line-28"></a>
<a name="line-29"></a><a name="isWindowsHost"></a><span class='hs-definition'>isWindowsHost</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Bool</span>
<a name="line-30"></a><span class='hs-cpp'>#ifdef mingw32_HOST_OS</span>
<a name="line-31"></a><span class='hs-definition'>isWindowsHost</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-32"></a><span class='hs-cpp'>#else</span>
<a name="line-33"></a><span class='hs-definition'>isWindowsHost</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-34"></a><span class='hs-cpp'>#endif</span>
<a name="line-35"></a>
<a name="line-36"></a><a name="isWindowsTarget"></a><span class='hs-definition'>isWindowsTarget</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Bool</span>
<a name="line-37"></a><span class='hs-cpp'>#ifdef mingw32_TARGET_OS</span>
<a name="line-38"></a><span class='hs-definition'>isWindowsTarget</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-39"></a><span class='hs-cpp'>#else</span>
<a name="line-40"></a><span class='hs-definition'>isWindowsTarget</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-41"></a><span class='hs-cpp'>#endif</span>
<a name="line-42"></a>
<a name="line-43"></a><a name="isDarwinTarget"></a><span class='hs-definition'>isDarwinTarget</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Bool</span>
<a name="line-44"></a><span class='hs-cpp'>#ifdef darwin_TARGET_OS</span>
<a name="line-45"></a><span class='hs-definition'>isDarwinTarget</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-46"></a><span class='hs-cpp'>#else</span>
<a name="line-47"></a><span class='hs-definition'>isDarwinTarget</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-48"></a><span class='hs-cpp'>#endif</span>
</pre>\end{code}
%************************************************************************
%* *
\subsection{A for loop}
%* *
%************************************************************************
\begin{code}
<pre><a name="line-1"></a><a name="nTimes"></a><span class='hs-comment'>-- | Compose a function with itself n times. (nth rather than twice)</span>
<a name="line-2"></a><span class='hs-definition'>nTimes</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-3"></a><span class='hs-definition'>nTimes</span> <span class='hs-num'>0</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>id</span>
<a name="line-4"></a><span class='hs-definition'>nTimes</span> <span class='hs-num'>1</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span>
<a name="line-5"></a><span class='hs-definition'>nTimes</span> <span class='hs-varid'>n</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span> <span class='hs-varop'>.</span> <span class='hs-varid'>nTimes</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span><span class='hs-comment'>-</span><span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>f</span>
</pre>\end{code}
%************************************************************************
%* *
\subsection[Utils-lists]{General list processing}
%* *
%************************************************************************
\begin{code}
<pre><a name="line-1"></a><a name="filterOut"></a><span class='hs-definition'>filterOut</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>-></span><span class='hs-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-2"></a><span class='hs-comment'>-- ^ Like filter, only it reverses the sense of the test</span>
<a name="line-3"></a><span class='hs-definition'>filterOut</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-4"></a><span class='hs-definition'>filterOut</span> <span class='hs-varid'>p</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>p</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>filterOut</span> <span class='hs-varid'>p</span> <span class='hs-varid'>xs</span>
<a name="line-5"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <span class='hs-conop'>:</span> <span class='hs-varid'>filterOut</span> <span class='hs-varid'>p</span> <span class='hs-varid'>xs</span>
<a name="line-6"></a>
<a name="line-7"></a><a name="partitionWith"></a><span class='hs-definition'>partitionWith</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Either</span> <span class='hs-varid'>b</span> <span class='hs-varid'>c</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>c</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span>
<a name="line-8"></a><span class='hs-comment'>-- ^ Uses a function to determine which of two output lists an input element should join</span>
<a name="line-9"></a><span class='hs-definition'>partitionWith</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-conid'>[]</span><span class='hs-layout'>,</span><span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-10"></a><span class='hs-definition'>partitionWith</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span> <span class='hs-keyword'>of</span>
<a name="line-11"></a> <span class='hs-conid'>Left</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-conop'>:</span><span class='hs-varid'>bs</span><span class='hs-layout'>,</span> <span class='hs-varid'>cs</span><span class='hs-layout'>)</span>
<a name="line-12"></a> <span class='hs-conid'>Right</span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>bs</span><span class='hs-layout'>,</span> <span class='hs-varid'>c</span><span class='hs-conop'>:</span><span class='hs-varid'>cs</span><span class='hs-layout'>)</span>
<a name="line-13"></a> <span class='hs-keyword'>where</span> <span class='hs-layout'>(</span><span class='hs-varid'>bs</span><span class='hs-layout'>,</span><span class='hs-varid'>cs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>partitionWith</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xs</span>
<a name="line-14"></a>
<a name="line-15"></a><a name="splitEithers"></a><span class='hs-definition'>splitEithers</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Either</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span>
<a name="line-16"></a><span class='hs-comment'>-- ^ Teases a list of 'Either's apart into two lists</span>
<a name="line-17"></a><span class='hs-definition'>splitEithers</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-conid'>[]</span><span class='hs-layout'>,</span><span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-18"></a><span class='hs-definition'>splitEithers</span> <span class='hs-layout'>(</span><span class='hs-varid'>e</span> <span class='hs-conop'>:</span> <span class='hs-varid'>es</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>e</span> <span class='hs-keyword'>of</span>
<a name="line-19"></a> <span class='hs-conid'>Left</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>,</span> <span class='hs-varid'>ys</span><span class='hs-layout'>)</span>
<a name="line-20"></a> <span class='hs-conid'>Right</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>xs</span><span class='hs-layout'>,</span> <span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span>
<a name="line-21"></a> <span class='hs-keyword'>where</span> <span class='hs-layout'>(</span><span class='hs-varid'>xs</span><span class='hs-layout'>,</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>splitEithers</span> <span class='hs-varid'>es</span>
</pre>\end{code}
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?
\begin{code}
<pre><a name="line-1"></a><a name="zipEqual"></a><span class='hs-definition'>zipEqual</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span><span class='hs-varid'>b</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-2"></a><a name="zipWithEqual"></a><span class='hs-definition'>zipWithEqual</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>b</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>c</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span><span class='hs-keyglyph'>-></span><span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span><span class='hs-keyglyph'>-></span><span class='hs-keyglyph'>[</span><span class='hs-varid'>c</span><span class='hs-keyglyph'>]</span>
<a name="line-3"></a><a name="zipWith3Equal"></a><span class='hs-definition'>zipWith3Equal</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>b</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>c</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>d</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span><span class='hs-keyglyph'>-></span><span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span><span class='hs-keyglyph'>-></span><span class='hs-keyglyph'>[</span><span class='hs-varid'>c</span><span class='hs-keyglyph'>]</span><span class='hs-keyglyph'>-></span><span class='hs-keyglyph'>[</span><span class='hs-varid'>d</span><span class='hs-keyglyph'>]</span>
<a name="line-4"></a><a name="zipWith4Equal"></a><span class='hs-definition'>zipWith4Equal</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>b</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>c</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>d</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>e</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span><span class='hs-keyglyph'>-></span><span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span><span class='hs-keyglyph'>-></span><span class='hs-keyglyph'>[</span><span class='hs-varid'>c</span><span class='hs-keyglyph'>]</span><span class='hs-keyglyph'>-></span><span class='hs-keyglyph'>[</span><span class='hs-varid'>d</span><span class='hs-keyglyph'>]</span><span class='hs-keyglyph'>-></span><span class='hs-keyglyph'>[</span><span class='hs-varid'>e</span><span class='hs-keyglyph'>]</span>
<a name="line-5"></a>
<a name="line-6"></a><span class='hs-cpp'>#ifndef DEBUG</span>
<a name="line-7"></a><span class='hs-definition'>zipEqual</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>zip</span>
<a name="line-8"></a><span class='hs-definition'>zipWithEqual</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>zipWith</span>
<a name="line-9"></a><span class='hs-definition'>zipWith3Equal</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>zipWith3</span>
<a name="line-10"></a><span class='hs-definition'>zipWith4Equal</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>zipWith4</span>
<a name="line-11"></a><span class='hs-cpp'>#else</span>
<a name="line-12"></a><span class='hs-definition'>zipEqual</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-13"></a><span class='hs-definition'>zipEqual</span> <span class='hs-varid'>msg</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-conop'>:</span><span class='hs-keyword'>as</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-conop'>:</span><span class='hs-varid'>bs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span><span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-varid'>zipEqual</span> <span class='hs-varid'>msg</span> <span class='hs-keyword'>as</span> <span class='hs-varid'>bs</span>
<a name="line-14"></a><span class='hs-definition'>zipEqual</span> <span class='hs-varid'>msg</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>panic</span> <span class='hs-layout'>(</span><span class='hs-str'>"zipEqual: unequal lists:"</span><span class='hs-varop'>++</span><span class='hs-varid'>msg</span><span class='hs-layout'>)</span>
<a name="line-15"></a>
<a name="line-16"></a><span class='hs-definition'>zipWithEqual</span> <span class='hs-varid'>msg</span> <span class='hs-varid'>z</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-conop'>:</span><span class='hs-keyword'>as</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-conop'>:</span><span class='hs-varid'>bs</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>=</span> <span class='hs-varid'>z</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-conop'>:</span> <span class='hs-varid'>zipWithEqual</span> <span class='hs-varid'>msg</span> <span class='hs-varid'>z</span> <span class='hs-keyword'>as</span> <span class='hs-varid'>bs</span>
<a name="line-17"></a><span class='hs-definition'>zipWithEqual</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-18"></a><span class='hs-definition'>zipWithEqual</span> <span class='hs-varid'>msg</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>panic</span> <span class='hs-layout'>(</span><span class='hs-str'>"zipWithEqual: unequal lists:"</span><span class='hs-varop'>++</span><span class='hs-varid'>msg</span><span class='hs-layout'>)</span>
<a name="line-19"></a>
<a name="line-20"></a><span class='hs-definition'>zipWith3Equal</span> <span class='hs-varid'>msg</span> <span class='hs-varid'>z</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-conop'>:</span><span class='hs-keyword'>as</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-conop'>:</span><span class='hs-varid'>bs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>c</span><span class='hs-conop'>:</span><span class='hs-varid'>cs</span><span class='hs-layout'>)</span>
<a name="line-21"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>z</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-varid'>c</span> <span class='hs-conop'>:</span> <span class='hs-varid'>zipWith3Equal</span> <span class='hs-varid'>msg</span> <span class='hs-varid'>z</span> <span class='hs-keyword'>as</span> <span class='hs-varid'>bs</span> <span class='hs-varid'>cs</span>
<a name="line-22"></a><span class='hs-definition'>zipWith3Equal</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-23"></a><span class='hs-definition'>zipWith3Equal</span> <span class='hs-varid'>msg</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>panic</span> <span class='hs-layout'>(</span><span class='hs-str'>"zipWith3Equal: unequal lists:"</span><span class='hs-varop'>++</span><span class='hs-varid'>msg</span><span class='hs-layout'>)</span>
<a name="line-24"></a>
<a name="line-25"></a><span class='hs-definition'>zipWith4Equal</span> <span class='hs-varid'>msg</span> <span class='hs-varid'>z</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-conop'>:</span><span class='hs-keyword'>as</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-conop'>:</span><span class='hs-varid'>bs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>c</span><span class='hs-conop'>:</span><span class='hs-varid'>cs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>d</span><span class='hs-conop'>:</span><span class='hs-varid'>ds</span><span class='hs-layout'>)</span>
<a name="line-26"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>z</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-varid'>c</span> <span class='hs-varid'>d</span> <span class='hs-conop'>:</span> <span class='hs-varid'>zipWith4Equal</span> <span class='hs-varid'>msg</span> <span class='hs-varid'>z</span> <span class='hs-keyword'>as</span> <span class='hs-varid'>bs</span> <span class='hs-varid'>cs</span> <span class='hs-varid'>ds</span>
<a name="line-27"></a><span class='hs-definition'>zipWith4Equal</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-28"></a><span class='hs-definition'>zipWith4Equal</span> <span class='hs-varid'>msg</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>panic</span> <span class='hs-layout'>(</span><span class='hs-str'>"zipWith4Equal: unequal lists:"</span><span class='hs-varop'>++</span><span class='hs-varid'>msg</span><span class='hs-layout'>)</span>
<a name="line-29"></a><span class='hs-cpp'>#endif</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="zipLazy"></a><span class='hs-comment'>-- | 'zipLazy' is a kind of 'zip' that is lazy in the second list (observe the ~)</span>
<a name="line-2"></a><span class='hs-definition'>zipLazy</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span><span class='hs-varid'>b</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-3"></a><span class='hs-definition'>zipLazy</span> <span class='hs-conid'>[]</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-4"></a><span class='hs-comment'>-- We want to write this, but with GHC 6.4 we get a warning, so it</span>
<a name="line-5"></a><span class='hs-comment'>-- doesn't validate:</span>
<a name="line-6"></a><span class='hs-comment'>-- zipLazy (x:xs) ~(y:ys) = (x,y) : zipLazy xs ys</span>
<a name="line-7"></a><span class='hs-comment'>-- so we write this instead:</span>
<a name="line-8"></a><span class='hs-definition'>zipLazy</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-varid'>zs</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>y</span> <span class='hs-conop'>:</span> <span class='hs-varid'>ys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>zs</span>
<a name="line-9"></a> <span class='hs-keyword'>in</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-layout'>,</span><span class='hs-varid'>y</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-varid'>zipLazy</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="stretchZipWith"></a><span class='hs-definition'>stretchZipWith</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>b</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>c</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>c</span><span class='hs-keyglyph'>]</span>
<a name="line-2"></a><span class='hs-comment'>-- ^ @stretchZipWith p z f xs ys@ stretches @ys@ by inserting @z@ in</span>
<a name="line-3"></a><span class='hs-comment'>-- the places where @p@ returns @True@</span>
<a name="line-4"></a>
<a name="line-5"></a><span class='hs-definition'>stretchZipWith</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-6"></a><span class='hs-definition'>stretchZipWith</span> <span class='hs-varid'>p</span> <span class='hs-varid'>z</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-varid'>ys</span>
<a name="line-7"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>p</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span> <span class='hs-varid'>z</span> <span class='hs-conop'>:</span> <span class='hs-varid'>stretchZipWith</span> <span class='hs-varid'>p</span> <span class='hs-varid'>z</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
<a name="line-8"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>ys</span> <span class='hs-keyword'>of</span>
<a name="line-9"></a> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>[]</span>
<a name="line-10"></a> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-conop'>:</span> <span class='hs-varid'>stretchZipWith</span> <span class='hs-varid'>p</span> <span class='hs-varid'>z</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="mapFst"></a><span class='hs-definition'>mapFst</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>c</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span><span class='hs-varid'>b</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>c</span><span class='hs-layout'>,</span><span class='hs-varid'>b</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-2"></a><a name="mapSnd"></a><span class='hs-definition'>mapSnd</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>c</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span><span class='hs-varid'>b</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span><span class='hs-varid'>c</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-3"></a>
<a name="line-4"></a><span class='hs-definition'>mapFst</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xys</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varid'>x</span><span class='hs-layout'>,</span> <span class='hs-varid'>y</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-layout'>,</span><span class='hs-varid'>y</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>xys</span><span class='hs-keyglyph'>]</span>
<a name="line-5"></a><span class='hs-definition'>mapSnd</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xys</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-layout'>,</span> <span class='hs-varid'>f</span> <span class='hs-varid'>y</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-layout'>,</span><span class='hs-varid'>y</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>xys</span><span class='hs-keyglyph'>]</span>
<a name="line-6"></a>
<a name="line-7"></a><a name="mapAndUnzip"></a><span class='hs-definition'>mapAndUnzip</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-layout'>,</span> <span class='hs-varid'>c</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>c</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span>
<a name="line-8"></a>
<a name="line-9"></a><span class='hs-definition'>mapAndUnzip</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-conid'>[]</span><span class='hs-layout'>,</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-10"></a><span class='hs-definition'>mapAndUnzip</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
<a name="line-11"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>r1</span><span class='hs-layout'>,</span> <span class='hs-varid'>r2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span>
<a name="line-12"></a> <span class='hs-layout'>(</span><span class='hs-varid'>rs1</span><span class='hs-layout'>,</span> <span class='hs-varid'>rs2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mapAndUnzip</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xs</span>
<a name="line-13"></a> <span class='hs-keyword'>in</span>
<a name="line-14"></a> <span class='hs-layout'>(</span><span class='hs-varid'>r1</span><span class='hs-conop'>:</span><span class='hs-varid'>rs1</span><span class='hs-layout'>,</span> <span class='hs-varid'>r2</span><span class='hs-conop'>:</span><span class='hs-varid'>rs2</span><span class='hs-layout'>)</span>
<a name="line-15"></a>
<a name="line-16"></a><a name="mapAndUnzip3"></a><span class='hs-definition'>mapAndUnzip3</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-layout'>,</span> <span class='hs-varid'>c</span><span class='hs-layout'>,</span> <span class='hs-varid'>d</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>c</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>d</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span>
<a name="line-17"></a>
<a name="line-18"></a><span class='hs-definition'>mapAndUnzip3</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-conid'>[]</span><span class='hs-layout'>,</span> <span class='hs-conid'>[]</span><span class='hs-layout'>,</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-19"></a><span class='hs-definition'>mapAndUnzip3</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
<a name="line-20"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>r1</span><span class='hs-layout'>,</span> <span class='hs-varid'>r2</span><span class='hs-layout'>,</span> <span class='hs-varid'>r3</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span>
<a name="line-21"></a> <span class='hs-layout'>(</span><span class='hs-varid'>rs1</span><span class='hs-layout'>,</span> <span class='hs-varid'>rs2</span><span class='hs-layout'>,</span> <span class='hs-varid'>rs3</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mapAndUnzip3</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xs</span>
<a name="line-22"></a> <span class='hs-keyword'>in</span>
<a name="line-23"></a> <span class='hs-layout'>(</span><span class='hs-varid'>r1</span><span class='hs-conop'>:</span><span class='hs-varid'>rs1</span><span class='hs-layout'>,</span> <span class='hs-varid'>r2</span><span class='hs-conop'>:</span><span class='hs-varid'>rs2</span><span class='hs-layout'>,</span> <span class='hs-varid'>r3</span><span class='hs-conop'>:</span><span class='hs-varid'>rs3</span><span class='hs-layout'>)</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="nOfThem"></a><span class='hs-definition'>nOfThem</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-2"></a><span class='hs-definition'>nOfThem</span> <span class='hs-varid'>n</span> <span class='hs-varid'>thing</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>replicate</span> <span class='hs-varid'>n</span> <span class='hs-varid'>thing</span>
<a name="line-3"></a>
<a name="line-4"></a><a name="atLength"></a><span class='hs-comment'>-- | @atLength atLen atEnd ls n@ unravels list @ls@ to position @n@. Precisely:</span>
<a name="line-5"></a><span class='hs-comment'>--</span>
<a name="line-6"></a><span class='hs-comment'>-- @</span>
<a name="line-7"></a><span class='hs-comment'>-- atLength atLenPred atEndPred ls n</span>
<a name="line-8"></a><span class='hs-comment'>-- | n < 0 = atLenPred n</span>
<a name="line-9"></a><span class='hs-comment'>-- | length ls < n = atEndPred (n - length ls)</span>
<a name="line-10"></a><span class='hs-comment'>-- | otherwise = atLenPred (drop n ls)</span>
<a name="line-11"></a><span class='hs-comment'>-- @</span>
<a name="line-12"></a><span class='hs-definition'>atLength</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-13"></a> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-14"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-15"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Int</span>
<a name="line-16"></a> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span>
<a name="line-17"></a><span class='hs-definition'>atLength</span> <span class='hs-varid'>atLenPred</span> <span class='hs-varid'>atEndPred</span> <span class='hs-varid'>ls</span> <span class='hs-varid'>n</span>
<a name="line-18"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>n</span> <span class='hs-varop'><</span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>atEndPred</span> <span class='hs-varid'>n</span>
<a name="line-19"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-varid'>n</span> <span class='hs-varid'>ls</span>
<a name="line-20"></a> <span class='hs-keyword'>where</span>
<a name="line-21"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>n</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>atEndPred</span> <span class='hs-varid'>n</span>
<a name="line-22"></a> <span class='hs-varid'>go</span> <span class='hs-num'>0</span> <span class='hs-varid'>ls</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>atLenPred</span> <span class='hs-varid'>ls</span>
<a name="line-23"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span><span class='hs-comment'>-</span><span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
<a name="line-24"></a>
<a name="line-25"></a><span class='hs-comment'>-- Some special cases of atLength:</span>
<a name="line-26"></a>
<a name="line-27"></a><a name="lengthExceeds"></a><span class='hs-definition'>lengthExceeds</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-28"></a><span class='hs-comment'>-- ^ > (lengthExceeds xs n) = (length xs > n)</span>
<a name="line-29"></a><span class='hs-definition'>lengthExceeds</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>atLength</span> <span class='hs-varid'>notNull</span> <span class='hs-layout'>(</span><span class='hs-varid'>const</span> <span class='hs-conid'>False</span><span class='hs-layout'>)</span>
<a name="line-30"></a>
<a name="line-31"></a><a name="lengthAtLeast"></a><span class='hs-definition'>lengthAtLeast</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-32"></a><span class='hs-definition'>lengthAtLeast</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>atLength</span> <span class='hs-varid'>notNull</span> <span class='hs-layout'>(</span><span class='hs-varop'>==</span> <span class='hs-num'>0</span><span class='hs-layout'>)</span>
<a name="line-33"></a>
<a name="line-34"></a><a name="lengthIs"></a><span class='hs-definition'>lengthIs</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-35"></a><span class='hs-definition'>lengthIs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>atLength</span> <span class='hs-varid'>null</span> <span class='hs-layout'>(</span><span class='hs-varop'>==</span><span class='hs-num'>0</span><span class='hs-layout'>)</span>
<a name="line-36"></a>
<a name="line-37"></a><a name="listLengthCmp"></a><span class='hs-definition'>listLengthCmp</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Ordering</span>
<a name="line-38"></a><span class='hs-definition'>listLengthCmp</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>atLength</span> <span class='hs-varid'>atLen</span> <span class='hs-varid'>atEnd</span>
<a name="line-39"></a> <span class='hs-keyword'>where</span>
<a name="line-40"></a> <span class='hs-varid'>atEnd</span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>EQ</span>
<a name="line-41"></a> <span class='hs-varid'>atEnd</span> <span class='hs-varid'>x</span>
<a name="line-42"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>x</span> <span class='hs-varop'>></span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>LT</span> <span class='hs-comment'>-- not yet seen 'n' elts, so list length is < n.</span>
<a name="line-43"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>GT</span>
<a name="line-44"></a>
<a name="line-45"></a> <span class='hs-varid'>atLen</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>EQ</span>
<a name="line-46"></a> <span class='hs-varid'>atLen</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>GT</span>
<a name="line-47"></a>
<a name="line-48"></a><a name="equalLength"></a><span class='hs-definition'>equalLength</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-49"></a><span class='hs-definition'>equalLength</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-50"></a><span class='hs-definition'>equalLength</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>equalLength</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
<a name="line-51"></a><span class='hs-definition'>equalLength</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-52"></a>
<a name="line-53"></a><a name="compareLength"></a><span class='hs-definition'>compareLength</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Ordering</span>
<a name="line-54"></a><span class='hs-definition'>compareLength</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>EQ</span>
<a name="line-55"></a><span class='hs-definition'>compareLength</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>compareLength</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
<a name="line-56"></a><span class='hs-definition'>compareLength</span> <span class='hs-conid'>[]</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>LT</span>
<a name="line-57"></a><span class='hs-definition'>compareLength</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>GT</span>
<a name="line-58"></a>
<a name="line-59"></a><a name="singleton"></a><span class='hs-comment'>----------------------------</span>
<a name="line-60"></a><span class='hs-definition'>singleton</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-61"></a><span class='hs-definition'>singleton</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>x</span><span class='hs-keyglyph'>]</span>
<a name="line-62"></a>
<a name="line-63"></a><a name="isSingleton"></a><span class='hs-definition'>isSingleton</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-64"></a><span class='hs-definition'>isSingleton</span> <span class='hs-keyglyph'>[</span><span class='hs-keyword'>_</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-65"></a><span class='hs-definition'>isSingleton</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-66"></a>
<a name="line-67"></a><a name="notNull"></a><span class='hs-definition'>notNull</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-68"></a><span class='hs-definition'>notNull</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-69"></a><span class='hs-definition'>notNull</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-70"></a>
<a name="line-71"></a><a name="only"></a><span class='hs-definition'>only</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-72"></a><span class='hs-cpp'>#ifdef DEBUG</span>
<a name="line-73"></a><span class='hs-definition'>only</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>a</span>
<a name="line-74"></a><span class='hs-cpp'>#else</span>
<a name="line-75"></a><span class='hs-definition'>only</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>a</span>
<a name="line-76"></a><span class='hs-cpp'>#endif</span>
<a name="line-77"></a><span class='hs-definition'>only</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>panic</span> <span class='hs-str'>"Util: only"</span>
</pre>\end{code}
Debugging/specialising versions of \tr{elem} and \tr{notElem}
\begin{code}
<pre><a name="line-1"></a><a name="isIn"></a><span class='hs-definition'>isIn</span><span class='hs-layout'>,</span> <span class='hs-varid'>isn'tIn</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Eq</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-2"></a>
<a name="line-3"></a><span class='hs-cpp'># ifndef DEBUG</span>
<a name="line-4"></a><span class='hs-definition'>isIn</span> <span class='hs-sel'>_msg</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>elem__</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span>
<a name="line-5"></a><a name="isn'tIn"></a><span class='hs-definition'>isn'tIn</span> <span class='hs-sel'>_msg</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>notElem__</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span>
<a name="line-6"></a>
<a name="line-7"></a><a name="elem__"></a><span class='hs-comment'>--these are here to be SPECIALIZEd (automagically)</span>
<a name="line-8"></a><span class='hs-definition'>elem__</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Eq</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-9"></a><span class='hs-definition'>elem__</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-10"></a><span class='hs-definition'>elem__</span> <span class='hs-varid'>x</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <span class='hs-varop'>==</span> <span class='hs-varid'>y</span> <span class='hs-varop'>||</span> <span class='hs-varid'>elem__</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span>
<a name="line-11"></a>
<a name="line-12"></a><a name="notElem__"></a><span class='hs-definition'>notElem__</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Eq</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-13"></a><span class='hs-definition'>notElem__</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-14"></a><span class='hs-definition'>notElem__</span> <span class='hs-varid'>x</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <span class='hs-varop'>/=</span> <span class='hs-varid'>y</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>notElem__</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span>
<a name="line-15"></a>
<a name="line-16"></a><span class='hs-cpp'># else /* DEBUG */</span>
<a name="line-17"></a><span class='hs-definition'>isIn</span> <span class='hs-varid'>msg</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span>
<a name="line-18"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>elem</span> <span class='hs-layout'>(</span><span class='hs-sel'>_ILIT</span><span class='hs-layout'>(</span><span class='hs-num'>0</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span>
<a name="line-19"></a> <span class='hs-keyword'>where</span>
<a name="line-20"></a> <span class='hs-varid'>elem</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-21"></a> <span class='hs-varid'>elem</span> <span class='hs-varid'>i</span> <span class='hs-varid'>x</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span>
<a name="line-22"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span> <span class='hs-varop'>>#</span> <span class='hs-sel'>_ILIT</span><span class='hs-layout'>(</span><span class='hs-num'>100</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>trace</span> <span class='hs-layout'>(</span><span class='hs-str'>"Over-long elem in "</span> <span class='hs-varop'>++</span> <span class='hs-varid'>msg</span><span class='hs-layout'>)</span>
<a name="line-23"></a> <span class='hs-layout'>(</span><span class='hs-varid'>x</span> <span class='hs-varop'>`</span><span class='hs-conid'>List</span><span class='hs-varop'>.</span><span class='hs-varid'>elem</span><span class='hs-varop'>`</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-24"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <span class='hs-varop'>==</span> <span class='hs-varid'>y</span> <span class='hs-varop'>||</span> <span class='hs-varid'>elem</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span> <span class='hs-varop'>+#</span> <span class='hs-sel'>_ILIT</span><span class='hs-layout'>(</span><span class='hs-num'>1</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span>
<a name="line-25"></a>
<a name="line-26"></a><span class='hs-definition'>isn'tIn</span> <span class='hs-varid'>msg</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span>
<a name="line-27"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>notElem</span> <span class='hs-layout'>(</span><span class='hs-sel'>_ILIT</span><span class='hs-layout'>(</span><span class='hs-num'>0</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span>
<a name="line-28"></a> <span class='hs-keyword'>where</span>
<a name="line-29"></a> <span class='hs-varid'>notElem</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-30"></a> <span class='hs-varid'>notElem</span> <span class='hs-varid'>i</span> <span class='hs-varid'>x</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span>
<a name="line-31"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span> <span class='hs-varop'>>#</span> <span class='hs-sel'>_ILIT</span><span class='hs-layout'>(</span><span class='hs-num'>100</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>trace</span> <span class='hs-layout'>(</span><span class='hs-str'>"Over-long notElem in "</span> <span class='hs-varop'>++</span> <span class='hs-varid'>msg</span><span class='hs-layout'>)</span>
<a name="line-32"></a> <span class='hs-layout'>(</span><span class='hs-varid'>x</span> <span class='hs-varop'>`</span><span class='hs-conid'>List</span><span class='hs-varop'>.</span><span class='hs-varid'>notElem</span><span class='hs-varop'>`</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-33"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <span class='hs-varop'>/=</span> <span class='hs-varid'>y</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>notElem</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span> <span class='hs-varop'>+#</span> <span class='hs-sel'>_ILIT</span><span class='hs-layout'>(</span><span class='hs-num'>1</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span>
<a name="line-34"></a><span class='hs-cpp'># endif /* DEBUG */</span>
</pre>\end{code}
%************************************************************************
%* *
\subsubsection[Utils-Carsten-mergesort]{A mergesort from Carsten}
%* *
%************************************************************************
\begin{display}
Date: Mon, 3 May 93 20:45:23 +0200
From: Carsten Kehler Holst <kehler@cs.chalmers.se>
To: partain@dcs.gla.ac.uk
Subject: natural merge sort beats quick sort [ and it is prettier ]
Here is a piece of Haskell code that I'm rather fond of. See it as an
attempt to get rid of the ridiculous quick-sort routine. group is
quite useful by itself I think it was John's idea originally though I
believe the lazy version is due to me [surprisingly complicated].
gamma [used to be called] is called gamma because I got inspired by
the Gamma calculus. It is not very close to the calculus but does
behave less sequentially than both foldr and foldl. One could imagine
a version of gamma that took a unit element as well thereby avoiding
the problem with empty lists.
I've tried this code against
1) insertion sort - as provided by haskell
2) the normal implementation of quick sort
3) a deforested version of quick sort due to Jan Sparud
4) a super-optimized-quick-sort of Lennart's
If the list is partially sorted both merge sort and in particular
natural merge sort wins. If the list is random [ average length of
rising subsequences = approx 2 ] mergesort still wins and natural
merge sort is marginally beaten by Lennart's soqs. The space
consumption of merge sort is a bit worse than Lennart's quick sort
approx a factor of 2. And a lot worse if Sparud's bug-fix [see his
fpca article ] isn't used because of group.
have fun
Carsten
\end{display}
\begin{code}
<pre><a name="line-1"></a><a name="group"></a><span class='hs-definition'>group</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span><span class='hs-keyglyph'>]</span>
<a name="line-2"></a><span class='hs-comment'>-- Given a <= function, group finds maximal contiguous up-runs</span>
<a name="line-3"></a><span class='hs-comment'>-- or down-runs in the input list.</span>
<a name="line-4"></a><span class='hs-comment'>-- It's stable, in the sense that it never re-orders equal elements</span>
<a name="line-5"></a><span class='hs-comment'>--</span>
<a name="line-6"></a><span class='hs-comment'>-- Date: Mon, 12 Feb 1996 15:09:41 +0000</span>
<a name="line-7"></a><span class='hs-comment'>-- From: Andy Gill <andy@dcs.gla.ac.uk></span>
<a name="line-8"></a><span class='hs-comment'>-- Here is a `better' definition of group.</span>
<a name="line-9"></a>
<a name="line-10"></a><span class='hs-definition'>group</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-11"></a><span class='hs-definition'>group</span> <span class='hs-varid'>p</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>group'</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>x</span> <span class='hs-varid'>x</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span> <span class='hs-conop'>:</span><span class='hs-layout'>)</span>
<a name="line-12"></a> <span class='hs-keyword'>where</span>
<a name="line-13"></a> <span class='hs-varid'>group'</span> <span class='hs-conid'>[]</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>s</span> <span class='hs-conid'>[]</span><span class='hs-keyglyph'>]</span>
<a name="line-14"></a> <span class='hs-varid'>group'</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-varid'>x_min</span> <span class='hs-varid'>x_max</span> <span class='hs-varid'>s</span>
<a name="line-15"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>x_max</span> <span class='hs-varop'>`p`</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>group'</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>x_min</span> <span class='hs-varid'>x</span> <span class='hs-layout'>(</span><span class='hs-varid'>s</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span> <span class='hs-conop'>:</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-16"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>not</span> <span class='hs-layout'>(</span><span class='hs-varid'>x_min</span> <span class='hs-varop'>`p`</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>group'</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>x</span> <span class='hs-varid'>x_max</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>x</span> <span class='hs-conop'>:</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-varid'>s</span><span class='hs-layout'>)</span>
<a name="line-17"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>s</span> <span class='hs-conid'>[]</span> <span class='hs-conop'>:</span> <span class='hs-varid'>group'</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>x</span> <span class='hs-varid'>x</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span> <span class='hs-conop'>:</span><span class='hs-layout'>)</span>
<a name="line-18"></a> <span class='hs-comment'>-- NB: the 'not' is essential for stablity</span>
<a name="line-19"></a> <span class='hs-comment'>-- x `p` x_min would reverse equal elements</span>
<a name="line-20"></a>
<a name="line-21"></a><a name="generalMerge"></a><span class='hs-definition'>generalMerge</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-22"></a><span class='hs-definition'>generalMerge</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>xs</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>xs</span>
<a name="line-23"></a><span class='hs-definition'>generalMerge</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>ys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ys</span>
<a name="line-24"></a><span class='hs-definition'>generalMerge</span> <span class='hs-varid'>p</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>x</span> <span class='hs-varop'>`p`</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <span class='hs-conop'>:</span> <span class='hs-varid'>generalMerge</span> <span class='hs-varid'>p</span> <span class='hs-varid'>xs</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span>
<a name="line-25"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>y</span> <span class='hs-conop'>:</span> <span class='hs-varid'>generalMerge</span> <span class='hs-varid'>p</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-varid'>ys</span>
<a name="line-26"></a>
<a name="line-27"></a><span class='hs-comment'>-- gamma is now called balancedFold</span>
<a name="line-28"></a>
<a name="line-29"></a><a name="balancedFold"></a><span class='hs-definition'>balancedFold</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-30"></a><span class='hs-definition'>balancedFold</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>error</span> <span class='hs-str'>"can't reduce an empty list using balancedFold"</span>
<a name="line-31"></a><span class='hs-definition'>balancedFold</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>x</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span>
<a name="line-32"></a><span class='hs-definition'>balancedFold</span> <span class='hs-varid'>f</span> <span class='hs-varid'>l</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>balancedFold</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-varid'>balancedFold'</span> <span class='hs-varid'>f</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span>
<a name="line-33"></a>
<a name="line-34"></a><a name="balancedFold'"></a><span class='hs-definition'>balancedFold'</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-35"></a><span class='hs-definition'>balancedFold'</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-conop'>:</span> <span class='hs-varid'>balancedFold'</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xs</span>
<a name="line-36"></a><span class='hs-definition'>balancedFold'</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>xs</span>
<a name="line-37"></a>
<a name="line-38"></a><a name="generalNaturalMergeSort"></a><span class='hs-definition'>generalNaturalMergeSort</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-39"></a><span class='hs-definition'>generalNaturalMergeSort</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-40"></a><span class='hs-definition'>generalNaturalMergeSort</span> <span class='hs-varid'>p</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>balancedFold</span> <span class='hs-layout'>(</span><span class='hs-varid'>generalMerge</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-varid'>group</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
<a name="line-41"></a>
<a name="line-42"></a><span class='hs-cpp'>#if NOT_USED</span>
<a name="line-43"></a><a name="generalMergeSort"></a><span class='hs-definition'>generalMergeSort</span> <span class='hs-varid'>p</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-44"></a><span class='hs-definition'>generalMergeSort</span> <span class='hs-varid'>p</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>balancedFold</span> <span class='hs-layout'>(</span><span class='hs-varid'>generalMerge</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-varid'>map</span> <span class='hs-layout'>(</span><span class='hs-conop'>:</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
<a name="line-45"></a>
<a name="line-46"></a><a name="mergeSort"></a><span class='hs-definition'>mergeSort</span><span class='hs-layout'>,</span> <span class='hs-varid'>naturalMergeSort</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Ord</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-47"></a>
<a name="line-48"></a><span class='hs-definition'>mergeSort</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>generalMergeSort</span> <span class='hs-layout'>(</span><span class='hs-varop'><=</span><span class='hs-layout'>)</span>
<a name="line-49"></a><a name="naturalMergeSort"></a><span class='hs-definition'>naturalMergeSort</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>generalNaturalMergeSort</span> <span class='hs-layout'>(</span><span class='hs-varop'><=</span><span class='hs-layout'>)</span>
<a name="line-50"></a>
<a name="line-51"></a><a name="mergeSortLe"></a><span class='hs-definition'>mergeSortLe</span> <span class='hs-varid'>le</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>generalMergeSort</span> <span class='hs-varid'>le</span>
<a name="line-52"></a><span class='hs-cpp'>#endif</span>
<a name="line-53"></a>
<a name="line-54"></a><a name="sortLe"></a><span class='hs-definition'>sortLe</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>a</span><span class='hs-keyglyph'>-></span><span class='hs-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-55"></a><span class='hs-definition'>sortLe</span> <span class='hs-varid'>le</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>generalNaturalMergeSort</span> <span class='hs-varid'>le</span>
<a name="line-56"></a>
<a name="line-57"></a><a name="sortWith"></a><span class='hs-definition'>sortWith</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Ord</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=></span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-58"></a><span class='hs-definition'>sortWith</span> <span class='hs-varid'>get_key</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>sortLe</span> <span class='hs-varid'>le</span> <span class='hs-varid'>xs</span>
<a name="line-59"></a> <span class='hs-keyword'>where</span>
<a name="line-60"></a> <span class='hs-varid'>x</span> <span class='hs-varop'>`le`</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>get_key</span> <span class='hs-varid'>x</span> <span class='hs-varop'><</span> <span class='hs-varid'>get_key</span> <span class='hs-varid'>y</span>
<a name="line-61"></a>
<a name="line-62"></a><a name="on"></a><span class='hs-definition'>on</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>c</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>c</span>
<a name="line-63"></a><span class='hs-definition'>on</span> <span class='hs-varid'>cmp</span> <span class='hs-varid'>sel</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>\</span><span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>sel</span> <span class='hs-varid'>x</span> <span class='hs-varop'>`cmp`</span> <span class='hs-varid'>sel</span> <span class='hs-varid'>y</span>
<a name="line-64"></a>
</pre>\end{code}
%************************************************************************
%* *
\subsection[Utils-transitive-closure]{Transitive closure}
%* *
%************************************************************************
This algorithm for transitive closure is straightforward, albeit quadratic.
\begin{code}
<pre><a name="line-1"></a><a name="transitiveClosure"></a><span class='hs-definition'>transitiveClosure</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- Successor function</span>
<a name="line-2"></a> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- Equality predicate</span>
<a name="line-3"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-4"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- The transitive closure</span>
<a name="line-5"></a>
<a name="line-6"></a><span class='hs-definition'>transitiveClosure</span> <span class='hs-varid'>succ</span> <span class='hs-varid'>eq</span> <span class='hs-varid'>xs</span>
<a name="line-7"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>xs</span>
<a name="line-8"></a> <span class='hs-keyword'>where</span>
<a name="line-9"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>done</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>done</span>
<a name="line-10"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>done</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>x</span> <span class='hs-varop'>`is_in`</span> <span class='hs-varid'>done</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-varid'>done</span> <span class='hs-varid'>xs</span>
<a name="line-11"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>done</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>succ</span> <span class='hs-varid'>x</span> <span class='hs-varop'>++</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
<a name="line-12"></a>
<a name="line-13"></a> <span class='hs-keyword'>_</span> <span class='hs-varop'>`is_in`</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-14"></a> <span class='hs-varid'>x</span> <span class='hs-varop'>`is_in`</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>eq</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-15"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <span class='hs-varop'>`is_in`</span> <span class='hs-varid'>ys</span>
</pre>\end{code}
%************************************************************************
%* *
\subsection[Utils-accum]{Accumulating}
%* *
%************************************************************************
A combination of foldl with zip. It works with equal length lists.
\begin{code}
<pre><a name="line-1"></a><a name="foldl2"></a><span class='hs-definition'>foldl2</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>acc</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>acc</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>acc</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>acc</span>
<a name="line-2"></a><span class='hs-definition'>foldl2</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>z</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>z</span>
<a name="line-3"></a><span class='hs-definition'>foldl2</span> <span class='hs-varid'>k</span> <span class='hs-varid'>z</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-conop'>:</span><span class='hs-keyword'>as</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-conop'>:</span><span class='hs-varid'>bs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldl2</span> <span class='hs-varid'>k</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span> <span class='hs-varid'>z</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyword'>as</span> <span class='hs-varid'>bs</span>
<a name="line-4"></a><span class='hs-definition'>foldl2</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>panic</span> <span class='hs-str'>"Util: foldl2"</span>
<a name="line-5"></a>
<a name="line-6"></a><a name="all2"></a><span class='hs-definition'>all2</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-7"></a><span class='hs-comment'>-- True if the lists are the same length, and</span>
<a name="line-8"></a><span class='hs-comment'>-- all corresponding elements satisfy the predicate</span>
<a name="line-9"></a><span class='hs-definition'>all2</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-10"></a><span class='hs-definition'>all2</span> <span class='hs-varid'>p</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>p</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>all2</span> <span class='hs-varid'>p</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
<a name="line-11"></a><span class='hs-definition'>all2</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
</pre>\end{code}
Count the number of times a predicate is true
\begin{code}
<pre><a name="line-1"></a><a name="count"></a><span class='hs-definition'>count</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Int</span>
<a name="line-2"></a><span class='hs-definition'>count</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>0</span>
<a name="line-3"></a><span class='hs-definition'>count</span> <span class='hs-varid'>p</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>p</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>1</span> <span class='hs-varop'>+</span> <span class='hs-varid'>count</span> <span class='hs-varid'>p</span> <span class='hs-varid'>xs</span>
<a name="line-4"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>count</span> <span class='hs-varid'>p</span> <span class='hs-varid'>xs</span>
</pre>\end{code}
@splitAt@, @take@, and @drop@ but with length of another
list giving the break-off point:
\begin{code}
<pre><a name="line-1"></a><a name="takeList"></a><span class='hs-definition'>takeList</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-2"></a><span class='hs-definition'>takeList</span> <span class='hs-conid'>[]</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-3"></a><span class='hs-definition'>takeList</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-varid'>ls</span> <span class='hs-keyglyph'>=</span>
<a name="line-4"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>ls</span> <span class='hs-keyword'>of</span>
<a name="line-5"></a> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>[]</span>
<a name="line-6"></a> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>y</span> <span class='hs-conop'>:</span> <span class='hs-varid'>takeList</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
<a name="line-7"></a>
<a name="line-8"></a><a name="dropList"></a><span class='hs-definition'>dropList</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-9"></a><span class='hs-definition'>dropList</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>xs</span>
<a name="line-10"></a><span class='hs-definition'>dropList</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>xs</span><span class='hs-keyglyph'>@</span><span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>xs</span>
<a name="line-11"></a><span class='hs-definition'>dropList</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>dropList</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
<a name="line-12"></a>
<a name="line-13"></a>
<a name="line-14"></a><a name="splitAtList"></a><span class='hs-definition'>splitAtList</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span>
<a name="line-15"></a><span class='hs-definition'>splitAtList</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-conid'>[]</span><span class='hs-layout'>,</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
<a name="line-16"></a><span class='hs-definition'>splitAtList</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>xs</span><span class='hs-keyglyph'>@</span><span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>xs</span><span class='hs-layout'>,</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
<a name="line-17"></a><span class='hs-definition'>splitAtList</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys'</span><span class='hs-layout'>,</span> <span class='hs-varid'>ys''</span><span class='hs-layout'>)</span>
<a name="line-18"></a> <span class='hs-keyword'>where</span>
<a name="line-19"></a> <span class='hs-layout'>(</span><span class='hs-varid'>ys'</span><span class='hs-layout'>,</span> <span class='hs-varid'>ys''</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>splitAtList</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
<a name="line-20"></a>
<a name="line-21"></a><a name="dropTail"></a><span class='hs-comment'>-- drop from the end of a list</span>
<a name="line-22"></a><span class='hs-definition'>dropTail</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-23"></a><span class='hs-definition'>dropTail</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>reverse</span> <span class='hs-varop'>.</span> <span class='hs-varid'>drop</span> <span class='hs-varid'>n</span> <span class='hs-varop'>.</span> <span class='hs-varid'>reverse</span>
<a name="line-24"></a>
<a name="line-25"></a><a name="snocView"></a><span class='hs-definition'>snocView</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-26"></a> <span class='hs-comment'>-- Split off the last element</span>
<a name="line-27"></a><span class='hs-definition'>snocView</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Nothing</span>
<a name="line-28"></a><span class='hs-definition'>snocView</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>xs</span>
<a name="line-29"></a> <span class='hs-keyword'>where</span>
<a name="line-30"></a> <span class='hs-comment'>-- Invariant: second arg is non-empty</span>
<a name="line-31"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>acc</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>x</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>reverse</span> <span class='hs-varid'>acc</span><span class='hs-layout'>,</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span>
<a name="line-32"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>acc</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>acc</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
<a name="line-33"></a> <span class='hs-varid'>go</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>panic</span> <span class='hs-str'>"Util: snocView"</span>
<a name="line-34"></a>
<a name="line-35"></a><a name="split"></a><span class='hs-definition'>split</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Char</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>String</span><span class='hs-keyglyph'>]</span>
<a name="line-36"></a><span class='hs-definition'>split</span> <span class='hs-varid'>c</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>rest</span> <span class='hs-keyword'>of</span>
<a name="line-37"></a> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>chunk</span><span class='hs-keyglyph'>]</span>
<a name="line-38"></a> <span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>rest</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>chunk</span> <span class='hs-conop'>:</span> <span class='hs-varid'>split</span> <span class='hs-varid'>c</span> <span class='hs-varid'>rest</span>
<a name="line-39"></a> <span class='hs-keyword'>where</span> <span class='hs-layout'>(</span><span class='hs-varid'>chunk</span><span class='hs-layout'>,</span> <span class='hs-varid'>rest</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>break</span> <span class='hs-layout'>(</span><span class='hs-varop'>==</span><span class='hs-varid'>c</span><span class='hs-layout'>)</span> <span class='hs-varid'>s</span>
</pre>\end{code}
%************************************************************************
%* *
\subsection[Utils-comparison]{Comparisons}
%* *
%************************************************************************
\begin{code}
<pre><a name="line-1"></a><a name="isEqual"></a><span class='hs-definition'>isEqual</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Ordering</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-2"></a><span class='hs-comment'>-- Often used in (isEqual (a `compare` b))</span>
<a name="line-3"></a><span class='hs-definition'>isEqual</span> <span class='hs-conid'>GT</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-4"></a><span class='hs-definition'>isEqual</span> <span class='hs-conid'>EQ</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-5"></a><span class='hs-definition'>isEqual</span> <span class='hs-conid'>LT</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-6"></a>
<a name="line-7"></a><a name="thenCmp"></a><span class='hs-definition'>thenCmp</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Ordering</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Ordering</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Ordering</span>
<a name="line-8"></a><span class='hs-comment'>{-# INLINE thenCmp #-}</span>
<a name="line-9"></a><span class='hs-definition'>thenCmp</span> <span class='hs-conid'>EQ</span> <span class='hs-varid'>ordering</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ordering</span>
<a name="line-10"></a><span class='hs-definition'>thenCmp</span> <span class='hs-varid'>ordering</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ordering</span>
<a name="line-11"></a>
<a name="line-12"></a><a name="eqListBy"></a><span class='hs-definition'>eqListBy</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>-></span><span class='hs-varid'>a</span><span class='hs-keyglyph'>-></span><span class='hs-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-13"></a><span class='hs-definition'>eqListBy</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-14"></a><span class='hs-definition'>eqListBy</span> <span class='hs-varid'>eq</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>eq</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>eqListBy</span> <span class='hs-varid'>eq</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
<a name="line-15"></a><span class='hs-definition'>eqListBy</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-16"></a>
<a name="line-17"></a><a name="cmpList"></a><span class='hs-definition'>cmpList</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Ordering</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Ordering</span>
<a name="line-18"></a> <span class='hs-comment'>-- `cmpList' uses a user-specified comparer</span>
<a name="line-19"></a>
<a name="line-20"></a><span class='hs-definition'>cmpList</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>EQ</span>
<a name="line-21"></a><span class='hs-definition'>cmpList</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>LT</span>
<a name="line-22"></a><span class='hs-definition'>cmpList</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>GT</span>
<a name="line-23"></a><span class='hs-definition'>cmpList</span> <span class='hs-varid'>cmp</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-conop'>:</span><span class='hs-keyword'>as</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span><span class='hs-conop'>:</span><span class='hs-varid'>bs</span><span class='hs-layout'>)</span>
<a name="line-24"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>cmp</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-keyword'>of</span> <span class='hs-layout'>{</span> <span class='hs-conid'>EQ</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>cmpList</span> <span class='hs-varid'>cmp</span> <span class='hs-keyword'>as</span> <span class='hs-varid'>bs</span><span class='hs-layout'>;</span> <span class='hs-varid'>xxx</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>xxx</span> <span class='hs-layout'>}</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="removeSpaces"></a><span class='hs-definition'>removeSpaces</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>String</span>
<a name="line-2"></a><span class='hs-definition'>removeSpaces</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>reverse</span> <span class='hs-varop'>.</span> <span class='hs-varid'>dropWhile</span> <span class='hs-varid'>isSpace</span> <span class='hs-varop'>.</span> <span class='hs-varid'>reverse</span> <span class='hs-varop'>.</span> <span class='hs-varid'>dropWhile</span> <span class='hs-varid'>isSpace</span>
</pre>\end{code}
%************************************************************************
%* *
\subsection[Utils-pairs]{Pairs}
%* *
%************************************************************************
\begin{code}
<pre><a name="line-1"></a><a name="unzipWith"></a><span class='hs-definition'>unzipWith</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>c</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>c</span><span class='hs-keyglyph'>]</span>
<a name="line-2"></a><span class='hs-definition'>unzipWith</span> <span class='hs-varid'>f</span> <span class='hs-varid'>pairs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>map</span> <span class='hs-layout'>(</span> <span class='hs-keyglyph'>\</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>f</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-layout'>)</span> <span class='hs-varid'>pairs</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="seqList"></a><span class='hs-definition'>seqList</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span>
<a name="line-2"></a><span class='hs-definition'>seqList</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>b</span>
<a name="line-3"></a><span class='hs-definition'>seqList</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <span class='hs-varop'>`seq`</span> <span class='hs-varid'>seqList</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>b</span>
</pre>\end{code}
Global variables:
\begin{code}
<pre><a name="line-1"></a><a name="global"></a><span class='hs-definition'>global</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IORef</span> <span class='hs-varid'>a</span>
<a name="line-2"></a><span class='hs-definition'>global</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>unsafePerformIO</span> <span class='hs-layout'>(</span><span class='hs-varid'>newIORef</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="consIORef"></a><span class='hs-definition'>consIORef</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>IORef</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IO</span> <span class='hs-conid'>()</span>
<a name="line-2"></a><span class='hs-definition'>consIORef</span> <span class='hs-varid'>var</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-3"></a> <span class='hs-varid'>atomicModifyIORef</span> <span class='hs-varid'>var</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>xs</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>,</span><span class='hs-conid'>()</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="globalMVar"></a><span class='hs-definition'>globalMVar</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>MVar</span> <span class='hs-varid'>a</span>
<a name="line-2"></a><span class='hs-definition'>globalMVar</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>unsafePerformIO</span> <span class='hs-layout'>(</span><span class='hs-varid'>newMVar</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-3"></a>
<a name="line-4"></a><a name="globalEmptyMVar"></a><span class='hs-definition'>globalEmptyMVar</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>MVar</span> <span class='hs-varid'>a</span>
<a name="line-5"></a><span class='hs-definition'>globalEmptyMVar</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>unsafePerformIO</span> <span class='hs-varid'>newEmptyMVar</span>
</pre>\end{code}
Module names:
\begin{code}
<pre><a name="line-1"></a><a name="looksLikeModuleName"></a><span class='hs-definition'>looksLikeModuleName</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-2"></a><span class='hs-definition'>looksLikeModuleName</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-3"></a><span class='hs-definition'>looksLikeModuleName</span> <span class='hs-layout'>(</span><span class='hs-varid'>c</span><span class='hs-conop'>:</span><span class='hs-varid'>cs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>isUpper</span> <span class='hs-varid'>c</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>go</span> <span class='hs-varid'>cs</span>
<a name="line-4"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>go</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-5"></a> <span class='hs-varid'>go</span> <span class='hs-layout'>(</span><span class='hs-chr'>'.'</span><span class='hs-conop'>:</span><span class='hs-varid'>cs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>looksLikeModuleName</span> <span class='hs-varid'>cs</span>
<a name="line-6"></a> <span class='hs-varid'>go</span> <span class='hs-layout'>(</span><span class='hs-varid'>c</span><span class='hs-conop'>:</span><span class='hs-varid'>cs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>isAlphaNum</span> <span class='hs-varid'>c</span> <span class='hs-varop'>||</span> <span class='hs-varid'>c</span> <span class='hs-varop'>==</span> <span class='hs-chr'>'_'</span> <span class='hs-varop'>||</span> <span class='hs-varid'>c</span> <span class='hs-varop'>==</span> <span class='hs-chr'>'\''</span><span class='hs-layout'>)</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>go</span> <span class='hs-varid'>cs</span>
</pre>\end{code}
Akin to @Prelude.words@, but acts like the Bourne shell, treating
quoted strings as Haskell Strings, and also parses Haskell [String]
syntax.
\begin{code}
<pre><a name="line-1"></a><a name="getCmd"></a><span class='hs-definition'>getCmd</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Either</span> <span class='hs-conid'>String</span> <span class='hs-comment'>-- Error</span>
<a name="line-2"></a> <span class='hs-layout'>(</span><span class='hs-conid'>String</span><span class='hs-layout'>,</span> <span class='hs-conid'>String</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- (Cmd, Rest)</span>
<a name="line-3"></a><span class='hs-definition'>getCmd</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>break</span> <span class='hs-varid'>isSpace</span> <span class='hs-varop'>$</span> <span class='hs-varid'>dropWhile</span> <span class='hs-varid'>isSpace</span> <span class='hs-varid'>s</span> <span class='hs-keyword'>of</span>
<a name="line-4"></a> <span class='hs-layout'>(</span><span class='hs-conid'>[]</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Left</span> <span class='hs-layout'>(</span><span class='hs-str'>"Couldn't find command in "</span> <span class='hs-varop'>++</span> <span class='hs-varid'>show</span> <span class='hs-varid'>s</span><span class='hs-layout'>)</span>
<a name="line-5"></a> <span class='hs-varid'>res</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Right</span> <span class='hs-varid'>res</span>
<a name="line-6"></a>
<a name="line-7"></a><a name="toCmdArgs"></a><span class='hs-definition'>toCmdArgs</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Either</span> <span class='hs-conid'>String</span> <span class='hs-comment'>-- Error</span>
<a name="line-8"></a> <span class='hs-layout'>(</span><span class='hs-conid'>String</span><span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>String</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- (Cmd, Args)</span>
<a name="line-9"></a><span class='hs-definition'>toCmdArgs</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>getCmd</span> <span class='hs-varid'>s</span> <span class='hs-keyword'>of</span>
<a name="line-10"></a> <span class='hs-conid'>Left</span> <span class='hs-varid'>err</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Left</span> <span class='hs-varid'>err</span>
<a name="line-11"></a> <span class='hs-conid'>Right</span> <span class='hs-layout'>(</span><span class='hs-varid'>cmd</span><span class='hs-layout'>,</span> <span class='hs-varid'>s'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>case</span> <span class='hs-varid'>toArgs</span> <span class='hs-varid'>s'</span> <span class='hs-keyword'>of</span>
<a name="line-12"></a> <span class='hs-conid'>Left</span> <span class='hs-varid'>err</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Left</span> <span class='hs-varid'>err</span>
<a name="line-13"></a> <span class='hs-conid'>Right</span> <span class='hs-varid'>args</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Right</span> <span class='hs-layout'>(</span><span class='hs-varid'>cmd</span><span class='hs-layout'>,</span> <span class='hs-varid'>args</span><span class='hs-layout'>)</span>
<a name="line-14"></a>
<a name="line-15"></a><a name="toArgs"></a><span class='hs-definition'>toArgs</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Either</span> <span class='hs-conid'>String</span> <span class='hs-comment'>-- Error</span>
<a name="line-16"></a> <span class='hs-keyglyph'>[</span><span class='hs-conid'>String</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- Args</span>
<a name="line-17"></a><span class='hs-definition'>toArgs</span> <span class='hs-varid'>str</span>
<a name="line-18"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>dropWhile</span> <span class='hs-varid'>isSpace</span> <span class='hs-varid'>str</span> <span class='hs-keyword'>of</span>
<a name="line-19"></a> <span class='hs-varid'>s</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-chr'>'['</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>case</span> <span class='hs-varid'>reads</span> <span class='hs-varid'>s</span> <span class='hs-keyword'>of</span>
<a name="line-20"></a> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>args</span><span class='hs-layout'>,</span> <span class='hs-varid'>spaces</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-21"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>all</span> <span class='hs-varid'>isSpace</span> <span class='hs-varid'>spaces</span> <span class='hs-keyglyph'>-></span>
<a name="line-22"></a> <span class='hs-conid'>Right</span> <span class='hs-varid'>args</span>
<a name="line-23"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span>
<a name="line-24"></a> <span class='hs-conid'>Left</span> <span class='hs-layout'>(</span><span class='hs-str'>"Couldn't read "</span> <span class='hs-varop'>++</span> <span class='hs-varid'>show</span> <span class='hs-varid'>str</span> <span class='hs-varop'>++</span> <span class='hs-str'>"as [String]"</span><span class='hs-layout'>)</span>
<a name="line-25"></a> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>toArgs'</span> <span class='hs-varid'>s</span>
<a name="line-26"></a> <span class='hs-keyword'>where</span>
<a name="line-27"></a> <span class='hs-varid'>toArgs'</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>dropWhile</span> <span class='hs-varid'>isSpace</span> <span class='hs-varid'>s</span> <span class='hs-keyword'>of</span>
<a name="line-28"></a> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Right</span> <span class='hs-conid'>[]</span>
<a name="line-29"></a> <span class='hs-layout'>(</span><span class='hs-chr'>'"'</span> <span class='hs-conop'>:</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>case</span> <span class='hs-varid'>reads</span> <span class='hs-varid'>s</span> <span class='hs-keyword'>of</span>
<a name="line-30"></a> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>arg</span><span class='hs-layout'>,</span> <span class='hs-varid'>rest</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-31"></a> <span class='hs-comment'>-- rest must either be [] or start with a space</span>
<a name="line-32"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>all</span> <span class='hs-varid'>isSpace</span> <span class='hs-layout'>(</span><span class='hs-varid'>take</span> <span class='hs-num'>1</span> <span class='hs-varid'>rest</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span>
<a name="line-33"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>toArgs'</span> <span class='hs-varid'>rest</span> <span class='hs-keyword'>of</span>
<a name="line-34"></a> <span class='hs-conid'>Left</span> <span class='hs-varid'>err</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Left</span> <span class='hs-varid'>err</span>
<a name="line-35"></a> <span class='hs-conid'>Right</span> <span class='hs-varid'>args</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Right</span> <span class='hs-layout'>(</span><span class='hs-varid'>arg</span> <span class='hs-conop'>:</span> <span class='hs-varid'>args</span><span class='hs-layout'>)</span>
<a name="line-36"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span>
<a name="line-37"></a> <span class='hs-conid'>Left</span> <span class='hs-layout'>(</span><span class='hs-str'>"Couldn't read "</span> <span class='hs-varop'>++</span> <span class='hs-varid'>show</span> <span class='hs-varid'>s</span> <span class='hs-varop'>++</span> <span class='hs-str'>"as String"</span><span class='hs-layout'>)</span>
<a name="line-38"></a> <span class='hs-varid'>s'</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>case</span> <span class='hs-varid'>break</span> <span class='hs-varid'>isSpace</span> <span class='hs-varid'>s'</span> <span class='hs-keyword'>of</span>
<a name="line-39"></a> <span class='hs-layout'>(</span><span class='hs-varid'>arg</span><span class='hs-layout'>,</span> <span class='hs-varid'>s''</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>case</span> <span class='hs-varid'>toArgs'</span> <span class='hs-varid'>s''</span> <span class='hs-keyword'>of</span>
<a name="line-40"></a> <span class='hs-conid'>Left</span> <span class='hs-varid'>err</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Left</span> <span class='hs-varid'>err</span>
<a name="line-41"></a> <span class='hs-conid'>Right</span> <span class='hs-varid'>args</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Right</span> <span class='hs-layout'>(</span><span class='hs-varid'>arg</span> <span class='hs-conop'>:</span> <span class='hs-varid'>args</span><span class='hs-layout'>)</span>
</pre>\end{code}
-- -----------------------------------------------------------------------------
-- Floats
\begin{code}
<pre><a name="line-1"></a><a name="readRational__"></a><span class='hs-definition'>readRational__</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>ReadS</span> <span class='hs-conid'>Rational</span> <span class='hs-comment'>-- NB: doesn't handle leading "-"</span>
<a name="line-2"></a><span class='hs-definition'>readRational__</span> <span class='hs-varid'>r</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-3"></a> <span class='hs-layout'>(</span><span class='hs-varid'>n</span><span class='hs-layout'>,</span><span class='hs-varid'>d</span><span class='hs-layout'>,</span><span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>readFix</span> <span class='hs-varid'>r</span>
<a name="line-4"></a> <span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>readExp</span> <span class='hs-varid'>s</span>
<a name="line-5"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>n</span><span class='hs-varop'>%</span><span class='hs-num'>1</span><span class='hs-layout'>)</span><span class='hs-varop'>*</span><span class='hs-num'>10</span><span class='hs-varop'>^^</span><span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-comment'>-</span><span class='hs-varid'>d</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-6"></a> <span class='hs-keyword'>where</span>
<a name="line-7"></a> <span class='hs-varid'>readFix</span> <span class='hs-varid'>r</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-8"></a> <span class='hs-layout'>(</span><span class='hs-varid'>ds</span><span class='hs-layout'>,</span><span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>lexDecDigits</span> <span class='hs-varid'>r</span>
<a name="line-9"></a> <span class='hs-layout'>(</span><span class='hs-varid'>ds'</span><span class='hs-layout'>,</span><span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>lexDotDigits</span> <span class='hs-varid'>s</span>
<a name="line-10"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>read</span> <span class='hs-layout'>(</span><span class='hs-varid'>ds</span><span class='hs-varop'>++</span><span class='hs-varid'>ds'</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>length</span> <span class='hs-varid'>ds'</span><span class='hs-layout'>,</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-11"></a>
<a name="line-12"></a> <span class='hs-varid'>readExp</span> <span class='hs-layout'>(</span><span class='hs-varid'>e</span><span class='hs-conop'>:</span><span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>e</span> <span class='hs-varop'>`elem`</span> <span class='hs-str'>"eE"</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>readExp'</span> <span class='hs-varid'>s</span>
<a name="line-13"></a> <span class='hs-varid'>readExp</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-num'>0</span><span class='hs-layout'>,</span><span class='hs-varid'>s</span><span class='hs-layout'>)</span>
<a name="line-14"></a>
<a name="line-15"></a> <span class='hs-varid'>readExp'</span> <span class='hs-layout'>(</span><span class='hs-chr'>'+'</span><span class='hs-conop'>:</span><span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>readDec</span> <span class='hs-varid'>s</span>
<a name="line-16"></a> <span class='hs-varid'>readExp'</span> <span class='hs-layout'>(</span><span class='hs-chr'>'-'</span><span class='hs-conop'>:</span><span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>readDec</span> <span class='hs-varid'>s</span>
<a name="line-17"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-comment'>-</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-18"></a> <span class='hs-varid'>readExp'</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>readDec</span> <span class='hs-varid'>s</span>
<a name="line-19"></a>
<a name="line-20"></a> <span class='hs-varid'>readDec</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-21"></a> <span class='hs-layout'>(</span><span class='hs-varid'>ds</span><span class='hs-layout'>,</span><span class='hs-varid'>r</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>nonnull</span> <span class='hs-varid'>isDigit</span> <span class='hs-varid'>s</span>
<a name="line-22"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>foldl1</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>n</span> <span class='hs-varid'>d</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>n</span> <span class='hs-varop'>*</span> <span class='hs-num'>10</span> <span class='hs-varop'>+</span> <span class='hs-varid'>d</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>ord</span> <span class='hs-varid'>d</span> <span class='hs-comment'>-</span> <span class='hs-varid'>ord</span> <span class='hs-chr'>'0'</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>d</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>ds</span> <span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span>
<a name="line-23"></a> <span class='hs-varid'>r</span><span class='hs-layout'>)</span>
<a name="line-24"></a>
<a name="line-25"></a> <span class='hs-varid'>lexDecDigits</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>nonnull</span> <span class='hs-varid'>isDigit</span>
<a name="line-26"></a>
<a name="line-27"></a> <span class='hs-varid'>lexDotDigits</span> <span class='hs-layout'>(</span><span class='hs-chr'>'.'</span><span class='hs-conop'>:</span><span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>span</span> <span class='hs-varid'>isDigit</span> <span class='hs-varid'>s</span><span class='hs-layout'>)</span>
<a name="line-28"></a> <span class='hs-varid'>lexDotDigits</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-str'>""</span><span class='hs-layout'>,</span><span class='hs-varid'>s</span><span class='hs-layout'>)</span>
<a name="line-29"></a>
<a name="line-30"></a> <span class='hs-varid'>nonnull</span> <span class='hs-varid'>p</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span> <span class='hs-layout'>(</span><span class='hs-varid'>cs</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span><span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>span</span> <span class='hs-varid'>p</span> <span class='hs-varid'>s</span><span class='hs-layout'>)</span>
<a name="line-31"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>cs</span><span class='hs-layout'>,</span><span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-32"></a>
<a name="line-33"></a><a name="readRational"></a><span class='hs-definition'>readRational</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Rational</span> <span class='hs-comment'>-- NB: *does* handle a leading "-"</span>
<a name="line-34"></a><span class='hs-definition'>readRational</span> <span class='hs-varid'>top_s</span>
<a name="line-35"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>top_s</span> <span class='hs-keyword'>of</span>
<a name="line-36"></a> <span class='hs-chr'>'-'</span> <span class='hs-conop'>:</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>-></span> <span class='hs-comment'>-</span> <span class='hs-layout'>(</span><span class='hs-varid'>read_me</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
<a name="line-37"></a> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>read_me</span> <span class='hs-varid'>xs</span>
<a name="line-38"></a> <span class='hs-keyword'>where</span>
<a name="line-39"></a> <span class='hs-varid'>read_me</span> <span class='hs-varid'>s</span>
<a name="line-40"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-layout'>(</span><span class='hs-keyword'>do</span> <span class='hs-layout'>{</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-layout'>,</span><span class='hs-str'>""</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>readRational__</span> <span class='hs-varid'>s</span> <span class='hs-layout'>;</span> <span class='hs-varid'>return</span> <span class='hs-varid'>x</span> <span class='hs-layout'>}</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span>
<a name="line-41"></a> <span class='hs-keyglyph'>[</span><span class='hs-varid'>x</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>x</span>
<a name="line-42"></a> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>error</span> <span class='hs-layout'>(</span><span class='hs-str'>"readRational: no parse:"</span> <span class='hs-varop'>++</span> <span class='hs-varid'>top_s</span><span class='hs-layout'>)</span>
<a name="line-43"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>error</span> <span class='hs-layout'>(</span><span class='hs-str'>"readRational: ambiguous parse:"</span> <span class='hs-varop'>++</span> <span class='hs-varid'>top_s</span><span class='hs-layout'>)</span>
<a name="line-44"></a>
<a name="line-45"></a>
<a name="line-46"></a><span class='hs-comment'>-----------------------------------------------------------------------------</span>
<a name="line-47"></a><span class='hs-comment'>-- Create a hierarchy of directories</span>
<a name="line-48"></a>
<a name="line-49"></a><a name="createDirectoryHierarchy"></a><span class='hs-definition'>createDirectoryHierarchy</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>FilePath</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IO</span> <span class='hs-conid'>()</span>
<a name="line-50"></a><span class='hs-definition'>createDirectoryHierarchy</span> <span class='hs-varid'>dir</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>isDrive</span> <span class='hs-varid'>dir</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-conid'>()</span> <span class='hs-comment'>-- XXX Hack</span>
<a name="line-51"></a><span class='hs-definition'>createDirectoryHierarchy</span> <span class='hs-varid'>dir</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-52"></a> <span class='hs-varid'>b</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>doesDirectoryExist</span> <span class='hs-varid'>dir</span>
<a name="line-53"></a> <span class='hs-varid'>unless</span> <span class='hs-varid'>b</span> <span class='hs-varop'>$</span> <span class='hs-keyword'>do</span> <span class='hs-varid'>createDirectoryHierarchy</span> <span class='hs-layout'>(</span><span class='hs-varid'>takeDirectory</span> <span class='hs-varid'>dir</span><span class='hs-layout'>)</span>
<a name="line-54"></a> <span class='hs-varid'>createDirectory</span> <span class='hs-varid'>dir</span>
<a name="line-55"></a>
<a name="line-56"></a><a name="doesDirNameExist"></a><span class='hs-comment'>-----------------------------------------------------------------------------</span>
<a name="line-57"></a><span class='hs-comment'>-- Verify that the 'dirname' portion of a FilePath exists.</span>
<a name="line-58"></a><span class='hs-comment'>--</span>
<a name="line-59"></a><span class='hs-definition'>doesDirNameExist</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>FilePath</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IO</span> <span class='hs-conid'>Bool</span>
<a name="line-60"></a><span class='hs-definition'>doesDirNameExist</span> <span class='hs-varid'>fpath</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>takeDirectory</span> <span class='hs-varid'>fpath</span> <span class='hs-keyword'>of</span>
<a name="line-61"></a> <span class='hs-str'>""</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>return</span> <span class='hs-conid'>True</span> <span class='hs-comment'>-- XXX Hack</span>
<a name="line-62"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>doesDirectoryExist</span> <span class='hs-layout'>(</span><span class='hs-varid'>takeDirectory</span> <span class='hs-varid'>fpath</span><span class='hs-layout'>)</span>
<a name="line-63"></a>
<a name="line-64"></a><span class='hs-comment'>-- --------------------------------------------------------------</span>
<a name="line-65"></a><span class='hs-comment'>-- check existence & modification time at the same time</span>
<a name="line-66"></a>
<a name="line-67"></a><a name="modificationTimeIfExists"></a><span class='hs-definition'>modificationTimeIfExists</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>FilePath</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IO</span> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-conid'>ClockTime</span><span class='hs-layout'>)</span>
<a name="line-68"></a><span class='hs-definition'>modificationTimeIfExists</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-69"></a> <span class='hs-layout'>(</span><span class='hs-keyword'>do</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getModificationTime</span> <span class='hs-varid'>f</span><span class='hs-layout'>;</span> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-70"></a> <span class='hs-varop'>`</span><span class='hs-conid'>IO</span><span class='hs-varop'>.</span><span class='hs-varid'>catch</span><span class='hs-varop'>`</span> <span class='hs-keyglyph'>\</span><span class='hs-varid'>e</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>if</span> <span class='hs-varid'>isDoesNotExistError</span> <span class='hs-varid'>e</span>
<a name="line-71"></a> <span class='hs-keyword'>then</span> <span class='hs-varid'>return</span> <span class='hs-conid'>Nothing</span>
<a name="line-72"></a> <span class='hs-keyword'>else</span> <span class='hs-varid'>ioError</span> <span class='hs-varid'>e</span>
<a name="line-73"></a>
<a name="line-74"></a><a name="splitLongestPrefix"></a><span class='hs-comment'>-- split a string at the last character where 'pred' is True,</span>
<a name="line-75"></a><span class='hs-comment'>-- returning a pair of strings. The first component holds the string</span>
<a name="line-76"></a><span class='hs-comment'>-- up (but not including) the last character for which 'pred' returned</span>
<a name="line-77"></a><span class='hs-comment'>-- True, the second whatever comes after (but also not including the</span>
<a name="line-78"></a><span class='hs-comment'>-- last character).</span>
<a name="line-79"></a><span class='hs-comment'>--</span>
<a name="line-80"></a><span class='hs-comment'>-- If 'pred' returns False for all characters in the string, the original</span>
<a name="line-81"></a><span class='hs-comment'>-- string is returned in the first component (and the second one is just</span>
<a name="line-82"></a><span class='hs-comment'>-- empty).</span>
<a name="line-83"></a><span class='hs-definition'>splitLongestPrefix</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>Char</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>String</span><span class='hs-layout'>,</span><span class='hs-conid'>String</span><span class='hs-layout'>)</span>
<a name="line-84"></a><span class='hs-definition'>splitLongestPrefix</span> <span class='hs-varid'>str</span> <span class='hs-varid'>pred</span>
<a name="line-85"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>null</span> <span class='hs-varid'>r_pre</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>str</span><span class='hs-layout'>,</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-86"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>reverse</span> <span class='hs-layout'>(</span><span class='hs-varid'>tail</span> <span class='hs-varid'>r_pre</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>reverse</span> <span class='hs-varid'>r_suf</span><span class='hs-layout'>)</span>
<a name="line-87"></a> <span class='hs-comment'>-- 'tail' drops the char satisfying 'pred'</span>
<a name="line-88"></a> <span class='hs-keyword'>where</span> <span class='hs-layout'>(</span><span class='hs-varid'>r_suf</span><span class='hs-layout'>,</span> <span class='hs-varid'>r_pre</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>break</span> <span class='hs-varid'>pred</span> <span class='hs-layout'>(</span><span class='hs-varid'>reverse</span> <span class='hs-varid'>str</span><span class='hs-layout'>)</span>
<a name="line-89"></a>
<a name="line-90"></a><a name="escapeSpaces"></a><span class='hs-definition'>escapeSpaces</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>String</span>
<a name="line-91"></a><span class='hs-definition'>escapeSpaces</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>c</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>if</span> <span class='hs-varid'>isSpace</span> <span class='hs-varid'>c</span> <span class='hs-keyword'>then</span> <span class='hs-chr'>'\\'</span><span class='hs-conop'>:</span><span class='hs-varid'>c</span><span class='hs-conop'>:</span><span class='hs-varid'>s</span> <span class='hs-keyword'>else</span> <span class='hs-varid'>c</span><span class='hs-conop'>:</span><span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-str'>""</span>
<a name="line-92"></a>
<a name="line-93"></a><a name="Suffix"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>Suffix</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>String</span>
<a name="line-94"></a>
<a name="line-95"></a><span class='hs-comment'>--------------------------------------------------------------</span>
<a name="line-96"></a><span class='hs-comment'>-- * Search path</span>
<a name="line-97"></a><span class='hs-comment'>--------------------------------------------------------------</span>
<a name="line-98"></a>
<a name="line-99"></a><a name="parseSearchPath"></a><span class='hs-comment'>-- | The function splits the given string to substrings</span>
<a name="line-100"></a><span class='hs-comment'>-- using the 'searchPathSeparator'.</span>
<a name="line-101"></a><span class='hs-definition'>parseSearchPath</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>FilePath</span><span class='hs-keyglyph'>]</span>
<a name="line-102"></a><span class='hs-definition'>parseSearchPath</span> <span class='hs-varid'>path</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>split</span> <span class='hs-varid'>path</span>
<a name="line-103"></a> <span class='hs-keyword'>where</span>
<a name="line-104"></a> <span class='hs-varid'>split</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>String</span><span class='hs-keyglyph'>]</span>
<a name="line-105"></a> <span class='hs-varid'>split</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span>
<a name="line-106"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>rest'</span> <span class='hs-keyword'>of</span>
<a name="line-107"></a> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>chunk</span><span class='hs-keyglyph'>]</span>
<a name="line-108"></a> <span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>rest</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>chunk</span> <span class='hs-conop'>:</span> <span class='hs-varid'>split</span> <span class='hs-varid'>rest</span>
<a name="line-109"></a> <span class='hs-keyword'>where</span>
<a name="line-110"></a> <span class='hs-varid'>chunk</span> <span class='hs-keyglyph'>=</span>
<a name="line-111"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>chunk'</span> <span class='hs-keyword'>of</span>
<a name="line-112"></a><span class='hs-cpp'>#ifdef mingw32_HOST_OS</span>
<a name="line-113"></a> <span class='hs-layout'>(</span><span class='hs-chr'>'\"'</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>last</span> <span class='hs-varid'>xs</span> <span class='hs-varop'>==</span> <span class='hs-chr'>'\"'</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>init</span> <span class='hs-varid'>xs</span>
<a name="line-114"></a><span class='hs-cpp'>#endif</span>
<a name="line-115"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>chunk'</span>
<a name="line-116"></a>
<a name="line-117"></a> <span class='hs-layout'>(</span><span class='hs-varid'>chunk'</span><span class='hs-layout'>,</span> <span class='hs-varid'>rest'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>break</span> <span class='hs-varid'>isSearchPathSeparator</span> <span class='hs-varid'>s</span>
<a name="line-118"></a>
<a name="line-119"></a><a name="Direction"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>Direction</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Forwards</span> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>Backwards</span>
<a name="line-120"></a>
<a name="line-121"></a><a name="reslash"></a><span class='hs-definition'>reslash</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Direction</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>FilePath</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>FilePath</span>
<a name="line-122"></a><span class='hs-definition'>reslash</span> <span class='hs-varid'>d</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span>
<a name="line-123"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-chr'>'/'</span> <span class='hs-conop'>:</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>slash</span> <span class='hs-conop'>:</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xs</span>
<a name="line-124"></a> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-chr'>'\\'</span> <span class='hs-conop'>:</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>slash</span> <span class='hs-conop'>:</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xs</span>
<a name="line-125"></a> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span> <span class='hs-conop'>:</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <span class='hs-conop'>:</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xs</span>
<a name="line-126"></a> <span class='hs-varid'>f</span> <span class='hs-str'>""</span> <span class='hs-keyglyph'>=</span> <span class='hs-str'>""</span>
<a name="line-127"></a> <span class='hs-varid'>slash</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>d</span> <span class='hs-keyword'>of</span>
<a name="line-128"></a> <span class='hs-conid'>Forwards</span> <span class='hs-keyglyph'>-></span> <span class='hs-chr'>'/'</span>
<a name="line-129"></a> <span class='hs-conid'>Backwards</span> <span class='hs-keyglyph'>-></span> <span class='hs-chr'>'\\'</span>
</pre>\end{code}
</body>
</html>
