# Look and say sequence (J)

### From LiteratePrograms

**Other implementations**: C++ | dc | Eiffel | Haskell |**J**| Java | Lua | OCaml | Perl | PHP | Python | Ruby | Scala | sed | sh

## Contents |

# theory

This is a simple J script to generate look-and-say sequences such as the Conway sequence.

# practice

## looking and saying

We simply **count** the multiplicity of the **value** in each run,
and — following functional programming tradition —
**zip** the results together so they interleave.
Here we take full advantage of J's facilities for *tacit programming*;
in this case the distributive law that makes
`x (F G H) y`

equivalent to `(x F y) G (x H y)`

.

<<look and say>>=((count zipto value) first)

## ancillary definitions

In order to work on the runs,
first we must find the **first** element
of each run.
The expression **2=/\**
compares each pair (**2**) of elements for equality (**=**).
As the first element is certainly not equal to its predecessor,
we prepend a boolean false to the result (**0,**).
Finally, as we have just computed every element in a run but the first,
we negate (**-.**) the entire result.
This function does throw information away, but
here we take advantage of another *tacit programming* definition:
`(F G) y`

is equivalent to `y F (G y)`

,
allowing us to have both the processed and the original argument.

*NB. x and y are canonical J for left and right arguments, respectively, in a function definition*

<<defns>>=first=: monad : '-.0,2=/\y'

To **count** the multiplicity in each run, we first find the indices (**I.**)
where **first** has indicated the beginning of a run.
Similar to the verb train **count zipto value**,
here we have the train **I. , #**,
which concatenates (**,**) the previous result
to the length of the entire list (**#**).
Finally we take pairwise differences (**2-~/\**)
to find the length of each run.

*Question: why do we use flip ( ~) to reverse the sense of the subtraction?*

<<defns>>=count=: dyad : '2-~/\(I.,#)y'

Extracting the **value**s is dead simple:
we repeat (**#**) each element
of the left argument (our original array)
with a multiplicity
of the right argument (from **first**).
Because **first** returns a boolean array,
this results in a *projection* where we get either
0 or 1 copies of each element;
in fact, the final result will be
just one value per run. QEF

*Exercise: rewrite the definition of value using flip (~) *

*Question: do you understand the difference between the monadic (length) and dyadic (repeat) uses of the # operator?*

<<defns>>=value=: dyad : 'y#x'

**zipto** is equally trivial.
Although the zip of an array is equivalent to the transpose,
here we find it easier to simply use sideways composition (**,.**)
to paste the arrays together as columns,
and then ravel (**,**) the result back to a linear array.

<<defns>>=zipto=: dyad : ',x,.y'

# wrapping up

J does have an operator for iterating expressions
(and, given an argument of ,
it naturally produces a fixpoint)
but here we know we have an arbitrary unfolding
that never converges,
so we use a simple tail-recursive definition instead,
setting it to work on the numeric value (**".**)
of the input as a character array (**stdin ''**).
As **echo** is called purely for effect,
we use the **[** as a binary equivalent of the K combinator
— it ignores its right argument.

<<conway.ijs>>=loop=: monad : 'loop look and say y [ echo y' defns loop ". stdin ''

of course, if one prefers combinator form, it's possible to precompose the functions, resulting in a nearly point-free, much terser, definition:

loop=: monad : 'loop,@(((2&(-~/\))@(I.,#)@],.#~)(1,-.@(2&(=/\))))y[echo y' loop".stdin''

Finally, we try a few test cases.

look and say:

> echo -n 1 | jconsole conway.ijs | head -10 1 1 1 2 1 1 2 1 1 1 1 1 2 2 1 3 1 2 2 1 1 1 3 1 1 2 2 2 1 1 1 1 3 2 1 3 2 1 1 3 1 1 3 1 2 1 1 1 3 1 2 2 1 1 3 2 1 1 3 1 1 1 2 3 1 1 3 1 1 2 2 1 1

conway:

> echo -n 3 | jconsole conway.ijs | head -10 3 1 3 1 1 1 3 3 1 1 3 1 3 2 1 1 3 1 1 1 3 1 2 2 1 1 3 3 1 1 3 1 1 2 2 2 1 1 3 1 3 2 1 1 3 2 1 3 2 2 1 1 3 1 1 1 3 1 2 2 1 1 3 1 2 1 1 1 3 2 2 2 1 1 3 3 1 1 3 1 1 2 2 2 1 1 3 1 1 1 2 3 1 1 3 3 2 2 1 1 3

sole degeneracy:

> echo -n 2 2 | jconsole conway.ijs | head -10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

*Exercise: this is a nondegenerate degeneracy. Can you find the degenerate degeneracy?*

Download code |