<?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>Data/Foldable.hs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='hs-comment'>-----------------------------------------------------------------------------</span>
<a name="line-2"></a><span class='hs-comment'>-- |</span>
<a name="line-3"></a><span class='hs-comment'>-- Module : Data.Foldable</span>
<a name="line-4"></a><span class='hs-comment'>-- Copyright : Ross Paterson 2005</span>
<a name="line-5"></a><span class='hs-comment'>-- License : BSD-style (see the LICENSE file in the distribution)</span>
<a name="line-6"></a><span class='hs-comment'>--</span>
<a name="line-7"></a><span class='hs-comment'>-- Maintainer : libraries@haskell.org</span>
<a name="line-8"></a><span class='hs-comment'>-- Stability : experimental</span>
<a name="line-9"></a><span class='hs-comment'>-- Portability : portable</span>
<a name="line-10"></a><span class='hs-comment'>--</span>
<a name="line-11"></a><span class='hs-comment'>-- Class of data structures that can be folded to a summary value.</span>
<a name="line-12"></a><span class='hs-comment'>--</span>
<a name="line-13"></a><span class='hs-comment'>-- Many of these functions generalize "Prelude", "Control.Monad" and</span>
<a name="line-14"></a><span class='hs-comment'>-- "Data.List" functions of the same names from lists to any 'Foldable'</span>
<a name="line-15"></a><span class='hs-comment'>-- functor. To avoid ambiguity, either import those modules hiding</span>
<a name="line-16"></a><span class='hs-comment'>-- these names or qualify uses of these function names with an alias</span>
<a name="line-17"></a><span class='hs-comment'>-- for this module.</span>
<a name="line-18"></a>
<a name="line-19"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Foldable</span> <span class='hs-layout'>(</span>
<a name="line-20"></a> <span class='hs-comment'>-- * Folds</span>
<a name="line-21"></a> <span class='hs-conid'>Foldable</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span>
<a name="line-22"></a> <span class='hs-comment'>-- ** Special biased folds</span>
<a name="line-23"></a> <span class='hs-varid'>foldr'</span><span class='hs-layout'>,</span>
<a name="line-24"></a> <span class='hs-varid'>foldl'</span><span class='hs-layout'>,</span>
<a name="line-25"></a> <span class='hs-varid'>foldrM</span><span class='hs-layout'>,</span>
<a name="line-26"></a> <span class='hs-varid'>foldlM</span><span class='hs-layout'>,</span>
<a name="line-27"></a> <span class='hs-comment'>-- ** Folding actions</span>
<a name="line-28"></a> <span class='hs-comment'>-- *** Applicative actions</span>
<a name="line-29"></a> <span class='hs-varid'>traverse_</span><span class='hs-layout'>,</span>
<a name="line-30"></a> <span class='hs-varid'>for_</span><span class='hs-layout'>,</span>
<a name="line-31"></a> <span class='hs-varid'>sequenceA_</span><span class='hs-layout'>,</span>
<a name="line-32"></a> <span class='hs-varid'>asum</span><span class='hs-layout'>,</span>
<a name="line-33"></a> <span class='hs-comment'>-- *** Monadic actions</span>
<a name="line-34"></a> <span class='hs-varid'>mapM_</span><span class='hs-layout'>,</span>
<a name="line-35"></a> <span class='hs-varid'>forM_</span><span class='hs-layout'>,</span>
<a name="line-36"></a> <span class='hs-varid'>sequence_</span><span class='hs-layout'>,</span>
<a name="line-37"></a> <span class='hs-varid'>msum</span><span class='hs-layout'>,</span>
<a name="line-38"></a> <span class='hs-comment'>-- ** Specialized folds</span>
<a name="line-39"></a> <span class='hs-varid'>toList</span><span class='hs-layout'>,</span>
<a name="line-40"></a> <span class='hs-varid'>concat</span><span class='hs-layout'>,</span>
<a name="line-41"></a> <span class='hs-varid'>concatMap</span><span class='hs-layout'>,</span>
<a name="line-42"></a> <span class='hs-varid'>and</span><span class='hs-layout'>,</span>
<a name="line-43"></a> <span class='hs-varid'>or</span><span class='hs-layout'>,</span>
<a name="line-44"></a> <span class='hs-varid'>any</span><span class='hs-layout'>,</span>
<a name="line-45"></a> <span class='hs-varid'>all</span><span class='hs-layout'>,</span>
<a name="line-46"></a> <span class='hs-varid'>sum</span><span class='hs-layout'>,</span>
<a name="line-47"></a> <span class='hs-varid'>product</span><span class='hs-layout'>,</span>
<a name="line-48"></a> <span class='hs-varid'>maximum</span><span class='hs-layout'>,</span>
<a name="line-49"></a> <span class='hs-varid'>maximumBy</span><span class='hs-layout'>,</span>
<a name="line-50"></a> <span class='hs-varid'>minimum</span><span class='hs-layout'>,</span>
<a name="line-51"></a> <span class='hs-varid'>minimumBy</span><span class='hs-layout'>,</span>
<a name="line-52"></a> <span class='hs-comment'>-- ** Searches</span>
<a name="line-53"></a> <span class='hs-varid'>elem</span><span class='hs-layout'>,</span>
<a name="line-54"></a> <span class='hs-varid'>notElem</span><span class='hs-layout'>,</span>
<a name="line-55"></a> <span class='hs-varid'>find</span>
<a name="line-56"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-57"></a>
<a name="line-58"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Prelude</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-varid'>foldl</span><span class='hs-layout'>,</span> <span class='hs-varid'>foldr</span><span class='hs-layout'>,</span> <span class='hs-varid'>foldl1</span><span class='hs-layout'>,</span> <span class='hs-varid'>foldr1</span><span class='hs-layout'>,</span> <span class='hs-varid'>mapM_</span><span class='hs-layout'>,</span> <span class='hs-varid'>sequence_</span><span class='hs-layout'>,</span>
<a name="line-59"></a> <span class='hs-varid'>elem</span><span class='hs-layout'>,</span> <span class='hs-varid'>notElem</span><span class='hs-layout'>,</span> <span class='hs-varid'>concat</span><span class='hs-layout'>,</span> <span class='hs-varid'>concatMap</span><span class='hs-layout'>,</span> <span class='hs-varid'>and</span><span class='hs-layout'>,</span> <span class='hs-varid'>or</span><span class='hs-layout'>,</span> <span class='hs-varid'>any</span><span class='hs-layout'>,</span> <span class='hs-varid'>all</span><span class='hs-layout'>,</span>
<a name="line-60"></a> <span class='hs-varid'>sum</span><span class='hs-layout'>,</span> <span class='hs-varid'>product</span><span class='hs-layout'>,</span> <span class='hs-varid'>maximum</span><span class='hs-layout'>,</span> <span class='hs-varid'>minimum</span><span class='hs-layout'>)</span>
<a name="line-61"></a><span class='hs-keyword'>import</span> <span class='hs-keyword'>qualified</span> <span class='hs-conid'>Prelude</span> <span class='hs-layout'>(</span><span class='hs-varid'>foldl</span><span class='hs-layout'>,</span> <span class='hs-varid'>foldr</span><span class='hs-layout'>,</span> <span class='hs-varid'>foldl1</span><span class='hs-layout'>,</span> <span class='hs-varid'>foldr1</span><span class='hs-layout'>)</span>
<a name="line-62"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Applicative</span>
<a name="line-63"></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-conid'>MonadPlus</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-64"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-varid'>fromMaybe</span><span class='hs-layout'>,</span> <span class='hs-varid'>listToMaybe</span><span class='hs-layout'>)</span>
<a name="line-65"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Monoid</span>
<a name="line-66"></a>
<a name="line-67"></a><span class='hs-cpp'>#ifdef __NHC__</span>
<a name="line-68"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Arrow</span> <span class='hs-layout'>(</span><span class='hs-conid'>ArrowZero</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- work around nhc98 typechecker problem</span>
<a name="line-69"></a><span class='hs-cpp'>#endif</span>
<a name="line-70"></a>
<a name="line-71"></a><span class='hs-cpp'>#ifdef __GLASGOW_HASKELL__</span>
<a name="line-72"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>GHC</span><span class='hs-varop'>.</span><span class='hs-conid'>Exts</span> <span class='hs-layout'>(</span><span class='hs-varid'>build</span><span class='hs-layout'>)</span>
<a name="line-73"></a><span class='hs-cpp'>#endif</span>
<a name="line-74"></a>
<a name="line-75"></a><span class='hs-cpp'>#if defined(__GLASGOW_HASKELL__)</span>
<a name="line-76"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>GHC</span><span class='hs-varop'>.</span><span class='hs-conid'>Arr</span>
<a name="line-77"></a><span class='hs-cpp'>#elif defined(__HUGS__)</span>
<a name="line-78"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Hugs</span><span class='hs-varop'>.</span><span class='hs-conid'>Array</span>
<a name="line-79"></a><span class='hs-cpp'>#elif defined(__NHC__)</span>
<a name="line-80"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Array</span>
<a name="line-81"></a><span class='hs-cpp'>#endif</span>
<a name="line-82"></a>
<a name="line-83"></a><span class='hs-comment'>-- | Data structures that can be folded.</span>
<a name="line-84"></a><span class='hs-comment'>--</span>
<a name="line-85"></a><span class='hs-comment'>-- Minimal complete definition: 'foldMap' or 'foldr'.</span>
<a name="line-86"></a><span class='hs-comment'>--</span>
<a name="line-87"></a><span class='hs-comment'>-- For example, given a data type</span>
<a name="line-88"></a><span class='hs-comment'>--</span>
<a name="line-89"></a><span class='hs-comment'>-- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)</span>
<a name="line-90"></a><span class='hs-comment'>--</span>
<a name="line-91"></a><span class='hs-comment'>-- a suitable instance would be</span>
<a name="line-92"></a><span class='hs-comment'>--</span>
<a name="line-93"></a><span class='hs-comment'>-- > instance Foldable Tree where</span>
<a name="line-94"></a><span class='hs-comment'>-- > foldMap f Empty = mempty</span>
<a name="line-95"></a><span class='hs-comment'>-- > foldMap f (Leaf x) = f x</span>
<a name="line-96"></a><span class='hs-comment'>-- > foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r</span>
<a name="line-97"></a><span class='hs-comment'>--</span>
<a name="line-98"></a><span class='hs-comment'>-- This is suitable even for abstract types, as the monoid is assumed</span>
<a name="line-99"></a><span class='hs-comment'>-- to satisfy the monoid laws. Alternatively, one could define @foldr@:</span>
<a name="line-100"></a><span class='hs-comment'>--</span>
<a name="line-101"></a><span class='hs-comment'>-- > instance Foldable Tree where</span>
<a name="line-102"></a><span class='hs-comment'>-- > foldr f z Empty = z</span>
<a name="line-103"></a><span class='hs-comment'>-- > foldr f z (Leaf x) = f x z</span>
<a name="line-104"></a><span class='hs-comment'>-- > foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l</span>
<a name="line-105"></a><span class='hs-comment'>--</span>
<a name="line-106"></a><span class='hs-keyword'>class</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span> <span class='hs-keyword'>where</span>
<a name="line-107"></a> <span class='hs-comment'>-- | Combine the elements of a structure using a monoid.</span>
<a name="line-108"></a> <span class='hs-varid'>fold</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Monoid</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m</span>
<a name="line-109"></a> <span class='hs-varid'>fold</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldMap</span> <span class='hs-varid'>id</span>
<a name="line-110"></a>
<a name="line-111"></a> <span class='hs-comment'>-- | Map each element of the structure to a monoid,</span>
<a name="line-112"></a> <span class='hs-comment'>-- and combine the results.</span>
<a name="line-113"></a> <span class='hs-varid'>foldMap</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Monoid</span> <span class='hs-varid'>m</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'>m</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m</span>
<a name="line-114"></a> <span class='hs-varid'>foldMap</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-layout'>(</span><span class='hs-varid'>mappend</span> <span class='hs-varop'>.</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-varid'>mempty</span>
<a name="line-115"></a>
<a name="line-116"></a> <span class='hs-comment'>-- | Right-associative fold of a structure.</span>
<a name="line-117"></a> <span class='hs-comment'>--</span>
<a name="line-118"></a> <span class='hs-comment'>-- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@</span>
<a name="line-119"></a> <span class='hs-varid'>foldr</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'>b</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'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span>
<a name="line-120"></a> <span class='hs-varid'>foldr</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>appEndo</span> <span class='hs-layout'>(</span><span class='hs-varid'>foldMap</span> <span class='hs-layout'>(</span><span class='hs-conid'>Endo</span> <span class='hs-varop'>.</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-varid'>z</span>
<a name="line-121"></a>
<a name="line-122"></a> <span class='hs-comment'>-- | Left-associative fold of a structure.</span>
<a name="line-123"></a> <span class='hs-comment'>--</span>
<a name="line-124"></a> <span class='hs-comment'>-- @'foldl' f z = 'Prelude.foldl' f z . 'toList'@</span>
<a name="line-125"></a> <span class='hs-varid'>foldl</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'>a</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-varid'>t</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-126"></a> <span class='hs-varid'>foldl</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>appEndo</span> <span class='hs-layout'>(</span><span class='hs-varid'>getDual</span> <span class='hs-layout'>(</span><span class='hs-varid'>foldMap</span> <span class='hs-layout'>(</span><span class='hs-conid'>Dual</span> <span class='hs-varop'>.</span> <span class='hs-conid'>Endo</span> <span class='hs-varop'>.</span> <span class='hs-varid'>flip</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>z</span>
<a name="line-127"></a>
<a name="line-128"></a> <span class='hs-comment'>-- | A variant of 'foldr' that has no base case,</span>
<a name="line-129"></a> <span class='hs-comment'>-- and thus may only be applied to non-empty structures.</span>
<a name="line-130"></a> <span class='hs-comment'>--</span>
<a name="line-131"></a> <span class='hs-comment'>-- @'foldr1' f = 'Prelude.foldr1' f . 'toList'@</span>
<a name="line-132"></a> <span class='hs-varid'>foldr1</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-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-133"></a> <span class='hs-varid'>foldr1</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fromMaybe</span> <span class='hs-layout'>(</span><span class='hs-varid'>error</span> <span class='hs-str'>"foldr1: empty structure"</span><span class='hs-layout'>)</span>
<a name="line-134"></a> <span class='hs-layout'>(</span><span class='hs-varid'>foldr</span> <span class='hs-varid'>mf</span> <span class='hs-conid'>Nothing</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
<a name="line-135"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>mf</span> <span class='hs-varid'>x</span> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>x</span>
<a name="line-136"></a> <span class='hs-varid'>mf</span> <span class='hs-varid'>x</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>y</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span><span class='hs-layout'>)</span>
<a name="line-137"></a>
<a name="line-138"></a> <span class='hs-comment'>-- | A variant of 'foldl' that has no base case,</span>
<a name="line-139"></a> <span class='hs-comment'>-- and thus may only be applied to non-empty structures.</span>
<a name="line-140"></a> <span class='hs-comment'>--</span>
<a name="line-141"></a> <span class='hs-comment'>-- @'foldl1' f = 'Prelude.foldl1' f . 'toList'@</span>
<a name="line-142"></a> <span class='hs-varid'>foldl1</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-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-143"></a> <span class='hs-varid'>foldl1</span> <span class='hs-varid'>f</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fromMaybe</span> <span class='hs-layout'>(</span><span class='hs-varid'>error</span> <span class='hs-str'>"foldl1: empty structure"</span><span class='hs-layout'>)</span>
<a name="line-144"></a> <span class='hs-layout'>(</span><span class='hs-varid'>foldl</span> <span class='hs-varid'>mf</span> <span class='hs-conid'>Nothing</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
<a name="line-145"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>mf</span> <span class='hs-conid'>Nothing</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>y</span>
<a name="line-146"></a> <span class='hs-varid'>mf</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span><span class='hs-layout'>)</span>
<a name="line-147"></a>
<a name="line-148"></a><span class='hs-comment'>-- instances for Prelude types</span>
<a name="line-149"></a>
<a name="line-150"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Foldable</span> <span class='hs-conid'>Maybe</span> <span class='hs-keyword'>where</span>
<a name="line-151"></a> <span class='hs-varid'>foldr</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>z</span> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>z</span>
<a name="line-152"></a> <span class='hs-varid'>foldr</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>x</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'>z</span>
<a name="line-153"></a>
<a name="line-154"></a> <span class='hs-varid'>foldl</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>z</span> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>z</span>
<a name="line-155"></a> <span class='hs-varid'>foldl</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-varid'>x</span>
<a name="line-156"></a>
<a name="line-157"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Foldable</span> <span class='hs-conid'>[]</span> <span class='hs-keyword'>where</span>
<a name="line-158"></a> <span class='hs-varid'>foldr</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>foldr</span>
<a name="line-159"></a> <span class='hs-varid'>foldl</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>foldl</span>
<a name="line-160"></a> <span class='hs-varid'>foldr1</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>foldr1</span>
<a name="line-161"></a> <span class='hs-varid'>foldl1</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>foldl1</span>
<a name="line-162"></a>
<a name="line-163"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Ix</span> <span class='hs-varid'>i</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Foldable</span> <span class='hs-layout'>(</span><span class='hs-conid'>Array</span> <span class='hs-varid'>i</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-164"></a> <span class='hs-varid'>foldr</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>foldr</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-varop'>.</span> <span class='hs-varid'>elems</span>
<a name="line-165"></a> <span class='hs-varid'>foldl</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>foldl</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-varop'>.</span> <span class='hs-varid'>elems</span>
<a name="line-166"></a> <span class='hs-varid'>foldr1</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>foldr1</span> <span class='hs-varid'>f</span> <span class='hs-varop'>.</span> <span class='hs-varid'>elems</span>
<a name="line-167"></a> <span class='hs-varid'>foldl1</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>foldl1</span> <span class='hs-varid'>f</span> <span class='hs-varop'>.</span> <span class='hs-varid'>elems</span>
<a name="line-168"></a>
<a name="line-169"></a><a name="foldr'"></a><span class='hs-comment'>-- | Fold over the elements of a structure,</span>
<a name="line-170"></a><span class='hs-comment'>-- associating to the right, but strictly.</span>
<a name="line-171"></a><span class='hs-definition'>foldr'</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</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'>b</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'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span>
<a name="line-172"></a><span class='hs-definition'>foldr'</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z0</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldl</span> <span class='hs-varid'>f'</span> <span class='hs-varid'>id</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>z0</span>
<a name="line-173"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>f'</span> <span class='hs-varid'>k</span> <span class='hs-varid'>x</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>k</span> <span class='hs-varop'>$!</span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span> <span class='hs-varid'>z</span>
<a name="line-174"></a>
<a name="line-175"></a><a name="foldrM"></a><span class='hs-comment'>-- | Monadic fold over the elements of a structure,</span>
<a name="line-176"></a><span class='hs-comment'>-- associating to the right, i.e. from right to left.</span>
<a name="line-177"></a><span class='hs-definition'>foldrM</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Monad</span> <span class='hs-varid'>m</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'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m</span> <span class='hs-varid'>b</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'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m</span> <span class='hs-varid'>b</span>
<a name="line-178"></a><span class='hs-definition'>foldrM</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z0</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldl</span> <span class='hs-varid'>f'</span> <span class='hs-varid'>return</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>z0</span>
<a name="line-179"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>f'</span> <span class='hs-varid'>k</span> <span class='hs-varid'>x</span> <span class='hs-varid'>z</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-varop'>>>=</span> <span class='hs-varid'>k</span>
<a name="line-180"></a>
<a name="line-181"></a><a name="foldl'"></a><span class='hs-comment'>-- | Fold over the elements of a structure,</span>
<a name="line-182"></a><span class='hs-comment'>-- associating to the left, but strictly.</span>
<a name="line-183"></a><span class='hs-definition'>foldl'</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</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'>a</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-varid'>t</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-184"></a><span class='hs-definition'>foldl'</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z0</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-varid'>f'</span> <span class='hs-varid'>id</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>z0</span>
<a name="line-185"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>f'</span> <span class='hs-varid'>x</span> <span class='hs-varid'>k</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>k</span> <span class='hs-varop'>$!</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-varid'>x</span>
<a name="line-186"></a>
<a name="line-187"></a><a name="foldlM"></a><span class='hs-comment'>-- | Monadic fold over the elements of a structure,</span>
<a name="line-188"></a><span class='hs-comment'>-- associating to the left, i.e. from left to right.</span>
<a name="line-189"></a><span class='hs-definition'>foldlM</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Monad</span> <span class='hs-varid'>m</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'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m</span> <span class='hs-varid'>a</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-varid'>t</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m</span> <span class='hs-varid'>a</span>
<a name="line-190"></a><span class='hs-definition'>foldlM</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z0</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-varid'>f'</span> <span class='hs-varid'>return</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>z0</span>
<a name="line-191"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>f'</span> <span class='hs-varid'>x</span> <span class='hs-varid'>k</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span> <span class='hs-varid'>z</span> <span class='hs-varid'>x</span> <span class='hs-varop'>>>=</span> <span class='hs-varid'>k</span>
<a name="line-192"></a>
<a name="line-193"></a><a name="traverse_"></a><span class='hs-comment'>-- | Map each element of a structure to an action, evaluate</span>
<a name="line-194"></a><span class='hs-comment'>-- these actions from left to right, and ignore the results.</span>
<a name="line-195"></a><span class='hs-definition'>traverse_</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Applicative</span> <span class='hs-varid'>f</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'>f</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>f</span> <span class='hs-conid'>()</span>
<a name="line-196"></a><span class='hs-definition'>traverse_</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varop'>*></span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>pure</span> <span class='hs-conid'>()</span><span class='hs-layout'>)</span>
<a name="line-197"></a>
<a name="line-198"></a><a name="for_"></a><span class='hs-comment'>-- | 'for_' is 'traverse_' with its arguments flipped.</span>
<a name="line-199"></a><span class='hs-definition'>for_</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Applicative</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</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-keyglyph'>-></span> <span class='hs-varid'>f</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-conid'>()</span>
<a name="line-200"></a><span class='hs-comment'>{-# INLINE for_ #-}</span>
<a name="line-201"></a><span class='hs-definition'>for_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>flip</span> <span class='hs-varid'>traverse_</span>
<a name="line-202"></a>
<a name="line-203"></a><a name="mapM_"></a><span class='hs-comment'>-- | Map each element of a structure to a monadic action, evaluate</span>
<a name="line-204"></a><span class='hs-comment'>-- these actions from left to right, and ignore the results.</span>
<a name="line-205"></a><span class='hs-definition'>mapM_</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Monad</span> <span class='hs-varid'>m</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'>m</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m</span> <span class='hs-conid'>()</span>
<a name="line-206"></a><span class='hs-definition'>mapM_</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varop'>>></span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>return</span> <span class='hs-conid'>()</span><span class='hs-layout'>)</span>
<a name="line-207"></a>
<a name="line-208"></a><a name="forM_"></a><span class='hs-comment'>-- | 'forM_' is 'mapM_' with its arguments flipped.</span>
<a name="line-209"></a><span class='hs-definition'>forM_</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Monad</span> <span class='hs-varid'>m</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</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-keyglyph'>-></span> <span class='hs-varid'>m</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m</span> <span class='hs-conid'>()</span>
<a name="line-210"></a><span class='hs-comment'>{-# INLINE forM_ #-}</span>
<a name="line-211"></a><span class='hs-definition'>forM_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>flip</span> <span class='hs-varid'>mapM_</span>
<a name="line-212"></a>
<a name="line-213"></a><a name="sequenceA_"></a><span class='hs-comment'>-- | Evaluate each action in the structure from left to right,</span>
<a name="line-214"></a><span class='hs-comment'>-- and ignore the results.</span>
<a name="line-215"></a><span class='hs-definition'>sequenceA_</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Applicative</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>f</span> <span class='hs-conid'>()</span>
<a name="line-216"></a><span class='hs-definition'>sequenceA_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-layout'>(</span><span class='hs-varop'>*></span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>pure</span> <span class='hs-conid'>()</span><span class='hs-layout'>)</span>
<a name="line-217"></a>
<a name="line-218"></a><a name="sequence_"></a><span class='hs-comment'>-- | Evaluate each monadic action in the structure from left to right,</span>
<a name="line-219"></a><span class='hs-comment'>-- and ignore the results.</span>
<a name="line-220"></a><span class='hs-definition'>sequence_</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Monad</span> <span class='hs-varid'>m</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m</span> <span class='hs-conid'>()</span>
<a name="line-221"></a><span class='hs-definition'>sequence_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-layout'>(</span><span class='hs-varop'>>></span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>return</span> <span class='hs-conid'>()</span><span class='hs-layout'>)</span>
<a name="line-222"></a>
<a name="line-223"></a><a name="asum"></a><span class='hs-comment'>-- | The sum of a collection of actions, generalizing 'concat'.</span>
<a name="line-224"></a><span class='hs-definition'>asum</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Alternative</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>f</span> <span class='hs-varid'>a</span>
<a name="line-225"></a><span class='hs-comment'>{-# INLINE asum #-}</span>
<a name="line-226"></a><span class='hs-definition'>asum</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-layout'>(</span><span class='hs-varop'><|></span><span class='hs-layout'>)</span> <span class='hs-varid'>empty</span>
<a name="line-227"></a>
<a name="line-228"></a><a name="msum"></a><span class='hs-comment'>-- | The sum of a collection of actions, generalizing 'concat'.</span>
<a name="line-229"></a><span class='hs-definition'>msum</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>MonadPlus</span> <span class='hs-varid'>m</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m</span> <span class='hs-varid'>a</span>
<a name="line-230"></a><span class='hs-comment'>{-# INLINE msum #-}</span>
<a name="line-231"></a><span class='hs-definition'>msum</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-varid'>mplus</span> <span class='hs-varid'>mzero</span>
<a name="line-232"></a>
<a name="line-233"></a><span class='hs-comment'>-- These use foldr rather than foldMap to avoid repeated concatenation.</span>
<a name="line-234"></a>
<a name="line-235"></a><a name="toList"></a><span class='hs-comment'>-- | List of elements of a structure.</span>
<a name="line-236"></a><span class='hs-definition'>toList</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</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-237"></a><span class='hs-comment'>{-# INLINE toList #-}</span>
<a name="line-238"></a><span class='hs-cpp'>#ifdef __GLASGOW_HASKELL__</span>
<a name="line-239"></a><span class='hs-definition'>toList</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>build</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span> <span class='hs-varid'>c</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>foldr</span> <span class='hs-varid'>c</span> <span class='hs-varid'>n</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-240"></a><span class='hs-cpp'>#else</span>
<a name="line-241"></a><span class='hs-definition'>toList</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-layout'>(</span><span class='hs-conop'>:</span><span class='hs-layout'>)</span> <span class='hs-conid'>[]</span>
<a name="line-242"></a><span class='hs-cpp'>#endif</span>
<a name="line-243"></a>
<a name="line-244"></a><a name="concat"></a><span class='hs-comment'>-- | The concatenation of all the elements of a container of lists.</span>
<a name="line-245"></a><span class='hs-definition'>concat</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</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-246"></a><span class='hs-definition'>concat</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fold</span>
<a name="line-247"></a>
<a name="line-248"></a><a name="concatMap"></a><span class='hs-comment'>-- | Map a function over all the elements of a container and concatenate</span>
<a name="line-249"></a><span class='hs-comment'>-- the resulting lists.</span>
<a name="line-250"></a><span class='hs-definition'>concatMap</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</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'>b</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>t</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>
<a name="line-251"></a><span class='hs-definition'>concatMap</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldMap</span>
<a name="line-252"></a>
<a name="line-253"></a><a name="and"></a><span class='hs-comment'>-- | 'and' returns the conjunction of a container of Bools. For the</span>
<a name="line-254"></a><span class='hs-comment'>-- result to be 'True', the container must be finite; 'False', however,</span>
<a name="line-255"></a><span class='hs-comment'>-- results from a 'False' value finitely far from the left end.</span>
<a name="line-256"></a><span class='hs-definition'>and</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</span> <span class='hs-conid'>Bool</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-257"></a><span class='hs-definition'>and</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>getAll</span> <span class='hs-varop'>.</span> <span class='hs-varid'>foldMap</span> <span class='hs-conid'>All</span>
<a name="line-258"></a>
<a name="line-259"></a><a name="or"></a><span class='hs-comment'>-- | 'or' returns the disjunction of a container of Bools. For the</span>
<a name="line-260"></a><span class='hs-comment'>-- result to be 'False', the container must be finite; 'True', however,</span>
<a name="line-261"></a><span class='hs-comment'>-- results from a 'True' value finitely far from the left end.</span>
<a name="line-262"></a><span class='hs-definition'>or</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</span> <span class='hs-conid'>Bool</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-263"></a><span class='hs-definition'>or</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>getAny</span> <span class='hs-varop'>.</span> <span class='hs-varid'>foldMap</span> <span class='hs-conid'>Any</span>
<a name="line-264"></a>
<a name="line-265"></a><a name="any"></a><span class='hs-comment'>-- | Determines whether any element of the structure satisfies the predicate.</span>
<a name="line-266"></a><span class='hs-definition'>any</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</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'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-267"></a><span class='hs-definition'>any</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>getAny</span> <span class='hs-varop'>.</span> <span class='hs-varid'>foldMap</span> <span class='hs-layout'>(</span><span class='hs-conid'>Any</span> <span class='hs-varop'>.</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span>
<a name="line-268"></a>
<a name="line-269"></a><a name="all"></a><span class='hs-comment'>-- | Determines whether all elements of the structure satisfy the predicate.</span>
<a name="line-270"></a><span class='hs-definition'>all</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</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'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-271"></a><span class='hs-definition'>all</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>getAll</span> <span class='hs-varop'>.</span> <span class='hs-varid'>foldMap</span> <span class='hs-layout'>(</span><span class='hs-conid'>All</span> <span class='hs-varop'>.</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span>
<a name="line-272"></a>
<a name="line-273"></a><a name="sum"></a><span class='hs-comment'>-- | The 'sum' function computes the sum of the numbers of a structure.</span>
<a name="line-274"></a><span class='hs-definition'>sum</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Num</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-275"></a><span class='hs-definition'>sum</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>getSum</span> <span class='hs-varop'>.</span> <span class='hs-varid'>foldMap</span> <span class='hs-conid'>Sum</span>
<a name="line-276"></a>
<a name="line-277"></a><a name="product"></a><span class='hs-comment'>-- | The 'product' function computes the product of the numbers of a structure.</span>
<a name="line-278"></a><span class='hs-definition'>product</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Num</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-279"></a><span class='hs-definition'>product</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>getProduct</span> <span class='hs-varop'>.</span> <span class='hs-varid'>foldMap</span> <span class='hs-conid'>Product</span>
<a name="line-280"></a>
<a name="line-281"></a><a name="maximum"></a><span class='hs-comment'>-- | The largest element of a non-empty structure.</span>
<a name="line-282"></a><span class='hs-definition'>maximum</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Ord</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-283"></a><span class='hs-definition'>maximum</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr1</span> <span class='hs-varid'>max</span>
<a name="line-284"></a>
<a name="line-285"></a><a name="maximumBy"></a><span class='hs-comment'>-- | The largest element of a non-empty structure with respect to the</span>
<a name="line-286"></a><span class='hs-comment'>-- given comparison function.</span>
<a name="line-287"></a><span class='hs-definition'>maximumBy</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</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-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-288"></a><span class='hs-definition'>maximumBy</span> <span class='hs-varid'>cmp</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr1</span> <span class='hs-varid'>max'</span>
<a name="line-289"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>max'</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>cmp</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-keyword'>of</span>
<a name="line-290"></a> <span class='hs-conid'>GT</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>x</span>
<a name="line-291"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>y</span>
<a name="line-292"></a>
<a name="line-293"></a><a name="minimum"></a><span class='hs-comment'>-- | The least element of a non-empty structure.</span>
<a name="line-294"></a><span class='hs-definition'>minimum</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Ord</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-295"></a><span class='hs-definition'>minimum</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr1</span> <span class='hs-varid'>min</span>
<a name="line-296"></a>
<a name="line-297"></a><a name="minimumBy"></a><span class='hs-comment'>-- | The least element of a non-empty structure with respect to the</span>
<a name="line-298"></a><span class='hs-comment'>-- given comparison function.</span>
<a name="line-299"></a><span class='hs-definition'>minimumBy</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</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-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-300"></a><span class='hs-definition'>minimumBy</span> <span class='hs-varid'>cmp</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr1</span> <span class='hs-varid'>min'</span>
<a name="line-301"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>min'</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>cmp</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-keyword'>of</span>
<a name="line-302"></a> <span class='hs-conid'>GT</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>y</span>
<a name="line-303"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>x</span>
<a name="line-304"></a>
<a name="line-305"></a><a name="elem"></a><span class='hs-comment'>-- | Does the element occur in the structure?</span>
<a name="line-306"></a><span class='hs-definition'>elem</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Eq</span> <span class='hs-varid'>a</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-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-307"></a><span class='hs-definition'>elem</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>any</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-varop'>==</span><span class='hs-layout'>)</span>
<a name="line-308"></a>
<a name="line-309"></a><a name="notElem"></a><span class='hs-comment'>-- | 'notElem' is the negation of 'elem'.</span>
<a name="line-310"></a><span class='hs-definition'>notElem</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Eq</span> <span class='hs-varid'>a</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-varid'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-311"></a><span class='hs-definition'>notElem</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>not</span> <span class='hs-varop'>.</span> <span class='hs-varid'>elem</span> <span class='hs-varid'>x</span>
<a name="line-312"></a>
<a name="line-313"></a><a name="find"></a><span class='hs-comment'>-- | The 'find' function takes a predicate and a structure and returns</span>
<a name="line-314"></a><span class='hs-comment'>-- the leftmost element of the structure matching the predicate, or</span>
<a name="line-315"></a><span class='hs-comment'>-- 'Nothing' if there is no such element.</span>
<a name="line-316"></a><span class='hs-definition'>find</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Foldable</span> <span class='hs-varid'>t</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'>t</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Maybe</span> <span class='hs-varid'>a</span>
<a name="line-317"></a><span class='hs-definition'>find</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>listToMaybe</span> <span class='hs-varop'>.</span> <span class='hs-varid'>concatMap</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>if</span> <span class='hs-varid'>p</span> <span class='hs-varid'>x</span> <span class='hs-keyword'>then</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>x</span><span class='hs-keyglyph'>]</span> <span class='hs-keyword'>else</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
</pre></body>
</html>
