<div dir="ltr"><div>Getting stuck in <i>Real World Haskell</i>'s chapter on pretty printing (chap 5), I decided to take a look at one of the suggested sources, i.e., John Hughes' <i><a href="https://www.researchgate.net/publication/226525714_The_Design_of_a_Pretty-printing_Library">The Design of a Pretty-printing Library</a></i>. Not that I fully got the first three section, still, let me skip ahead to section 4, <i>Designing a Sequence Type </i>where we're designing a supposedly generic sequence type, I'm guessing in the same universal, fundamental way that Peano's Axioms give a generic underpinning of the natural numbers. Good. I get it. This is why Haskell is unique. So he says we take the following <i>signature</i> as our starting point</div><div><br></div><div><font face="monospace">nil :: Seq a<br>unit :: a -> Seq a<br>cat :: Seq a -> Seq a -> Seq a<br>list :: Seq a -> [a]<br></font></div><br clear="all"><div>where <font face="monospace">nil , unit ,</font> and <font face="monospace">cat </font>give us ways to build sequences, and <font face="monospace">list</font> is an <i>observation </i>[explained before]. The correspondence with the usual list operations is</div><div><br><font face="monospace">nil = []<br>unit x = [x]<br>cat = (++)</font></div><div><br>These operations are to satisfy the following laws:</div><div><br><font face="monospace">xs `cat` ( ys `cat` zs ) = ( xs `cat` ys ) `cat` zs<br>nil `cat` xs = xs<br>xs `cat` nil = xs<br>list nil = []<br>list ( unit x `cat` xs ) = x : list xs</font><br></div><div><br></div><div>My first question is why must we satisfy these laws? Where did these laws come from? Is this a universal truth thing? I've heard the word <i>monoid </i>and <i>semigroup</i> tossed around. Is this germane here?<br></div><div><br></div><div>Next in <i>4.1 Term Representation</i> I'm immediately lost with the concept of <i>term. </i>On a hunch, I borrowed a book <i>Term Rewriting and All That </i>from Baader and Nipkow which I'm sure goes very deep into the concept of terms, but I'm not there yet. What is meant by <i>term</i>? As 4.1 continues, confusing is this passage</div><div><br></div><div>The most direct way to represent values of [the?] sequence type is just as terms of the<br>algebra [huh?], for example using</div><div><br><font face="monospace">data Seq a = Nil j Unit a j Seq a `Cat` Seq a</font></div><div><br>But this trivial representation does not exploit the algebraic laws that we know to<br>hold [huh?], and moreover the list observation will be a little tricky to de ne (ideally we would like to implement observations by very simple, non-recursive functions: the real work should be done in the implementations of the Seq operators themselves). Instead, we may choose a restricted subset of terms -- call them simplified forms -- into which every term can be put using the algebraic laws. Then we can represent sequences using a datatype that represents the syntax of simplified forms.</div><div><br>In this case, there is an obvious candidate for simplified forms: terms of the form <font face="monospace">nil </font>and <font face="monospace">unit x `cat` xs</font> , where <font face="monospace">xs</font> is also in simplified form. Simplified forms can be represented using the type</div><div><br></div><div><span style="font-family:monospace">data Seq a = Nil j a `UnitCat` Seq a</span></div><div><font face="monospace"><br></font>with the interpretation</div><div><br><font face="monospace">Nil = nil<br>x `UnitCat` xs = unit x `cat` xs</font><br></div><div><font face="monospace"><br></font></div><div><font face="arial, sans-serif">All of this presupposes much math lore that I'm hereby asking someone on this mailing list to point me towards. I threw in a few [huh?] as specific points, but in general, I'm not there yet. Any explanations appreciated.</font></div><div><br></div><br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div>⨽<br></div>Lawrence Bottorff<div>Grand Marais, MN, USA</div><div><a href="mailto:borgauf@gmail.com" target="_blank">borgauf@gmail.com</a></div></div></div></div>