in

Type-level constraints in Haskell


[*]

I’m trying to encode term algebra as a data type in Haskell for further use in an algorithm. By term algebra I mean a set of terms which are either variables or functions applied to other terms. The functions with zero arguments are constants (but that’s actually does not matter here).

Firstly, one would need the following GHC language extensions to replicate my code:

{-# LANGUAGE GADTs, DataKinds,
TypeApplications,
TypeFamilies,
TypeOperators,
StandaloneKindSignatures,
UndecidableInstances#-}

and the following imports:

import qualified GHC.TypeLits as GTL
import Data.Kind

The direct way to encode terms (the first one I took):

data Term where
  Var :: String -> Term
  Func :: String -> Integer -> [Term] -> Term

where by String I want to encode the name, by Integer the arity and by [Terms] the list of arguments of a function.
Then I want to be sure that the list of terms as arguments have the same length as an arity.[*]
The first idea is to use smart constructors, but I would like to encode such constraints on a type level. So the second idea would be to create type-level naturals, lists of a specified length and the data type where these numbers coincide:

data Z = Z
data S a = S a

data List n a where
    Nil  :: List Z a
    Cons :: a -> List m a -> List (S m) a

data WWTerm where
  WWVar :: String -> WWTerm
  WWFunc :: String -> m -> List m WWTerm -> WWTerm

My question here is the following: is there a way to impose type-level constraints using ordinary lists at the same time via 1) creating special type-families, 2) creating special type classes, or 3) via constraints in data types?

Regarding my attempts, I wrote the following:

type MyLength :: [Type] -> GTL.Nat
type family MyLength xs where
  MyLength '[] = 0
  MyLength (x':xs) = 1 GTL.+ (MyLength xs)

data QFunc n l where
  QFunc :: (MyLength l ~ n) => String -> (n :: GTL.Nat) -> l -> QFunc n l

Unfortunately, this part of code doesn’t compile for the following reasons:

Expected a type, but ‘n :: Nat’ has kind ‘Nat’
...

Expected a type, but ‘l’ has kind ‘[*]’
...

Are there any thoughts on how to approach my goal?

[*]
[*] Source: https://stackoverflow.com/questions/70721758/type-level-constraints-in-haskell

easily convert Python notebook to web app and share with others

How Slack Modernized its Mobile Apps and Went Full Swift on iOS