I’ve been collaborating with Gabor Greif on a new version of his ‘thrist’ module, which was just released last night! I approached Gabor with some new ideas that came to me as I was writing a module that uses Thrists heavily, and he invited me to co-author this version. (See below for a brief explanation of Thrists).

I noticed that in the previous version, the function `foldThrist`

was
essentially a `foldr`

with a type signature that was overly restrictive.

For instance, one *could not* define an identity function on Thrists in terms
of the foldThrist function, the way one can with regular lists, e.g.:

```
foldr (:) [] [1..4] == [1,2,3,4]
```

Other additions followed as I tried to define the Thrist equivalent of many
useful list functions. For example I wanted to define a `foldl`

-like function
that we could use to reverse a Thrist.

Check out the release announcement on Gabor’s blog, along with his draft paper on Thrists.

### A Brief Thrist Primer

A Thrist is a **type-threaded list**. This is easiest explained with an
example:

```
*Data.Thrist> :t Cons (True,'z')$ Cons ('a',"bar")$ Cons ("foo",3.14) Nil
Cons (True,'z')$ Cons ('a',"bar")$ Cons ("foo",3.14) Nil :: (Fractional c)=> Thrist (,) Bool c
```

As you can see, unlike the regular haskell list type which takes a single type
for each element, the Thrist takes a single *binary type* (in the case above
we have the tuple type:`(,)`

) for each element, whose type arguments are
*chained* together. So the *second* type argument of one cell must be the same
type as the *first* type argument of the following cell, and so on.

The two arguments that are visible in the outer Thrist type itself are the
first argument of the first cell, and the second argument of the last cell. In
the example above those would be `Bool`

(taken from the `True`

value fst of
the head of our Thrist), and some as-yet-undetermined `Fractional`

type (our
3.14 value).

This type of cool data structure is only possible because of
GADTs which let us enforce the
type-threading and allow us to have all these types *inside the Thrist*
without having them show up in the type signature.

Here is how the Thrist GADT is defined:

```
data Thrist :: (* -> * -> *) -> * -> * -> * where
Nil :: Thrist (~>) a a
Cons :: (a ~> b) -> Thrist (~>) b c -> Thrist (~>) a c
```

Here is another example of a Thrist in which the binary type element is a
*function*:

```
*Data.Thrist> :t Cons head $ Cons fst $ Cons not Nil
Cons head $ Cons fst $ Cons not Nil :: Thrist (->) [(Bool, b)] Bool
```

It might look odd to see `(->)`

used by itself as an argument to a type
signature, but a Thrist of functions is actually pretty cool. We can actual
fold the Thrist using function composition:

```
*Data.Thrist> :t foldl1Thrist (flip (.)) $ Cons head $ Cons fst $ Cons not Nil
foldl1Thrist (flip (.))$ Cons head $ Cons fst $ Cons not Nil :: [(Bool, b)] -> Bool
```

Notice how similar the Thrist definition is to the composed function. You can see how the Thrist generalizes function composition to a certain extent.