<?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/Traversable.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.Traversable</span>
<a name="line-4"></a><span class='hs-comment'>-- Copyright : Conor McBride and 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 traversed from left to right,</span>
<a name="line-12"></a><span class='hs-comment'>-- performing an action on each element.</span>
<a name="line-13"></a><span class='hs-comment'>--</span>
<a name="line-14"></a><span class='hs-comment'>-- See also</span>
<a name="line-15"></a><span class='hs-comment'>--</span>
<a name="line-16"></a><span class='hs-comment'>-- * /Applicative Programming with Effects/,</span>
<a name="line-17"></a><span class='hs-comment'>-- by Conor McBride and Ross Paterson, online at</span>
<a name="line-18"></a><span class='hs-comment'>-- <<a href="http://www.soi.city.ac.uk/~ross/papers/Applicative.html">http://www.soi.city.ac.uk/~ross/papers/Applicative.html</a>>.</span>
<a name="line-19"></a><span class='hs-comment'>--</span>
<a name="line-20"></a><span class='hs-comment'>-- * /The Essence of the Iterator Pattern/,</span>
<a name="line-21"></a><span class='hs-comment'>-- by Jeremy Gibbons and Bruno Oliveira,</span>
<a name="line-22"></a><span class='hs-comment'>-- in /Mathematically-Structured Functional Programming/, 2006, and online at</span>
<a name="line-23"></a><span class='hs-comment'>-- <<a href="http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/#iterator">http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/#iterator</a>>.</span>
<a name="line-24"></a><span class='hs-comment'>--</span>
<a name="line-25"></a><span class='hs-comment'>-- Note that the functions 'mapM' and 'sequence' generalize "Prelude"</span>
<a name="line-26"></a><span class='hs-comment'>-- functions of the same names from lists to any 'Traversable' functor.</span>
<a name="line-27"></a><span class='hs-comment'>-- To avoid ambiguity, either import the "Prelude" hiding these names</span>
<a name="line-28"></a><span class='hs-comment'>-- or qualify uses of these function names with an alias for this module.</span>
<a name="line-29"></a>
<a name="line-30"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Traversable</span> <span class='hs-layout'>(</span>
<a name="line-31"></a> <span class='hs-conid'>Traversable</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span>
<a name="line-32"></a> <span class='hs-varid'>for</span><span class='hs-layout'>,</span>
<a name="line-33"></a> <span class='hs-varid'>forM</span><span class='hs-layout'>,</span>
<a name="line-34"></a> <span class='hs-varid'>mapAccumL</span><span class='hs-layout'>,</span>
<a name="line-35"></a> <span class='hs-varid'>mapAccumR</span><span class='hs-layout'>,</span>
<a name="line-36"></a> <span class='hs-varid'>fmapDefault</span><span class='hs-layout'>,</span>
<a name="line-37"></a> <span class='hs-varid'>foldMapDefault</span><span class='hs-layout'>,</span>
<a name="line-38"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-39"></a>
<a name="line-40"></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'>mapM</span><span class='hs-layout'>,</span> <span class='hs-varid'>sequence</span><span class='hs-layout'>,</span> <span class='hs-varid'>foldr</span><span class='hs-layout'>)</span>
<a name="line-41"></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'>mapM</span><span class='hs-layout'>,</span> <span class='hs-varid'>foldr</span><span class='hs-layout'>)</span>
<a name="line-42"></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-43"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Foldable</span> <span class='hs-layout'>(</span><span class='hs-conid'>Foldable</span><span class='hs-conid'>()</span><span class='hs-layout'>)</span>
<a name="line-44"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Monoid</span> <span class='hs-layout'>(</span><span class='hs-conid'>Monoid</span><span class='hs-layout'>)</span>
<a name="line-45"></a>
<a name="line-46"></a><span class='hs-cpp'>#if defined(__GLASGOW_HASKELL__)</span>
<a name="line-47"></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-48"></a><span class='hs-cpp'>#elif defined(__HUGS__)</span>
<a name="line-49"></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-50"></a><span class='hs-cpp'>#elif defined(__NHC__)</span>
<a name="line-51"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Array</span>
<a name="line-52"></a><span class='hs-cpp'>#endif</span>
<a name="line-53"></a>
<a name="line-54"></a><a name="Traversable"></a><span class='hs-comment'>-- | Functors representing data structures that can be traversed from</span>
<a name="line-55"></a><a name="Traversable"></a><span class='hs-comment'>-- left to right.</span>
<a name="line-56"></a><a name="Traversable"></a><span class='hs-comment'>--</span>
<a name="line-57"></a><a name="Traversable"></a><span class='hs-comment'>-- Minimal complete definition: 'traverse' or 'sequenceA'.</span>
<a name="line-58"></a><a name="Traversable"></a><span class='hs-comment'>--</span>
<a name="line-59"></a><a name="Traversable"></a><span class='hs-comment'>-- Instances are similar to 'Functor', e.g. given a data type</span>
<a name="line-60"></a><a name="Traversable"></a><span class='hs-comment'>--</span>
<a name="line-61"></a><a name="Traversable"></a><span class='hs-comment'>-- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)</span>
<a name="line-62"></a><a name="Traversable"></a><span class='hs-comment'>--</span>
<a name="line-63"></a><a name="Traversable"></a><span class='hs-comment'>-- a suitable instance would be</span>
<a name="line-64"></a><a name="Traversable"></a><span class='hs-comment'>--</span>
<a name="line-65"></a><a name="Traversable"></a><span class='hs-comment'>-- > instance Traversable Tree where</span>
<a name="line-66"></a><a name="Traversable"></a><span class='hs-comment'>-- > traverse f Empty = pure Empty</span>
<a name="line-67"></a><a name="Traversable"></a><span class='hs-comment'>-- > traverse f (Leaf x) = Leaf <$> f x</span>
<a name="line-68"></a><a name="Traversable"></a><span class='hs-comment'>-- > traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r</span>
<a name="line-69"></a><a name="Traversable"></a><span class='hs-comment'>--</span>
<a name="line-70"></a><a name="Traversable"></a><span class='hs-comment'>-- This is suitable even for abstract types, as the laws for '<*>'</span>
<a name="line-71"></a><a name="Traversable"></a><span class='hs-comment'>-- imply a form of associativity.</span>
<a name="line-72"></a><a name="Traversable"></a><span class='hs-comment'>--</span>
<a name="line-73"></a><a name="Traversable"></a><span class='hs-comment'>-- The superclass instances should satisfy the following:</span>
<a name="line-74"></a><a name="Traversable"></a><span class='hs-comment'>--</span>
<a name="line-75"></a><a name="Traversable"></a><span class='hs-comment'>-- * In the 'Functor' instance, 'fmap' should be equivalent to traversal</span>
<a name="line-76"></a><a name="Traversable"></a><span class='hs-comment'>-- with the identity applicative functor ('fmapDefault').</span>
<a name="line-77"></a><a name="Traversable"></a><span class='hs-comment'>--</span>
<a name="line-78"></a><a name="Traversable"></a><span class='hs-comment'>-- * In the 'Foldable' instance, 'Data.Foldable.foldMap' should be</span>
<a name="line-79"></a><a name="Traversable"></a><span class='hs-comment'>-- equivalent to traversal with a constant applicative functor</span>
<a name="line-80"></a><a name="Traversable"></a><span class='hs-comment'>-- ('foldMapDefault').</span>
<a name="line-81"></a><a name="Traversable"></a><span class='hs-comment'>--</span>
<a name="line-82"></a><a name="Traversable"></a><span class='hs-keyword'>class</span> <span class='hs-layout'>(</span><span class='hs-conid'>Functor</span> <span class='hs-varid'>t</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-keyglyph'>=></span> <span class='hs-conid'>Traversable</span> <span class='hs-varid'>t</span> <span class='hs-keyword'>where</span>
<a name="line-83"></a> <span class='hs-comment'>-- | Map each element of a structure to an action, evaluate</span>
<a name="line-84"></a> <span class='hs-comment'>-- these actions from left to right, and collect the results.</span>
<a name="line-85"></a> <span class='hs-varid'>traverse</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Applicative</span> <span class='hs-varid'>f</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-layout'>(</span><span class='hs-varid'>t</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-86"></a> <span class='hs-varid'>traverse</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>sequenceA</span> <span class='hs-varop'>.</span> <span class='hs-varid'>fmap</span> <span class='hs-varid'>f</span>
<a name="line-87"></a>
<a name="line-88"></a> <span class='hs-comment'>-- | Evaluate each action in the structure from left to right,</span>
<a name="line-89"></a> <span class='hs-comment'>-- and collect the results.</span>
<a name="line-90"></a> <span class='hs-varid'>sequenceA</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Applicative</span> <span class='hs-varid'>f</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-layout'>(</span><span class='hs-varid'>t</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-91"></a> <span class='hs-varid'>sequenceA</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>traverse</span> <span class='hs-varid'>id</span>
<a name="line-92"></a>
<a name="line-93"></a> <span class='hs-comment'>-- | Map each element of a structure to a monadic action, evaluate</span>
<a name="line-94"></a> <span class='hs-comment'>-- these actions from left to right, and collect the results.</span>
<a name="line-95"></a> <span class='hs-varid'>mapM</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Monad</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-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-layout'>(</span><span class='hs-varid'>t</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-96"></a> <span class='hs-varid'>mapM</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>unwrapMonad</span> <span class='hs-varop'>.</span> <span class='hs-varid'>traverse</span> <span class='hs-layout'>(</span><span class='hs-conid'>WrapMonad</span> <span class='hs-varop'>.</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span>
<a name="line-97"></a>
<a name="line-98"></a> <span class='hs-comment'>-- | Evaluate each monadic action in the structure from left to right,</span>
<a name="line-99"></a> <span class='hs-comment'>-- and collect the results.</span>
<a name="line-100"></a> <span class='hs-varid'>sequence</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Monad</span> <span class='hs-varid'>m</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-layout'>(</span><span class='hs-varid'>t</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-101"></a> <span class='hs-varid'>sequence</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mapM</span> <span class='hs-varid'>id</span>
<a name="line-102"></a>
<a name="line-103"></a><span class='hs-comment'>-- instances for Prelude types</span>
<a name="line-104"></a>
<a name="line-105"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Traversable</span> <span class='hs-conid'>Maybe</span> <span class='hs-keyword'>where</span>
<a name="line-106"></a> <span class='hs-varid'>traverse</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pure</span> <span class='hs-conid'>Nothing</span>
<a name="line-107"></a> <span class='hs-varid'>traverse</span> <span class='hs-varid'>f</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-conid'>Just</span> <span class='hs-varop'><$></span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span>
<a name="line-108"></a>
<a name="line-109"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Traversable</span> <span class='hs-conid'>[]</span> <span class='hs-keyword'>where</span>
<a name="line-110"></a> <span class='hs-comment'>{-# INLINE traverse #-}</span> <span class='hs-comment'>-- so that traverse can fuse</span>
<a name="line-111"></a> <span class='hs-varid'>traverse</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'>foldr</span> <span class='hs-varid'>cons_f</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-112"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>cons_f</span> <span class='hs-varid'>x</span> <span class='hs-varid'>ys</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-conop'>:</span><span class='hs-layout'>)</span> <span class='hs-varop'><$></span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span> <span class='hs-varop'><*></span> <span class='hs-varid'>ys</span>
<a name="line-113"></a>
<a name="line-114"></a> <span class='hs-varid'>mapM</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>mapM</span>
<a name="line-115"></a>
<a name="line-116"></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'>Traversable</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-117"></a> <span class='hs-varid'>traverse</span> <span class='hs-varid'>f</span> <span class='hs-varid'>arr</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>listArray</span> <span class='hs-layout'>(</span><span class='hs-varid'>bounds</span> <span class='hs-varid'>arr</span><span class='hs-layout'>)</span> <span class='hs-varop'>`fmap`</span> <span class='hs-varid'>traverse</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-varid'>elems</span> <span class='hs-varid'>arr</span><span class='hs-layout'>)</span>
<a name="line-118"></a>
<a name="line-119"></a><span class='hs-comment'>-- general functions</span>
<a name="line-120"></a>
<a name="line-121"></a><a name="for"></a><span class='hs-comment'>-- | 'for' is 'traverse' with its arguments flipped.</span>
<a name="line-122"></a><span class='hs-definition'>for</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Traversable</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-layout'>(</span><span class='hs-varid'>t</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-123"></a><span class='hs-comment'>{-# INLINE for #-}</span>
<a name="line-124"></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-125"></a>
<a name="line-126"></a><a name="forM"></a><span class='hs-comment'>-- | 'forM' is 'mapM' with its arguments flipped.</span>
<a name="line-127"></a><span class='hs-definition'>forM</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Traversable</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-layout'>(</span><span class='hs-varid'>t</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-128"></a><span class='hs-comment'>{-# INLINE forM #-}</span>
<a name="line-129"></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-130"></a>
<a name="line-131"></a><a name="StateL"></a><span class='hs-comment'>-- left-to-right state transformer</span>
<a name="line-132"></a><a name="StateL"></a><span class='hs-keyword'>newtype</span> <span class='hs-conid'>StateL</span> <span class='hs-varid'>s</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>StateL</span> <span class='hs-layout'>{</span> <span class='hs-varid'>runStateL</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>s</span><span class='hs-layout'>,</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-layout'>}</span>
<a name="line-133"></a>
<a name="line-134"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Functor</span> <span class='hs-layout'>(</span><span class='hs-conid'>StateL</span> <span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-135"></a> <span class='hs-varid'>fmap</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>StateL</span> <span class='hs-varid'>k</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>StateL</span> <span class='hs-varop'>$</span> <span class='hs-keyglyph'>\</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span>
<a name="line-136"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>s'</span><span class='hs-layout'>,</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>k</span> <span class='hs-varid'>s</span> <span class='hs-keyword'>in</span> <span class='hs-layout'>(</span><span class='hs-varid'>s'</span><span class='hs-layout'>,</span> <span class='hs-varid'>f</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span>
<a name="line-137"></a>
<a name="line-138"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Applicative</span> <span class='hs-layout'>(</span><span class='hs-conid'>StateL</span> <span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-139"></a> <span class='hs-varid'>pure</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>StateL</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>s</span><span class='hs-layout'>,</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-140"></a> <span class='hs-conid'>StateL</span> <span class='hs-varid'>kf</span> <span class='hs-varop'><*></span> <span class='hs-conid'>StateL</span> <span class='hs-varid'>kv</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>StateL</span> <span class='hs-varop'>$</span> <span class='hs-keyglyph'>\</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span>
<a name="line-141"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>s'</span><span class='hs-layout'>,</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>kf</span> <span class='hs-varid'>s</span>
<a name="line-142"></a> <span class='hs-layout'>(</span><span class='hs-varid'>s''</span><span class='hs-layout'>,</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>kv</span> <span class='hs-varid'>s'</span>
<a name="line-143"></a> <span class='hs-keyword'>in</span> <span class='hs-layout'>(</span><span class='hs-varid'>s''</span><span class='hs-layout'>,</span> <span class='hs-varid'>f</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span>
<a name="line-144"></a>
<a name="line-145"></a><a name="mapAccumL"></a><span class='hs-comment'>-- |The 'mapAccumL' function behaves like a combination of 'fmap'</span>
<a name="line-146"></a><span class='hs-comment'>-- and 'foldl'; it applies a function to each element of a structure,</span>
<a name="line-147"></a><span class='hs-comment'>-- passing an accumulating parameter from left to right, and returning</span>
<a name="line-148"></a><span class='hs-comment'>-- a final value of this accumulator together with the new structure.</span>
<a name="line-149"></a><span class='hs-definition'>mapAccumL</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Traversable</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-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-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-layout'>(</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span> <span class='hs-varid'>t</span> <span class='hs-varid'>c</span><span class='hs-layout'>)</span>
<a name="line-150"></a><span class='hs-definition'>mapAccumL</span> <span class='hs-varid'>f</span> <span class='hs-varid'>s</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>runStateL</span> <span class='hs-layout'>(</span><span class='hs-varid'>traverse</span> <span class='hs-layout'>(</span><span class='hs-conid'>StateL</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-varid'>s</span>
<a name="line-151"></a>
<a name="line-152"></a><a name="StateR"></a><span class='hs-comment'>-- right-to-left state transformer</span>
<a name="line-153"></a><a name="StateR"></a><span class='hs-keyword'>newtype</span> <span class='hs-conid'>StateR</span> <span class='hs-varid'>s</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>StateR</span> <span class='hs-layout'>{</span> <span class='hs-varid'>runStateR</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>s</span><span class='hs-layout'>,</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-layout'>}</span>
<a name="line-154"></a>
<a name="line-155"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Functor</span> <span class='hs-layout'>(</span><span class='hs-conid'>StateR</span> <span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-156"></a> <span class='hs-varid'>fmap</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>StateR</span> <span class='hs-varid'>k</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>StateR</span> <span class='hs-varop'>$</span> <span class='hs-keyglyph'>\</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span>
<a name="line-157"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>s'</span><span class='hs-layout'>,</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>k</span> <span class='hs-varid'>s</span> <span class='hs-keyword'>in</span> <span class='hs-layout'>(</span><span class='hs-varid'>s'</span><span class='hs-layout'>,</span> <span class='hs-varid'>f</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span>
<a name="line-158"></a>
<a name="line-159"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Applicative</span> <span class='hs-layout'>(</span><span class='hs-conid'>StateR</span> <span class='hs-varid'>s</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-160"></a> <span class='hs-varid'>pure</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>StateR</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>s</span><span class='hs-layout'>,</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-161"></a> <span class='hs-conid'>StateR</span> <span class='hs-varid'>kf</span> <span class='hs-varop'><*></span> <span class='hs-conid'>StateR</span> <span class='hs-varid'>kv</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>StateR</span> <span class='hs-varop'>$</span> <span class='hs-keyglyph'>\</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span>
<a name="line-162"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>s'</span><span class='hs-layout'>,</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>kv</span> <span class='hs-varid'>s</span>
<a name="line-163"></a> <span class='hs-layout'>(</span><span class='hs-varid'>s''</span><span class='hs-layout'>,</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>kf</span> <span class='hs-varid'>s'</span>
<a name="line-164"></a> <span class='hs-keyword'>in</span> <span class='hs-layout'>(</span><span class='hs-varid'>s''</span><span class='hs-layout'>,</span> <span class='hs-varid'>f</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span>
<a name="line-165"></a>
<a name="line-166"></a><a name="mapAccumR"></a><span class='hs-comment'>-- |The 'mapAccumR' function behaves like a combination of 'fmap'</span>
<a name="line-167"></a><span class='hs-comment'>-- and 'foldr'; it applies a function to each element of a structure,</span>
<a name="line-168"></a><span class='hs-comment'>-- passing an accumulating parameter from right to left, and returning</span>
<a name="line-169"></a><span class='hs-comment'>-- a final value of this accumulator together with the new structure.</span>
<a name="line-170"></a><span class='hs-definition'>mapAccumR</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Traversable</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-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-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-layout'>(</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span> <span class='hs-varid'>t</span> <span class='hs-varid'>c</span><span class='hs-layout'>)</span>
<a name="line-171"></a><span class='hs-definition'>mapAccumR</span> <span class='hs-varid'>f</span> <span class='hs-varid'>s</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>runStateR</span> <span class='hs-layout'>(</span><span class='hs-varid'>traverse</span> <span class='hs-layout'>(</span><span class='hs-conid'>StateR</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-varid'>s</span>
<a name="line-172"></a>
<a name="line-173"></a><a name="fmapDefault"></a><span class='hs-comment'>-- | This function may be used as a value for `fmap` in a `Functor` instance.</span>
<a name="line-174"></a><span class='hs-definition'>fmapDefault</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Traversable</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-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'>t</span> <span class='hs-varid'>b</span>
<a name="line-175"></a><span class='hs-definition'>fmapDefault</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>getId</span> <span class='hs-varop'>.</span> <span class='hs-varid'>traverse</span> <span class='hs-layout'>(</span><span class='hs-conid'>Id</span> <span class='hs-varop'>.</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span>
<a name="line-176"></a>
<a name="line-177"></a><a name="foldMapDefault"></a><span class='hs-comment'>-- | This function may be used as a value for `Data.Foldable.foldMap`</span>
<a name="line-178"></a><span class='hs-comment'>-- in a `Foldable` instance.</span>
<a name="line-179"></a><span class='hs-definition'>foldMapDefault</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Traversable</span> <span class='hs-varid'>t</span><span class='hs-layout'>,</span> <span class='hs-conid'>Monoid</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-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-180"></a><span class='hs-definition'>foldMapDefault</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>getConst</span> <span class='hs-varop'>.</span> <span class='hs-varid'>traverse</span> <span class='hs-layout'>(</span><span class='hs-conid'>Const</span> <span class='hs-varop'>.</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span>
<a name="line-181"></a>
<a name="line-182"></a><span class='hs-comment'>-- local instances</span>
<a name="line-183"></a>
<a name="line-184"></a><a name="Id"></a><span class='hs-keyword'>newtype</span> <span class='hs-conid'>Id</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Id</span> <span class='hs-layout'>{</span> <span class='hs-varid'>getId</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>a</span> <span class='hs-layout'>}</span>
<a name="line-185"></a>
<a name="line-186"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Functor</span> <span class='hs-conid'>Id</span> <span class='hs-keyword'>where</span>
<a name="line-187"></a> <span class='hs-varid'>fmap</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>Id</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Id</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span>
<a name="line-188"></a>
<a name="line-189"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Applicative</span> <span class='hs-conid'>Id</span> <span class='hs-keyword'>where</span>
<a name="line-190"></a> <span class='hs-varid'>pure</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Id</span>
<a name="line-191"></a> <span class='hs-conid'>Id</span> <span class='hs-varid'>f</span> <span class='hs-varop'><*></span> <span class='hs-conid'>Id</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Id</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span>
</pre></body>
</html>
