deepseq-bounded-0.5.0: HTML/deepseq-bounded.html
<!DOCTYPE html>
<html>
<head>
<title>Bounded DeepSeq</title>
<link rel="stylesheet" href="style.css" />
</head>
<body>
<div class="main">
<!--
<p>
<br />
<span class="red">Hyperlinks aren't set up yet.</span>
<p>
<span class="red">The introductory part, at least, needs a rewrite!</span>
<p>
<span class="red">Also, am I going to stay with this convention of having the download links take up the first section of every such posting?</span>
<p>
<span class="red">The PatAlg section needs updating; which should probably wait until done these new ideas (Seqable, the P* PatNode's, the S* PatNode's).</span>
-->
<h2 style="margin-top: 50px;">Bounded Forcing</h2>
<!--
<h3>Download</h3>
Here's <a href="deepseq-bounded-1.3.0.2.tar.gz">full source</a> (BSD3-licensed, Cabal sdist) for:
<ul>
<li>building the library
<li>building the testbench corresponding to the examples in this post.
</ul>
<p>
On Hackage: <a href="http://hackage.haskell.org/package/deepseq-bounded">deepseq-bounded</a>
-->
<!--div>
<p>
<Haddock API <a href="api/html/deepseq-bounded/index.html">here</a>.
</div-->
The <a href="http://hackage.haskell.org/package/deepseq-bounded">deepseq-bounded</a> package provides two means of forcing a Haskell expression to an arbitrary but bounded depth, <tt>deepseqn</tt> and <tt>deepseqp</tt>.
As compared with plain <tt>seq</tt> (incremental forcing) and the beloved <tt>deepseq</tt> (full forcing), the bounded versions bridge the gap between these extremes.
<p>
Artificially forcing evaluation can be useful to relieve space leak, measure and tune performance, influence exception behaviour, make lazy I/O happen in a timely manner, and assure threads don't accidentally pass unevaluated computations to other threads ("time leak").
Bounded forcing (what this package offers) is necessary to work with streams, and other "infinite" datastructures, where plain <tt>rnf</tt>/<tt>deepseq</tt>/<tt>force</tt> will diverge.
<p>
<a id="dig03s" class="dig-toggle-show" href='javascript:toggle("dig03");' style="margin-left: 0px;">Show</a>
<div id="dig03" class="digression" style="margin-left: 0px;">
<a id="dig03h" class="dig-toggle-hide" href='javascript:toggle("dig03");'>Hide</a><p>
My particular motivation for <tt>deepseq-bounded</tt> is to support tool building for space leak characterisation (and provisional alleviation).
Readers interested in those aspects might like to have a look at <a href="http://hackage.haskell.org/package/seqaid">seqaid</a> and <a href="http://hackage.haskell.org/package/leaky">leaky</a>.
Space leak is still an Achilles' heel of Haskell, they're often fatally severe, and can be as hard to debug as anything you see in other languages.
With the present tools in use, it's fair to say Haskell space leak is more difficult to diagnose than pointer bugs in C/C++, being perhaps on a par with concurrent programming bugs (probably the most difficult class of bugs in all of contemporary computing).
People talk about strict-by-default Haskell in the future, but it remains there, and anyway, lazyness has its charm and strengths and is attractive to many.
</div>
<p>
The bounded forcing functions also have theoretical interest, spanning the <tt>seq</tt> / <tt>deepseq</tt> axis.
They can be considered in a broader context of, for instance, strictness analysis and evaluation transformers.
<h3>Library Design Overview</h3>
Following the tradition of the <a href="http://hackage.haskell.org/package/deepseq">deepseq</a> package, the <tt>NFDataN</tt> module contains a class <tt>NFDataN</tt>, with a method called <tt>rnfn</tt>, instances of which do the work of forcing bounded evaluation.
Additional functions <tt>deepseqn</tt> and <tt>forcen</tt> are provided, like in <tt>NFData</tt>.
<tt>NFDataP</tt> also follows this design.
<p>
The <tt>NFDataN</tt> module is straightforward; the familiar method and functions of <tt>DeepSeq</tt> have an '<tt>n</tt>' appended to their names, and take an integer first argument which is the minimum depth, in levels of recursion of constructor applications, to which to force evaluation.
<pre>
rnfn :: NFDataN a => Int -> a -> ()
deepseqn :: NFDataN a => Int -> a -> b -> b
forcen :: NFDataN a => Int -> a -> a
</pre>
<p>
It is important to note that this is a <em>minimum</em> bound only, since (for example) the runtime system may have speculatively evaluated more of the value already.
Such behaviour is deliberately unspecified, platform dependent, and outside of our control.
Also note likewise that, as per <tt>DeepSeq</tt>, no guarantees are made about order of evaluation in the above method and functions.
<p>
With <tt>NFDataP</tt>, the extent of evaluation is determined by a value of <tt>Pattern</tt> type.
One feature of <tt>NFDataP</tt> is the ability to <a href="#order">control order</a> of evaluation.
<p>
Usually a user of this library will prefer to compile their patterns from a string in the embedded pattern DSL, but the <tt>Pattern</tt> constructors can be worked with directly.
<p>
<a id="dig04s" class="dig-toggle-show" href='javascript:toggle("dig04");' style="margin-left: 0px;">Show</a>
<div id="dig04" class="digression" style="margin-left: 0px;">
<a id="dig04h" class="dig-toggle-hide" href='javascript:toggle("dig04");'>Hide</a><p>
<pre style="width: 800px;">
rnfp :: NFDataP a => Pattern -> a -> ()
deepseqp_ :: NFDataP a => Pattern -> a -> b -> b
forcep_ :: NFDataP a => Pattern -> a -> a
data Pattern = Node PatNode [Pattern]
data PatNode = WR | WS | WW | ...
deepseqp :: NFDataP a => String -> a -> b -> b
forcep :: NFDataP a => String -> a -> a
deepseqp = deepseqp_ . compilePat
forcep = forcep_ . compilePat
compilePat :: String -> Pattern
</pre>
</div>
<p>
More examples are given further down this page, but here is one example to illustrate the use of <tt>NFDataP</tt>.
There is no essential dependence on <tt>rnf</tt> (from <tt>DeepSeq</tt>), but it is available as <tt>*</tt> and helps to concoct an example.
<pre>
expr = ( undefined :: SomeType
, ( someValueWantToForce, [2,4..] )
, anotherValueWantToForce
)
forcep ".{#.{*#}*}" expr
= forcep_ ( compilePat ".{#.{*#}*}" ) expr
= forcep_ (Node WR [Node WI [],Node WR [Node WW [],Node WI []],Node WW []]) expr
</pre>
<p>
which can be translated as
<pre>
= let someval = someValueWeWantToForce
another = anotherValueWeWantToForce
in
rnf someval
`seq` rnf another
`seq` expr
</pre>
<p>
<div class="digression" style="padding-bottom: 0px;">
This final translation is actually not quite correct — <tt>forcep</tt> forces the spine of the paths from <tt>expr</tt> to the substructures we want to hammer with <tt>rnf</tt>, but this translation does not.
In particular, the pair constructor <tt>(,)</tt> for <tt>( someValueWantToForce, [2,4..] )</tt> is forced by <tt>forcep</tt>, but not by this translation.
<p>
This has no semantic impact, because it only concerns interior nodes, never leaves, and bottoms are always leaves.
It may burn a few more cycles to force paths, but it always produces the same value as the translation, given the same inputs.
</div>
<p>
The pattern <tt>".{#.{*#}*}"</tt> will match any ternary constructor, ignoring the first subexpression, completely forcing the third, and recursively matching subpattern <tt>".{*#}"</tt> on the middle subexpression.
<p>
It's worth emphasising that pattern-matching requires forcing constructors along the way.
That is to say, every node in the path from the root to a node being pattern-matched is already forced.
So the shape of these forcing functions is always a rooted tree, with the root node corresponding to the outermost redex of the expression being forced.
<h3>Formally</h3>
<!--span class="red">Is this correct only relative to an arbitrary but fixed value?</span-->
<p>
In general, the behaviour can be formalised
<!-- ≻ ≽ -->
<!-- ≻ ≽ -->
<pre>
b > a ⇒ forcen b ≻ forcen a -- (strict) monotonicity
∨ ∀ c > b . forcen c = forcen a -- convergence
</pre>
<p>
and
<pre>
patB ⊃ patA ⇒ forcep patB ≻ forcep patA
∨ ∀ patC ⊃ patB . forcep patC = forcep patB
</pre>
<p>
where <tt>f ≻ g</tt> says "<tt>f</tt> causes deeper evaluation than <tt>g</tt>".
<p>
Only strict monotonicity is interesting, since non-decreasing monotonicity <tt>≽</tt> is axiomatic:
you cannot unevaluate anything (push thunks back on the heap?...).
<h3>Parallelism</h3>
Varieties of <tt>PatNode</tt> to trigger <tt>Control.Parallel.par</tt> parallel evaluation are of interest.
This is supported by the new <tt>PR</tt>, <tt>PN</tt> and <tt>PW</tt> <tt>PatNode</tt> constructors.
In the DSL such nodes are represented by preceding them with an <tt>=</tt> character.
This is new work and not yet completely implemented, but it's very straightforward.
<p>
So, revisiting our example
<pre>
expr = ( undefined :: SomeType
, ( someValueWantToForce, [2,4..] )
, anotherValueWantToForce
)
forcep ".{#.{=*#}*}" expr
= forcep_ ( compilePat ".{#.{=*#}*}" ) expr
= forcep_ (Node WR [Node WI [],Node WR [Node PW [],Node WI []],Node WW []]) expr
</pre>
<p>
which translates approximately as
<a id="order"></a>
<pre>
= let someval = someValueWeWantToForce
another = anotherValueWeWantToForce
in
rnf someval
`par` rnf another -- note `par` (not `seq`)
`seq` expr
</pre>
<p>
In particular, <tt>rnf someval</tt> will be sparked in parallel with the remainder of the forcing (<tt>rnf another</tt>).
<h3>Controlling Evaluation Order</h3>
We've noted that <tt>seq</tt> makes no guarantees about order of evaluation of its arguments.
This is concisely explained in the <a href="http://hackage.haskell.org/package/parallel-3.2.0.5/docs/Control-Parallel.html">Control.Parallel</a> API document.
Plain <tt>seq</tt> is strict in its second argument, so the evaluation semantics for <tt>x `seq` y</tt> amount to no guarantees at all about the order in which <tt>x</tt> and <tt>y</tt> are evaluated.
Evaluation of <tt>x</tt> and <tt>y</tt> is probably interleaved, in general.
<p>
In the previous section, we saw how to force parallel evaluation in <tt>NFDataP</tt> using <tt>par</tt> from <tt>Control.Parallel</tt>.
It is also possible to enforce sequencing of computations by leveraging the other primitive of <tt>Control.Parallel</tt>, namely <tt>pseq</tt>:
<pre>
pseq x y = x `seq` lazy y
</pre>
<p>
where <a href="http://hackage.haskell.org/package/base-4.7.0.1/docs/GHC-Exts.html#v:lazy"><tt>lazy</tt></a> is a GHC primitve that prevents strictness of the second argument.
In fact <tt>lazy</tt> is one of just two definitions living in the internal module <tt>GHC.Magic</tt> in the GHC source (the other is <tt>inline</tt>).
Quoting from the source in <a href="http://hackage.haskell.org/package/base/docs/src/GHC-Conc-Sync.html#pseq">base</a>
<pre>
-- The reason for the strange "lazy" call is that
-- it fools the compiler into thinking that pseq and par are non-strict in
-- their second argument (even if it inlines pseq at the call site).
-- If it thinks pseq is strict in "y", then it often evaluates
-- "y" before "x", which is totally wrong.
</pre>
<h3 id="fusion">Fusion</h3>
Little has been done so far to tune performance.
<p>
Several fusion rules are in effect.
For <tt>NFDataN</tt> we have
<pre>
{-# RULES
"rnfn/composition"
forall n1 n2 x. (.) (rnfn n2) (rnfn n1) x = rnfn (max n1 n2) x
#-}
</pre>
<p>
and for <tt>NFDataP</tt> we have
<pre>
{-# RULES
"rnfp/composition"
forall p1 p2 x. (.) (rnfp p2) (rnfp p1) x = rnfp ( unionPat [p1, p2] ) x
#-}
</pre>
<p>
Other rules are probably possible (considering <a href="#patalg">PatAlg</a>), and may have been implemented since the last time this section was updated.
<p>
Unfortunately I get GHC warnings for all my rules, such as
<pre>
Rule "forcen/composition" may never fire
because `.' might inline first
Probable fix: add an INLINE[n] or NOINLINE[n] pragma on `.'
</pre>
<p>
and it's not clear to me how to put an <tt>INLINE</tt> pragma
on base composition.
<p>
<a id="dig01s" class="dig-toggle-show" href='javascript:toggle("dig01");' style="margin-left: 0px;">Show</a>
<div id="dig01" class="digression" style="margin-left: 0px;">
<a id="dig01h" class="dig-toggle-hide" href='javascript:toggle("dig01");'>Hide</a><p>
There haven't been many cases of pattern composition coming up so far, except those deliberately written for the tests.
Also, given the amount of pattern-matching required by unionPat, it's far from certain that this rule will improve performance.
If the union could be computed once at compile-time (for static patterns only, of course) it would make a lot more sense.
This could be useful, since <tt>seqaid</tt> is going to output optimised, static patterns for ancillary use in subsequent builds.
But then seqaid might as well also compute and output the union itself.
</div>
<p>
Optimisations will get more attention in the next round of development.
<!-- hide/show
<h3>Fusion, and Misguided Digression on Order of Evaluation</h3>
<div class="outdated">
<div class="red">
LATER YET: Actually, check out Control.Parallel ( par, pseq ) which
were designed exactly to extend seq to give stronger guarantees
about order of evaluation.
</div><div class="red">
LATER: I think what follows is not right; we cannot control order of evaluation so easily...
So can relax about this, and add a fusion rule to combine the patterns (using NFDataP.unionPat).
<pre style="background-color: transparent;">
{-# RULES
"rnfp/composition" forall p1 p2 x. (.) (rnfp p2) (rnfp p1) x = rnfp ( unionPat [p1, p2] ) x
#-}
</pre>
</div>
<p>
Another thing which distinguishes NFDataP from NFDataN (and NFData) is that we can now control order of evaluation, in case that matters.
This we do by composing applications:
<pre>
-- Note that patA and patB must intersect on (,), both matching ".",
-- in order for the subpatterns to get applied.
( forcep patA . forcep patB ) ( value :: (A, B) )
</pre>
<p>
This will first force B (to the extent matched by patB), and then force A (to extent of patA).
The net effect does not depend or the order, provided no subexpression is undefined or non-terminating.
<p>
Controlling order of evaluation this way is probably a bit fragile, since the compiler may reorder things through optimisation, but — as composition does not normally commute in general — the reordering that would hurt us is unlikely to be performed.
<p>
It might actually be nice to get GHC to recognise opportunities for re-ordering, since the potential for optimisation is likely more important than controlling evaluation order! Perhaps this is possible with the GHC RULES pragma, but care would have to be taken to assure confluent rewriting (or at least bounding the number of recursive rule applications), which is a problem faced with most uses of GHC RULES.
</div>
-->
<h3 id="generic-deriving">Generic Deriving is Supported</h3>
The <tt>GNFDataN</tt> and <tt>GNFDataP</tt> classes support automatic derivation of instances of <tt>NFDataN</tt> and <tt>NFDataP</tt> for arbitrary types, <span style="white-space: nowrap;">using SOP (<a href="http://hackage.haskell.org/package/generics-sop">generics-sop</a></span></tt>), a relatively new generics library.
Latterly, <tt>Seqable</tt> supports all types via SOP, and there is no <tt>Seqable</tt> class, only generic functions.
This is an attractive alternative to wrestling with divers classes and constraints — one need only worry about one class constraint (Generics.SOP.Generic), instances of which are readily derived.
<!--<tt>GNFDataN</tt> has been implemented in two ways, once using standard <tt>GHC.Generics</tt> (analogously to <a href="http://hackage.haskell.org/package/deepseq-generics">deepseq-generics</a> package), and then again using
By default (in the <tt>.cabal</tt> file), SOP is used.
(However, the only implementation of <tt>GNFDataP</tt> is using SOP.)-->
<!-- Standard generic deriving using <tt>GHC.Generics</tt> is well-documented at <a href="">deepseq-generics</a>, and illustrated in the test suite of this package.
With it, there is one minor glitch still, but the correspondence of the depth parameter to actual depth in the structure is almost exact.-->
<p>
Strict monotonicity is assured, until convergence to full evaluation (for finite values).
With <tt>GNFDataN</tt>, increasing the depth parameter will strictly increase the amount of forced evaluation, in a level-by-level manner within the shape of the value.
Likewise, with <tt>GNFDataP</tt>, extending the pattern shape within the term shape will strictly increase the forcing.
<p>
<!--As for <tt>GNFDataP</tt>, only an SOP generics implementation is provided.
(It seems unlikely that <tt>GHC.Generics</tt> will suffice, as they explicitly state that nesting shape is unspecified and prone to optimising rewrites.)-->
<p>
To derive instances of <tt>NFDataN</tt> only, you can do:
<pre>
{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeFamilies #-}
import Generics.SOP.TH
import Control.DeepSeq.Bounded ( NFDataN(..), grnfn )
data TA = A1 TB | A2
instance NFDataN TA where rnfn = grnfn
data TB = B1 Int TA
instance NFDataN TB where rnfn = grnfn
deriveGeneric ''TA
deriveGeneric ''TB
</pre>
<p>
<a id="dig02s" class="dig-toggle-show" href='javascript:toggle("dig02");' style="margin-left: 0px;">Show</a>
<div id="dig02" class="digression" style="margin-left: 0px;">
<a id="dig02h" class="dig-toggle-hide" href='javascript:toggle("dig02");'>Hide</a><p>
To derive instances of <tt>NFDataP</tt> for a data type (which requires also instances of superclasses <tt>NFDataN</tt> and of <tt>NFData</tt>), the incantation is:
<pre>
{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DeriveDataTypeable #-}
import Generics.SOP.TH
import Control.DeepSeq.Bounded ( NFDataN(..), grnfn, NFDataP(..), grnfp )
import Control.DeepSeq.Generics ( NFData(..), genericRnf )
import GHC.Generics ( Generic ) -- for deriving NFData
import Data.Typeable ( Typeable ) -- for name-constrained pattern nodes
data TA = A1 TB | A2 deriving ( Show, Generic, Typeable )
instance NFData TA where rnf = genericRnf
instance NFDataN TA where rnfn = grnfn
instance NFDataP TA where rnfp = grnfp
data TB = B1 Int TA deriving ( Show, Generic, Typeable )
instance NFData TB where rnf = genericRnf
instance NFDataN TB where rnfn = grnfn
instance NFDataP TB where rnfp = grnfp
deriveGeneric ''TA
deriveGeneric ''TB
</pre>
</div>
<p>
Note that mutually-recursive data types require all their <tt>deriveGeneric</tt> calls to come below their collective definitions.
<p>
SOP also offers an alternative approach to automatic instance derivation, piggybacking on <tt>GHC.Generics</tt>, in case Template Haskell is unacceptable in your application.
<p>
It might be worth noting that the <a href="http://hackage.haskell.org/package/seqaid">seqaid</a> package provides a mechanism for completely automating this process.
However, it depends on use of a preprocessor, and was deemed inappropriate for this core library.
<h3 id="patalg">Pattern Algebra</h3>
In the course of developing <tt>NFDataP</tt>, several utility functions were written for creating, modifying and combining patterns.
They've been collected in the <tt>PatAlg</tt> module.
<pre>
module Control.DeepSeq.Bounded.PatAlg
import Control.DeepSeq.Bounded.Pattern
<b>Basic operations on Patterns</b>
<span style="font-size: 95%;"><em>-- Compute the union of a list of </em>Pattern<em>s.</em></span>
<b style="color: #333;">unionPats :: [ Pattern ] -> Pattern</b>
<span style="font-size: 95%;"><em>-- Compute the intersection of a list of </em>Pattern<em>s.</em></span>
<b style="color: #333;">intersectPats :: [ Pattern ] -> Pattern</b>
<span style="font-size: 95%;"><em>-- Return </em>True<em> if the first pattern matches the second
-- (and </em>False<em> otherwise). Note that matching does not imply
-- spanning. Equality </em>(==)<em> or </em>flip isSubPatOf<em> will
-- work there, depending on your intentions.</em></span>
<b style="color: #333;">isSubPatOf :: Pattern -> Pattern -> Bool</b>
<b>Operations for obtaining and modifying Patterns based on a term</b>
<span style="font-size: 95%;"><em>-- Obtain a lazy pattern, matching the shape of
-- an arbitrary term (value expression).
-- Interior nodes will be </em>WR<em>, and leaves will be </em>WS<em>.</em></span>
<b style="color: #333;">mkPat :: forall d. Data d => d -> Pattern</b>
<span style="font-size: 95%;"><em>-- Obtain a lazy pattern, matching the shape of
-- an arbitrary term, but only down to at most depth </em>n<em>.
-- Interior nodes will be </em>WR<em>. Leaf nodes will be </em>WS<em> if they
-- were leaves in the host value; otherwise they will be </em>WR<em>.
-- Satisfies </em>forcep . mkPatN n = forcen n<em>.</em></span>
<b style="color: #333;">mkPatN :: forall d. Data d => Int -> d -> Pattern</b>
<span style="font-size: 95%;"><em>-- Grow all leaves by one level within the shape of the provided value.</em></span>
<b style="color: #333;">growPat :: forall d. Data d => Pattern -> d -> Pattern</b>
<b>Operations for obtaining subpatterns (in the 'isSubPatOf' sense)</b>
<span style="font-size: 95%;"><em>-- Given an integer depth and a pattern, truncate the pattern to
-- extend to at most this requested depth.</em></span>
<b style="color: #333;">truncatePat :: Int -> Pattern -> Pattern</b>
<span style="font-size: 95%;"><em>-- Elide all leaves which have no non-leaf sibling.
-- We want the pattern to still match the same value, only less of it.
-- Merely eliding all leaves would, in most cases, cause match failure,
-- so we have to be a bit more subtle.</em></span>
<b style="color: #333;">shrinkPat :: Pattern -> Pattern</b>
<b>Operations for the direct construction and perturbation of Patterns</b>
<span style="font-size: 95%;"><em>-- There is no Nil in the Pattern type, but a single </em>WI<em> node as
-- empty pattern is a dependable way to assure the empty pattern
-- never forces anything.</em></span>
<b style="color: #333;">emptyPat :: Pattern</b>
<span style="font-size: 95%;"><em>-- This creates a new </em>WR<em> node, the common root. The argument patterns
-- become the children of the root (order is preserved).</em></span>
<b style="color: #333;">liftPats :: [ Pattern ] -> Pattern</b>
<span style="font-size: 95%;"><em>-- Introduce siblings at a node (interior or leaf) of the target.
-- The first argument is target, the second is a path, and the
-- third is a list of subpatterns for insertion, along with the
-- indices of the child before which to insert.</em></span>
<b style="color: #333;">splicePats :: Pattern -> [Int] -> [ (Int, Pattern) ] -> Pattern</b>
<span style="font-size: 95%;"><em>-- Elide siblings at a node (interior or leaf) of the target.
-- The first argument is target, the second is a path, and the
-- third is a list of child indices for elision.</em></span>
<b style="color: #333;">elidePats :: Pattern -> [Int] -> [Int] -> Pattern</b>
<span style="font-size: 95%;"><em>-- Select a leaf at random, and elide it. In order to achieve fairness,
-- the node probabilities are weighted by nodes in branch. The path
-- arg can "focus" the stochastic erosion to only consider leaves
-- beneath a given node.</em></span>
<b style="color: #333;">erodePat :: StdGen -> [Int] -> Pattern -> (Pattern, StdGen)</b>
</pre>
<h3>Examples</h3>
More examples can be browsed in the <a href="tests.html">testing output</a>.
Here we only touch on a few particulars.
<!--
<p>
The following abbreviation is used frequently in the examples:
<pre>
__ = undefined
</pre>
<p>
Also, suppose the following data types have NFDataP instances (refer to the <a href="#generic-deriving">Generic Deriving</a> section above).
<pre>
data TA = A1
| A2 (TB Complex,Int)
| A3 TA Bool (TB String)
data TB a = B1
| B2 [a]
| B3 [TA]
</pre>
-->
<p>
First, note that we can handle infinite values, unlike <tt>deepseq</tt>.
<pre>
force $ take 5 [1,2..] -- [1,2,3,4,5]
take 5 $ force [1,2..] -- << nonterminates >>
forcen 100 $ take 5 [1,2..] -- [1,2,3,4,5]
take 5 $ forcen 100 [1,2..] -- [1,2,3,4,5]
</pre>
<p>
Oops, never finished this section...
And that's a pretty silly example, although it illustrates the distinction.
Best to refer to the tests for examples, or just play around.
Will try to toss in a few more scraps...
<p>
Here is the result of iterating <tt>shrinkPat</tt> on a test pattern.
<pre>
".{.{#.{*.{.*3}}}.{..{*1.{..{##}}}}}"
".{.{#.{*5.{#*2}}}.{#.{#.{##}}}}"
".{.{#.{*4.{#.}}}.{#.{##}}}"
".{.{#.{*3.{##}}}.{##}}"
".{.{#.{*2#}}#}"
".{.{#.{.#}}#}"
".{.{#.{##}}#}"
".{.{##}#}"
".{##}"
"#"
"#"
</pre>
<div class="footer" style="margin-top: 50px;">
Andrew Seniuk
<br>
July 13, 2014
<br>
<tt>rasfar@gmail.com</tt>
</div>
</div>
<script language="javascript">
function toggle(id1){
var ele_s = document.getElementById(id1+"s");
var ele_h = document.getElementById(id1+"h");
var ele = document.getElementById(id1);
if( ele.style.display == "inline-block" ){
ele.style.display = "none";
ele_s.style.display = "inline-block";
ele_h.style.display = "none";
}else{
ele.style.display = "inline-block";
ele_s.style.display = "none";
ele_h.style.display = "block";
}
}
</script>
</body>
</html>