New version of 'thrist' package released

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.