Pattern matching against value constructors in type variables / some sort of flexible function-polymorphism in Haskell

Question

Let’s say I have the algebraic data type of a binary tree defined as:

data Tree a = Empty | Node a (Tree a) (Tree a)

To build trees, I now want to define a function (-<) such that I can create trees like this:

1-<(2,3)      1-<(2-<(3,4),5)      1-<(Empty,2-<(4,5))
  1                 1                        1
 / \               / \                        \
2   3             2   5                        2
                 / \                          / \
                3   4                        4   5

It seems it impossible! My reasoning is that it must have type signature a -> (a, a) -> Tree a). I then thought that it might be possible to interpret something of type a either as Tree b for some other type b or, if that fails, plainly as a. In the same manner I tried to define

f :: a -> Int
f (Just _) = 1
f _ = 0

which would be a function that told me whether a value is of type Maybe a and constructed by Just or not. But this doesn’t work – ghc then wants the type signature to be Maybe a -> Int.

Unless I don’t know of any special feature in Haskell, what I want is impossible. My questions now are:

• Is it? Or do I miss something?
• What would be a good approximation to what I want? (I want to go for succintness, so e.g. writing (Right 2 -<(Right 3, Left (Right 4 -<(Right 1, Right 5))) is no solution.)

P.S. I really don’t know how to title this question.

Answer 1

You can write a class which does what you want pretty easily:

{-# LANGUAGE MultiParamTypeClasses, 
  FlexibleInstances, FunctionalDependencies, TypeFamilies, OverlappingInstances, UndecidableInstances #-}

data Tree a = Empty | Node a (Tree a) (Tree a) deriving Show

class Leaf a b | a -> b where
    leaf :: a -> b

instance Leaf (Tree a) (Tree a) where leaf = id

instance (d ~ Tree c) => Leaf c d where leaf a = Node a Empty Empty

mkTree a (b,c) = Node a (leaf b) (leaf c)

The only problem with this approach is that due to defaulting rules, things like mkTree 1 (1,2) will fail because the integer literals are polymorphic, whereas mkTree (1 :: Int) ((1 :: Int),(2 :: Int)) will work. You can make it 'work' with fully polymorphic types by turning on IncoherentInstances but this makes things behave even more strangely so it isn't the best solution.

You mentioned you want a succinct syntax and the 2nd option is only slightly less succinct but will always work when it should instead of giving cryptic type errors, including with fully polymorphic types:

{-# LANGUAGE 
    MultiParamTypeClasses
  , FlexibleInstances
  , FunctionalDependencies
  #-}

data Tree a = Empty | Node a (Tree a) (Tree a) deriving Show

data L a = L a 

class Leaf' a b | a -> b where
    leaf' :: a -> b

instance Leaf' (L a) (Tree a) where
    leaf' (L a) = Node a Empty Empty

instance Leaf' (Tree a) (Tree a) where
    leaf' = id

mkTree' a (b,c) = Node a (leaf' b) (leaf' c)

>1-<(L 2,L 3)
Node 1 (Node 2 Empty Empty) (Node 3 Empty Empty)
>1-<(2-<(L 3,L 4),L 5)
Node 1 (Node 2 (Node 3 Empty Empty) (Node 4 Empty Empty)) (Node 5 Empty Empty)
>1-<(Empty,2-<(L 4,L 5))
Node 1 Empty (Node 2 (Node 4 Empty Empty) (Node 5 Empty Empty))

Answer 2

You could just create three different operators:

(-<) :: a -> (a, a) -> Tree a
p -< (l, r) = Node p (Node l Empty Empty) (Node r Empty Empty)

(-<\) :: a -> (Tree a, a) -> Tree a
p -<\ (lt, r) = Node p lt (Node r Empty Empty)

(-</) :: a -> (a, Tree a) -> Tree a
p -</ (l, rt) = Node p (Node l Empty Empty) rt

then your trees can be expressed as

1-<(2,3)
1-<\(2-<(3,4),5)

and

1-<\(Empty,2-<(4,5))

Answer 3

The function you seek can't have type a -> (a, a) -> Tree a) in Haskell; it simply isn't well-typed at all. The reason is that those as could be any type at all, so you can't use their values in any operation that needs a property of any specific type (such as checking whether they are an Empty or Node value).

The function you're asking for is also ambiguously defined when you remember that you can put trees inside trees, and so a possibility for those as could actually be Tree b. For example, if I tried Empty -< (Empty, Empty) to make a Tree (Tree t) (for some t), is this supposed to return Node Empty Empty Empty where I interpret the (Empty, Empty) as a pair of trees, or Node (Node Empty Empty) (Node Empty Empty) where I interpret the (Empty, Empty) as a pair of "bare values" that need to be turned into leaf nodes? (Or one of the other permutations?)

You could design a language so that this ambiguity is resolvable, but Haskell avoids the issue by making values in a completely arbitrary type (like a) completely opaque. You basically can't do anything at all with such a value other than pass it on to another function that accepts a completely arbitrary type; this can seem limiting, but this is actually a key part of how Haskell types work and responsible for a lot of the safety guarantees that make a lot of generic library code work.

So what you need is for every position to be expecting an a, or a Tree a; it's not possible to accept an "anything" and see whether it is a Tree a. One way to do that is to use a family of functions that covers all the possibilities, as in Lee's answer. That's a lot less fun if there are more than two positions! Another possibility is to only accept trees and use a projection function that turns "bare values" into singleton trees¹. e.g.

data Tree a = Empty | Node a (Tree a) (Tree a)
    deriving (Show, Eq, Ord)

(-<) :: a -> (Tree a, Tree a) -> Tree a
x -< (l, r) = Node x l r

t :: a -> Tree a
t x = Node x Empty Empty

Then you are effectively resolving the ambiguity I mentioned above by using t to "tag" everything that needs to be turned into a tree, while everything without the tag must already be a tree of the correct type.

Your examples would then be written as:

*Main> 1 -< (t 2, t 3)
Node 1 (Node 2 Empty Empty) (Node 3 Empty Empty)
*Main> 1 -< (2 -< (t 3, t 4), t 5)
Node 1 (Node 2 (Node 3 Empty Empty) (Node 4 Empty Empty)) (Node 5 Empty Empty)
*Main> 1 -< (Empty, 2 -< (t 4, t 5))
Node 1 Empty (Node 2 (Node 4 Empty Empty) (Node 5 Empty Empty))

---

¹ This is basically the return function you would write if you were making Tree into a monad, but return is a bit long to sprinkle all through your succinct tree expressions, and seems unrelated to tree-making, so I think a better/shorter name is helpful here (t isn't necessarily great, but it's short and I wasn't feeling terribly inspired).