Weaken GADTs type constraints to deal with unpredictable data

Question

I am trying to make use of GADTs to have well constrained types, but some dependencies are impossible to handle during compilation time – for example user input. Let's consider following AVL tree definition:

data Zero
data S a

data AVL depth where
  Nil :: AVL Zero
  LNode :: AVL n -> Int -> AVL (S n) -> AVL (S (S n))
  RNode :: AVL (S n) -> Int -> AVL n -> AVL (S (S n))
  MNode :: AVL n -> Int -> AVL n -> AVL (S n)

Magic of GADTs ensures that every AVL tree is well balanced. I can define some basic functions like

singleton :: a -> AVL (S Zero) x
singleton a = MNode Nil a Nil

insert :: a -> AVL n a -> AVL (S n) a
insert = ...

Now I would like to write program that will read n numbers, insert them into AVL tree and return in order (assuming that these functions are defined):

main = IO ()
main = do
  (n :: Int) <- readInt  -- some IO defined somewhere
  (inp :: [Int]) <- readInts
  let avl = foldl (\tree x -> insert x tree) Nil inp
  print $ toList avl

And obviously I get error:

    • Couldn't match type ‘S Zero’ with ‘Zero’
      Expected type: AVL Zero
        Actual type: AVL (S Zero)

because type (depth) of the tree is going to change along with every insert. I understand what is happening here, but I don't see any reasonable way to use this AVL while handling input "online" – that is without any knowledge of how many elements I am going to insert.

Is there any solution that would allow me to abstract out tree's depth for this case? Even if AVL is too complicated example, this problem applies also to compile-time-sized vectors and matrices. For now I can solve only hardcoded tasks, which makes my programs completely inflexible.

Demivolt

In before: I have just spotted that insert does not always change AVL tree's depth, but it does not break the question's meritum – Demivolt

Answer 1

You can use another GADT to hide the depth of the tree. (This is called an existential type.)

data SomeAVL a where
  SomeAVL :: AVL n a -> SomeAVL a

With wrappers to operate on SomeAVLs:

insert' :: a -> SomeAVL a -> SomeAVL a
insert' a (SomeAVL t) = SomeAVL (insert a t)

Scaliger

That's what I was looking for. You forgot to add a as argument to insert' btw – Demivolt

Uh oh. Good catch! – Scaliger

Alternate syntax: data SomeAVL a = forall n. SomeAVL (AVL n a) – Denticulation