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:
(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.
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))