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
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
that we could use to reverse a Thrist.
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
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.