Is there a way to make more “dynamic” data constructors in Haskell?

Question

Is there some kind of Haskell extension that allows you to create more complex data constructors, then GADT?

Suppose I wanted to create a data structure that is an ordered list, and have a data constructor like (:) that works with lists with a signature type:

 data MyOrdList a where (>>>) :: (Ord a) -> a -> MyOrdList a -> MyOrdList a 

But I want (>>>) have a specific behavior, something like this:

 (>>>) :: (Ord a) => a -> [a] -> [a] x >>> [] = [x] x >>> xs = low ++ [x] ++ high where low = filter (<x) xs high = filter (>x) xs 

Thus, the structure will always be an ordered structure. (I’m not right now, if this is good practice, I’m just offering the simplest example that called me out by the type of behavior I want).

Of course, I can use the function (>>>) , but then I will not have the pattern matching and other advantages that I would have with it. >>> was a data constructor.

Is there a way to do something like this?

Answer 1

You can do :>>> a data constructor, but you need to hide it to preserve your invariant. Note that you can map the template to it, as in render :

 module MyOrdList (mkMyOrdList,MyOrdList,render) where import Data.List import qualified Data.ByteString as BS data MyOrdList a = EmptyDataList | (:>>>) a (MyOrdList a) deriving (Show) mkMyOrdList [] = EmptyDataList mkMyOrdList xs = y :>>> mkMyOrdList ys where y = minimum xs ys = delete y xs render :: (Show a) => MyOrdList a -> String render EmptyDataList = "<empty>" render (x :>>> xs) = (show x) ++ " -> " ++ render xs 

Then you can use the MyOrdList module, as in

 module Main where import Control.Applicative import System.IO import qualified Data.ByteString as BS import MyOrdList main = do h <- openBinaryFile "/dev/urandom" ReadMode cs <- readBytes 10 h -- but you cannot write... -- let bad = 3 :>>> 2 :>>> 1 :>>> EmptyOrdList putStrLn (render $ mkMyOrdList cs) where readBytes 0 _ = return [] readBytes nh = do c <- BS.head <$> BS.hGet h 1 cs <- readBytes (n-1) h return (c:cs) 

Output Example:

  54 -> 57 -> 64 -> 98 -> 131 -> 146 -> 147 -> 148 -> 190 -> 250 -> <empty> 

Answer 2

You can make MyOrdList abstract type and (>>>) function and use presentation templates. For simplicity, I use the standard list as a backend here.

 module MyOrdList (MyOrdList, MyOrdListView (OrdNil, OrdCons), (>>>), emptyOrdList, ordview ) where import Data.List (sort) newtype MyOrdList a = List [a] deriving Show data MyOrdListView a = OrdNil | OrdCons a (MyOrdList a) infixr 5 >>> (>>>) :: (Ord a) => a -> MyOrdList a -> MyOrdList a x >>> (List xs) = List (sort $ x:xs) emptyOrdList = List [] ordview :: MyOrdList a -> MyOrdListView a ordview (List []) = OrdNil ordview (List (x:xs)) = OrdCons x (List xs) 

You can use it like this:

 {-# LANGUAGE ViewPatterns #-} import MyOrdList ordlength :: MyOrdList a -> Int ordlength (ordview -> OrdNil) = 0 ordlength (ordview -> OrdCons x xs) = 1 + ordlength xs 

Works:

 *Main> ordlength $ 2 >>> 3 >>> 1 >>> emptyOrdList 3 *Main> 2 >>> 3 >>> 1 >>> emptyOrdList List [1,2,3] 

So your type is abstract, lists can only be created by emptyOrdList and (>>>) , but you still have the convenience of matching patterns.