## Haskell code to naively list orthobraces

Let’s see some simple Haskell code to generate orthobraces, by generating all sequences and throwing away ones we’ve already generated.

First, some library imports we’ll need.

``````> import Data.List
> import qualified Data.Set as S
``````

Here’s a function to generate all sequences with $n+4$ `X`s and $n$ `V`s.

``````> -- @orthoseqs n@ generates all length 2n+4 *sequences* with n+4 X's and
> -- n V's.
> orthoseqs :: Int -> [[Char]]
> orthoseqs n = go (n+4) n
``````

`orthoseqs` works by calling a recursive helper function `go`, which keeps track of how many `X`s and how many `V`s still need to be generated.

``````>   where
>     go 0 v = [replicate v 'V']
>     go x 0 = [replicate x 'X']
``````

If the number of `X`s or `V`s remaining is $0$, we just output the right number of copies of the other letter.

``````>     go x v = map ('X':) (go (x-1) v) ++ map ('V':) (go x (v-1))
``````

Otherwise, we recursively generate all strings with $x-1$ `X`’s and $v$ `V`’s, and put an `X` on the front of each; and similarly for strings with a `V` at the beginning.

Let’s try it:

``````ghci> orthoseqs 0
["XXXX"]

ghci> orthoseqs 1
["XXXXXV","XXXXVX","XXXVXX","XXVXXX","XVXXXX","VXXXXX"]

ghci> length (orthoseqs 2)
28

ghci> length (orthoseqs 3)
120
``````

This looks right and seems to match up with the numbers we computed last time.

Now, to throw out sequences which are equivalent up to rotation and/or reversal, the easiest way is to write a function `canonicalize` which computes a canonical representative from each equivalence class: in particular, given a sequence, it computes the lexicographically smallest (that’s a fancy way of saying “comes first in dictionary order”) sequence which is equivalent to it.

``````> canonicalize :: Ord a => [a] -> [a]
> canonicalize as = minimum (rots as ++ rots (reverse as))
``````

`canonicalize` just finds the minimum sequence among all rotations of `as` and rotations of `reverse as`.

``````>   where
>     rots xs = map (take n) . take n . tails \$ xs ++ xs
>       where
>         n = length xs
``````

To generate all rotations, we do a little list manipulation: `xs ++ xs` puts two copies of `xs` together end to end; `tails` produces something like this:

``````ghci> xs = [1,4,5]
ghci> tails (xs ++ xs)
[[1,4,5,1,4,5],[4,5,1,4,5],[5,1,4,5],[1,4,5],[4,5],,[]]
``````

Then we take just the first $n$ results of `tails` and take only the first `n` elements of each, like so:

``````ghci> map (take 3) . take 3 . tails \$ xs ++ xs
[[1,4,5],[4,5,1],[5,1,4]]
``````

Now we can write `orthobraces` fairly simply: generate all sequences, canonicalize each (resulting in a bunch of duplicates), then put them into a set (which gets rid of duplicates) and list the elements of the set.

``````> -- @orthobraces n@ generates all length 2n+4 *bracelets* with n+4 X's
> -- and n V's.  That is, one representative is generated for each
> -- bracelet, up to reflection and rotation.
> orthobraces :: Int -> [[Char]]
> orthobraces = S.toList . S.fromList . map canonicalize . orthoseqs
``````

Let’s try it:

``````ghci> orthobraces 0
["XXXX"]

ghci> orthobraces 1
["VXXXXX"]

ghci> orthobraces 2
["VVXXXXXX","VXVXXXXX","VXXVXXXX","VXXXVXXX"]

ghci> orthobraces 3
["VVVXXXXXXX","VVXVXXXXXX","VVXXVXXXXX","VVXXXVXXXX","VXVXVXXXXX","VXVXXVXXXX","VXVXXXVXXX","VXXVXXVXXX"]

ghci> map (length . orthobraces) [0..6]
[1,1,4,8,29,79,280]
``````

It seems to work! As we already discussed last time, this is not a particularly efficient way to generate orthobraces, since we end up spending most of our time throwing away duplicates (and what’s worse, even the proportion of time spent throwing away duplicates increases as $n$ increases). But it’s rather simple to write and test, and can serve as a good reference implementation to compare other implementations against. 