Where to find fancy type utilities?

I’m mixing some fun magic in my cauldron over here (details below), and I’m in need of a few utility types and functions. But I do not know where to find these if they exist, where to make PRs if libraries that do this sort of thing exist (but perhaps don’t address my specific needs), or where to put these definitions myself so that other people can find them. Hoogle is markedly less helpful in finding types of a certain shape than for finding functions with a certain type.

The two utilities I need this particular moment are

type List = []  -- avoid punning

-- | An indexed-heterogeneous list @FList f xs@, where each element has the same type @f@ but
-- with a different index @xs@.
type FList :: forall k. (k -> Type) -> List k -> Type
data FList f xs where
  FNil :: FList f '[]
  (:>>) :: f x -> FList f xs -> FList f (x : xs)
infixr 5 :>>

-- | Convert the representation of a list of compile-time data to a list of representations
typeRepList :: TypeRep @(List k) xs -> FList TypeRep xs
typeRepList = ...

Has anyone spotted these beasts in the wild? Any advice on how I might track them down? If I wish to release these beasts myself, any advice on where I should put them so others can find them?

If you’re curious, the magic I’m cooking is to allow the ability to look up and use class instances at runtime, so that if you know the name of a type (as a Text), you can get and use instances for that type. Note in [this StackOverflow post]Deserializing to different types at runtime in haskell - Stack Overflow), the first comment on the original post says “This can not be achieved, I think.” When I see someone say that about an idea in Haskell, I take it as a direct challenge. :slight_smile:

4 Likes

Well, I’ve kept looking, and I found.

  • https://hackage.haskell.org/package/type-combinators is basically what I’m looking for, but it doesn’t have the specific type I’m looking for, and appears unmaintained. Nevertheless, there are some good things in there!
  • https://hackage.haskell.org/package/parameterized-utils has my FList type! (It’s Data.Parameterized.List.List.) I think I will use that. (Drawback: parameterized-utils has a lot of dependencies, which I don’t really need.)
  • parameterized-utils.Data.Parameterized.Map.MapF and dependent-map.Data.Dependent.Map.DMap seem to be interchangeable. Both seem maintained. Is one better than the other? I don’t know. I found dependent-map first when I needed such a thing earlier in my work. But it makes me slightly sad that both of these types exist, when I think we should standardize around just one of them. I know this kind of thing is unavoidable, but it is yet more evidence that we need a better way to search for fancy types, so as to avoid duplication in the future.

Also, the only reason that I found parameterized-utils is that I had encountered it in the past. Searching today did not discover it.

2 Likes

For that kind of heterogeneous list I turn to the NP datatype from sop-core. The package provides a rich API and has very few dependencies.

In particular, the cpure_NP function might help writing something a bit like typeRepList:

ghci> import Data.SOP
ghci> import Data.SOP.NP
ghci> import Type.Reflection
ghci> :t cpure_NP (Proxy @Type.Reflection.Typeable) typeRep
cpure_NP (Proxy @Type.Reflection.Typeable) typeRep
  :: forall {k} {xs :: [k]}. All Typeable xs => NP TypeRep xs
ghci> cpure_NP @_ @[Int, Bool, Char] (Proxy @Type.Reflection.Typeable) typeRep
Int :* Bool :* Char :* Nil

One difference however is that the signature for TypeRep @(List k) xs -> FList TypeRep xs doesn’t require an All Typeable xs constraint, I guess because that’s implicit in the TypeRep argument? Perhaps something like ana_NP could help instead, but I’m not sure.

Edit. How about this:

typeRepList ::
  forall k (xs :: [k]).
  Data.SOP.SListI xs =>
  TypeRep xs ->
  NP TypeRep xs
typeRepList = ana_NP unconsRep

unconsRep ::
  forall k (x :: k) (xs :: [k]).
  TypeRep (x ': xs) ->
  (TypeRep x, TypeRep xs)
unconsRep z =
  let (_, sr : srs : []) = splitApps z
      r = case sr of
        SomeTypeRep z -> unsafeCoerce z
      rs = case srs of
        SomeTypeRep z -> unsafeCoerce z
   in (r, rs)

main :: IO ()
main = print $ typeRepList (typeRep @[Bool, Int, Char])

But I couldn’t make it work without the unsafeCoerces.